# Summation over shortest path lengths

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.