0
$\begingroup$

I have read that if we run the outer-loop of the Bellman-Ford algorithm for |V| times (where |V| is the number of nodes in the graph) and check if any distance has changed in the |V|th iteration (i.e. the last iteration) then there exists at least one negative weight cycle in the graph. But why does this work? Why only run for |V| times, why not more than that?

  1. I am looking for a mathematical proof on why a change in the value of the distance of a node during the last iteration (|V|th iteration) implies that there is a negative weight cycle?

  2. Can we detect all the nodes that are either reachable or are parts of the negative weight cycles after the |V|th iteration (can this also be proved mathematically)?

It would be helpful if someone can either provide the proofs and explanations or direct to the relevant resources.

Thank you.

$\endgroup$
  • $\begingroup$ Have you checked any textbook? Textbooks covering Bellman–Ford will likely contain the proof. $\endgroup$ – Yuval Filmus Oct 28 at 8:53
2
$\begingroup$

Let us start by observing that after the $k$-th iteration in the main loop, the Bellman-Ford algorithm has computed minimal weight paths (or the weight of such a path if we do not store the predecessors) of length at most $k$ from the starting vertex $s$ to every other vertex of our graph $G$ (if such paths exists).

To prove this, we can use induction: Clearly this holds after the first step as a path of length $1$ is just an edge connecting two vertices. Now suppose we found minimal weight paths from $s$ to any other vertex of length $\leq k$ after the $k$-th step and we execute the $(k + 1)$-th step. Note that any path $p_{sv}$ of length $k + 1$ from $s$ to some vertex $v$ can be formed by taking some path $p_{sw}$ of length $k$ from $s$ to a neighbor $w$ of $v$ and then appending the edge $wv$ and in particular we find that if $p_{sv}$ is of minimal weight w.r.t. all $s$-$v$-paths of length $k + 1$ then $p_{sw}$ must already be weight-minimal w.r.t. all $s$-$w$-paths of length $k$ (otherwise one could use a better path from $s$ to $w$ and adjoin $wv$ to get a path with less weight than $p_{sv}$) and the claim follows.

Now let us address your first question. Note that any simple path (i.e. one that does not self-intersect) between any two vertices in $G$ is of length at most $|V(G)| - 1$ and conversely, any path of length $\geq |V(G)|$ must contain a cycle. Hence, a path from $s$ to $v$ of length $|V(G)|$ (or greater) can be decomposed into three parts: some initial path segment starting at $s$ and ending at some vertex $w$, a cycle (of positive length) starting and ending at $w$ and some final path segment from $w$ to $v$ (note that the path segments need not be cycle-free themselves).

If $G$ contained no negative cycles, then the path obtained from appending the final path segment to the initial one is cannot be of larger weight than the one also containing the cycle and thus, the weight of any path containing a cycle can never be shorter than the cycle-free path obtained from cutting said cycle out in the manner I outlined and in particular, this means that the algorithm cannot improve on the paths it found in $|V(G)| - 1$ steps. However, if at least one negative cycle exists in $G$ we can use the lemma we proved in the beginning we get that the Bellman-Ford-algorithm will find an improved path in the $|V(G)|$-th step which could not exist in a graph with no negative cycles, showing that the graph contains a negative cycle if and only if we detect such an improvement in the $|V(G)|$-th step.

The answer to your second question is negative and it is easy to construct counterexamples where arbitrarily many iterations are needed to find all vertices reachable via paths including negative cycles: Consider the butterfly graph $B$ on the five vertices $v_1, ..., v_5$ such that both $C_1 = \{v_1, v_2, v_3\}$ and $C_3 = \{v_3, v_4, v_5\}$ are the triangles of $B$ (i.e. $v_3$ is the "center vertex" of degree 4) and set the weights such that $C_2$ forms a negative cycle of weight $-1$ while $v_1 v_2$ and $v_1 v_3$ have both weight $0$ and $v_2 v_3$ has weight $n$. Now consider the paths from $v_1$ to $v_2$ -- using the negative cycle $n + 1$ times we are able to find a path better than the one consisting only of the edge $v_1 v_2$ but such a path has length $2 + 3 \cdot (n + 1)$ and hence by choosing $n$ to be some large enough value (really $n > 1$ suffices) and recalling our initial result we can see that the Bellman-Ford algorithm will not find that $v_2$ can be reached via a negative cycle until step $2 + 3 \cdot (n + 1)$. Since of course every vertex in such a negative weight cycle is also one reachable via one, this also negatively answers the second part of this question.

However, note that if some vertex $v$ cannot be reached via a negative cycle from the starting vertex $s$ then the distance (in the algorithm's table) between $s$ and $v$ can only decrease at most $|V(G)| - 1$ times while for any vertex that can be reached via a negative cycle said distance can decrease arbitrarily often, so it is possible to find all such vertices eventually with some additional bookkeeping.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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