Bellman-Ford & Negative Weight Cycle Detection

Bellman-Ford Recap

Input: directed weighted graph $G(V,E,w)$, source $s$.

Init: dist[s]=0, dist[v]=∞ for v≠s
repeat V-1 times:
  for each edge (u,v) in E:
    if dist[u]+w(u,v) < dist[v]: dist[v]=dist[u]+w(u,v); parent[v]=u

After $V-1$ iterations, $dist[v]$ = shortest path weight from $s$ using ≤ $V-1$ edges (any simple path has ≤ $V-1$ edges). Complexity $O(VE)$.

Detecting Negative Cycle

Extra $V$-th iteration:

for each edge (u,v) in E:
  if dist[u]+w(u,v) < dist[v]: // still relaxable
    then v is reachable from a negative cycle (and from s)
    report "Negative cycle exists reachable from s"

Why? In graph without negative cycles, after $V-1$ rounds no edge can be relaxed (shortest paths have converged). If an edge can still be relaxed, the shortest path would require ≥ $V$ edges → must repeat a vertex → contains a cycle. Since total weight decreased by going around cycle, that cycle is negative. Moreover, repeated relaxation can propagate $-\infty$ along all vertices reachable from the cycle.

Finding cycle: To retrieve cycle, follow parent pointers from $v$ $V$ times to get into cycle, then walk until repeat.

Example

Triangle $s→a$ (1), $a→b$ (-2), $b→a$ (-2): sum $b→a→b$ = -4 negative. After $V-1=2$ iterations dist keeps decreasing; Vth iteration detects relaxation.

Scope

• Detects only cycles reachable from $s$. To detect any negative cycle in graph, add super-source $s'$ with 0-edge to all vertices and run Bellman-Ford.
• Dijkstra cannot detect/develop must not be used with negatives.