Bellman-Ford and Negative Cycles
Run n-1 relaxation passes over all edges, detect negative cycles with a final pass, and explain why Dijkstra fails on negative-weight edges.
Why Bellman-Ford Exists
Bellman-Ford solves the single-source shortest path problem like Dijkstra, but it handles negative edge weights. It also detects negative cycles — cycles whose total weight is negative, making it impossible to define a finite shortest path through them. While slower than Dijkstra, Bellman-Ford is the correct choice whenever the graph may contain negative-weight edges.
Relaxation: The Core Operation
Bellman-Ford is built on a single operation: relaxation. Relaxing edge (u, v, w) means: if dist[u] + w < dist[v], update dist[v] = dist[u] + w. We repeatedly relax all edges. The key insight is: any shortest path has at most V-1 edges (in a graph with no negative cycles). Therefore, V-1 rounds of relaxation over all edges are sufficient to find all shortest paths.
All lessons in this course
- Dijkstra's Algorithm with a Priority Queue
- Bellman-Ford and Negative Cycles
- Floyd-Warshall: All-Pairs Shortest Paths
- Network Delay Time and Path Reconstruction