How Does Bellman-Ford Detect Negative-Weight Cycles?

The Bellman-Ford algorithm finds the shortest paths from a single source vertex to all other vertices in a weighted, directed graph. Unlike Dijkstra's algorithm, Bellman-Ford handles edges with negative weights and can identify negative-weight cycles. It does this by repeatedly relaxing all edges in the graph and then performing one final check to see if any distance can still be improved.

Understanding Edge Relaxation

In a graph \(G = (V, E)\) with \(|V|\) vertices and \(|E|\) edges, each vertex \(v\) is initialized with a distance estimate \(d[v] = \infty\), except for the source vertex \(s\), which is set to \(d[s] = 0\).

Relaxing an edge \((u, v)\) with weight \(w(u, v)\) means checking whether the path to \(v\) can be shortened by going through \(u\):

\[d[u] + w(u, v) < d[v]\]

If this condition holds, the algorithm updates \(d[v] = d[u] + w(u, v)\).

Why \(|V| - 1\) Iterations Are Enough

In any graph without negative-weight cycles, a shortest path between two vertices contains at most \(|V| - 1\) edges, because visiting any vertex more than once would form a cycle that only adds to or maintains the total path weight.

By relaxing every edge in the graph \(|V| - 1\) times, Bellman-Ford guarantees that the shortest-path distances have propagated across all possible simple paths. After \(|V| - 1\) iterations, every reachable vertex \(v\) has settled on its true shortest-path distance \(d[v]\).

The Negative-Weight Cycle Check

A negative-weight cycle is a cycle whose edge weights sum to a negative value. If such a cycle is reachable from the source vertex \(s\), there is no well-defined shortest path to vertices on or reachable from that cycle, because traversing the cycle repeatedly reduces the total path weight indefinitely toward \(-\infty\).

To detect this, Bellman-Ford performs one additional pass—the \(|V|\)-th iteration—over all edges \((u, v) \in E\):

• If \(d[u] + w(u, v) < d[v]\) is still true for any edge \((u, v)\), then a shorter path was found after \(|V| - 1\) relaxations.
• Because a simple path can have at most \(|V| - 1\) edges, any further reduction in distance proves the existence of a negative-weight cycle reachable from \(s\).

Complexity and Limitations

The time complexity of Bellman-Ford is \(O(|V| \cdot |E|)\), as it relaxes all \(|E|\) edges \(|V|\) times (including the final detection pass). Its space complexity is \(O(|V|)\) to store the distance estimates and predecessor pointers.

Note that the standard \(|V|\)-th pass only detects negative-weight cycles that are reachable from the source vertex \(s\). If a graph contains a negative-weight cycle in a disconnected component that cannot be reached from \(s\), \(d[u]\) will remain \(\infty\) for those vertices, and the condition \(d[u] + w(u, v) < d[v]\) will not trigger. To detect negative-weight cycles anywhere in a disconnected graph, a common technique is to add a dummy source vertex connected to every other vertex with a zero-weight edge.