Negative Weight Cycle & Bellman-Ford Algorithm

Negative Weight Cycle

Directed cycle $C$ with sum $\sum_{e\in C} w(e) <0$. In such graph, shortest path from source to vertices reachable from $C$ is undefined ($-\infty$) because traversing cycle repeatedly reduces path weight arbitrarily. Example: $a→b$ -2, $b→a$ -1 → cycle -3.

Without negative cycles, shortest simple paths well-defined (≤ $V-1$ edges).

Bellman-Ford — Single Source Shortest Paths (SSSP) with Negatives

BellmanFord(G, s):
  dist[s]=0; dist[v]=∞ for v≠s; parent[v]=NIL
  repeat V-1 times:
    for each edge (u,v)∈E:
      if dist[u]+w(u,v) < dist[v]:
        dist[v]=dist[u]+w(u,v); parent[v]=u
  // detect negative cycle
  for each edge (u,v):
    if dist[u]+w(u,v) < dist[v]:
      return "Negative cycle reachable from s" (and retrieve cycle via parent)
  return dist, parent

Correctness: After $i$ iterations, $dist[v]$ = shortest path using ≤ $i$ edges. After $V-1$, all simple paths considered. If still relaxable → ≥ $V$ edges → must contain cycle → negative.

Complexities: Time $O(VE)$ (list) / $O(V^3)$ (matrix), Space $O(V)$. Superior to Dijkstra which fails with negatives; slower but handles them.

Finding All Negative Cycles: Add super source $s'$ with 0 edges to all vertices, run once to detect any cycle in graph.