Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
