0
$\begingroup$

Suppose directed graph $G=(V,E)$, let $\delta(u,v)$ as the shortest path between any pair $u,v\in V$. Also there is no negative cycle in $G$. Can we conclude that $$\sum_{u\in V}\sum_{v\in V}\delta(u,v)\geq0\;\;?$$

I try to find a counter example but I guess that it's true because if $\sum_{u\in V}\sum_{v\in V}\delta(u,v)<0$ there is negative cycle in $G$ but I can't prove it. Any hint will appreciated.

$\endgroup$
0

1 Answer 1

1
$\begingroup$

I will assume that $\delta(u,v)$ denotes the distance from $u$ to $v$ in $G$ (and not the shortest path) and that $\delta(u,v) = +\infty$ if $v$ is not reachable from $u$.

You can write: $$\sum_{u\in V}\sum_{v\in V}\delta(u,v) = \frac{1}{2} \cdot\sum_{u\in V}\sum_{v\in V} \left( \delta(u,v) + \delta(v,u) \right) $$

Then you just need to observe that $\delta(u,v) + \delta(v,u) \ge 0$ for all choices of $u,v$. Indeed, if $\delta(u,v) + \delta(v,u) < 0$ then the concatenation of a shortest path from $u$ to $v$ with a shortest path from $v$ to $u$ yields a closed walk $W = \langle u= w_1, w_2, \dots, w_k = u\rangle$ of negative total weight.

$W$ might contain repeated intermediate vertices, hence it might not be a (simple) cycle. If you are fine with that, you are done.

Otherwise there must be some repeated vertex $w = w_j = w_h$ with $j < h$ (and $(j,h) \neq (1,k)$) and you can decompose the edges of $W$ into two closed walks $W_1 = \langle u = w_1, w_2, \dots w_j, w_{h+1}, \dots w_k = u \rangle$ and $W_2 = \langle w = w_j, w_{j+1}, \dots, w_k = w\rangle$. At least one walk between $W_1$ and $W_2$, say $W^*$, has negative total weight. Either $W^*$ is a cycle and you are done, or you can repeat the same argument on $W^*$. This process eventually stops since the number of vertices (counting repetitions) in $W^*$ is monotonically decreasing.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.