Sum of edge weights in cycles of a directed graph I am studying for an exam in graph theory and algorithms, and am stuck on the following problem:
Let $G=(V,E)$ be a directed graph with edge weights $c:E(G) \rightarrow \mathbb{R}$.
Show that the following two statements are equivalent:
(1) $c$ is conservative, that is, there is no cycle with negative weight in $(G,c)$.
(2) There is a function $\pi:V(G) \rightarrow \mathbb{R}$ such that the relation $c(e) + \pi(v) - \pi(w) \geq 0 $ holds for all edges $ e = (v,w) \in E(G)$.
My attempted solution so far: Assuming (2) is true, look at any cycle in $G$, let the cycle have $k$ edges and $k$ unique vertices. We label the edges $1,...,k$ and the vertices $1,...,k$, such that $e_i = (v_i,v_{i+1})$ for $1 \leq i \leq k-1$ and $e_k = (v_k,v_1)$. (2) then yields
$$\pi_1 + c_1 \geq \pi_2$$
$$\pi_2 + c_2 \geq \pi_3$$
$$...$$
$$\pi_{k} + c_k \geq \pi_1.$$
Combining all these, we get $\pi_1 + c_1 + c_2 +...+c_k \geq \pi_1$, so the sum of weights in any cycle must be greater than or equal to zero, implying (1). So if I did this right, (2) $\Rightarrow$ (1) should be ok.
This is where I am stuck: how do I prove (1) $\Rightarrow$ (2), or $\neg$(2) $\Rightarrow$ $\neg$(1)? (2) has to hold for all edges, so I cannot just look at cycles. I am unsure how to approach this. A second part of the problem concerns proving that a suitable $\pi$ can be computed in $O(nm)$ time complexity, with $n$ the number of vertices in $G$ and $m$ the number of edges. I sense that if I can grasp the first part, that second part would also be within grasp.
 A: Your solution to the first part is correct. As for the second part, let's add a new vertex $s$ to $G$, along with a directed edge $sv$ with zero cost for all $v \in V$. (*) For each vertex $v$, let $\pi(v)$ be the length of a shortest $s-v$ path in $G$. You should try showing that this $\pi$ has the desired property; more precisely, if $vw$ was an edge with $c(vw) + \pi(v) < \pi(w)$, then a walk consisting of a shortest $s-v$ path and then the edge $vw$ would contain a negative cycle.
Such a function $\pi$ is sometimes called a feasible potential (with respect to $c$). We can define another cost function $c'$ on $G$ by letting $c'(vw) = c(vw) + \pi(v) - \pi(w)$. Then the condition on $\pi$ means exactly that $c'$ is non-negative. The interesting observation is that for any walk in $G$ starting with some vertex $u$ and ending with $v$, the cost of the walk according to $c'$ is the cost according to $c$ plus $\pi(v) - \pi(u)$. In other words, the cost of every $u-v$ walk changes by the same amount. This means that shortest paths according to $c$ are the same as the shortest paths according to $c'$!
Using this observation, we can find the shortest path between all pairs of vertices in $G$ by first computing a feasible potential and then using Dijkstra's algorithm with the cost function $c'$ for each source vertex $v$ to find shortest paths starting from $v$. This is called Johnson's algorithm. Note that this is faster than running the Bellman-Ford algorithm for each source vertex (and if the graph is sparse, then it is even faster than the Floyd-Warshall algorithm).
(*) Instead of this, we could just take a source vertex from each connected component (in the undirected sense) of $G$ and do the same thing component-wise, but I think this is slightly cleaner.
