One operation, relaxation, plus three ways of choosing the order in which to apply it — giving three algorithms with different assumptions and different costs.
Given a weighted directed graph and a source s, find a shortest path from s to every other vertex. Every algorithm in this chapter maintains an estimate v.d ≥ δ(s,v) and improves it by relaxing edges until the estimates equal the true distances. What separates the algorithms is the order of relaxation and what they assume about the weights: Bellman-Ford handles negative edges and detects negative cycles, the DAG algorithm exploits acyclicity for linear time, and Dijkstra is fastest but requires non-negative weights.
The shortest-path weight from u to v is δ(u,v), the minimum weight over all paths, or ∞ if no path exists.
s to v passes through a cycle of negative total weight, you can go round it repeatedly and drive the weight to -∞. No shortest path exists, and CLRS defines δ(s,v) = -∞ for such vertices. Algorithms must either forbid negative cycles or detect them. Negative edges are fine; negative cycles are not.Two structural facts used constantly:
|V| - 1 edges. That bound is exactly why Bellman-Ford runs |V| - 1 passes.Every algorithm maintains two attributes per vertex: v.d, an upper-bound estimate on δ(s,v), and v.π, the predecessor on the best path found so far.
(u,v) asks whether going through u improves the best known route to v, and if so updates the estimate and the predecessor. This is the only operation that ever changes d or π.INITIALIZE-SINGLE-SOURCE(G, s) RELAX(u, v, w)
1 for each v ∈ G.V 1 if v.d > u.d + w(u,v)
2 v.d = ∞ 2 v.d = u.d + w(u,v)
3 v.π = NIL 3 v.π = u
4 s.d = 0Three lines. Every algorithm below differs only in which edges it relaxes and in what order.
Section 22.5 proves these; they are the toolkit for every correctness argument in the chapter.
| Property | Statement |
|---|---|
| Triangle inequality | δ(s,v) ≤ δ(s,u) + w(u,v) for any edge (u,v). |
| Upper-bound | v.d ≥ δ(s,v) always, and once v.d reaches δ(s,v) it never changes again. |
| No-path | If there is no path from s to v, then v.d = δ(s,v) = ∞ always. |
| Convergence | If s ↝ u → v is a shortest path and u.d = δ(s,u) before relaxing (u,v), then v.d = δ(s,v) afterwards and forever. |
| Path-relaxation | If the edges of a shortest path to v are relaxed in path order (possibly interleaved with others), then v.d = δ(s,v). |
The most general algorithm: it allows negative edges and reports whether a negative cycle is reachable from the source.
BELLMAN-FORD(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 for i = 1 to |G.V| - 1 // |V|-1 passes
3 for each edge (u,v) ∈ G.E
4 RELAX(u, v, w)
5 for each edge (u,v) ∈ G.E // one extra pass: still improving?
6 if v.d > u.d + w(u,v)
7 return FALSE // negative-weight cycle
8 return TRUEO(V E) — |V|-1 passes over all |E| edges.
|V| - 1 passes suffice. A shortest path is simple, so it has at most |V|-1 edges. After pass i, every vertex reachable by a shortest path of i or fewer edges has its correct distance — each pass relaxes every edge, so it certainly relaxes the next edge of every shortest path. By the path-relaxation property, |V|-1 passes finish the job.|V|-1 passes and no further relaxation can succeed. So if any edge still improves on pass |V|, some distance is still falling, which can only happen if a negative cycle is reachable.If the graph is acyclic, shortest paths get much easier — and negative edges cause no trouble, since a DAG has no cycles at all.
DAG-SHORTEST-PATHS(G, w, s)
1 topologically sort the vertices of G
2 INITIALIZE-SINGLE-SOURCE(G, s)
3 for each vertex u, taken in topologically sorted order
4 for each v ∈ G.Adj[u]
5 RELAX(u, v, w)Θ(V + E) — linear. One topological sort plus one pass, relaxing each edge exactly once.
Topological order guarantees that when u is processed, every path into u has already been fully relaxed, so u.d is already final. That is the path-relaxation property satisfied by construction, with no repetition needed.
DIJKSTRA(G, w, s)
1 INITIALIZE-SINGLE-SOURCE(G, s)
2 S = ∅ // vertices with final distances
3 Q = G.V // min-priority queue keyed on d
4 while Q ≠ ∅
5 u = EXTRACT-MIN(Q) // closest unfinalised vertex
6 S = S ∪ {u}
7 for each v ∈ G.Adj[u]
8 RELAX(u, v, w) // may DECREASE-KEY v in Qw(u,v), Dijkstra on the path total u.d + w(u,v). Three algorithms, one skeleton.Correctness (Theorem 22.6). The loop invariant is that v.d = δ(s,v) for every v ∈ S. The key step: when u is extracted it has the minimum d among unfinalised vertices, and because all weights are non-negative, any path reaching u through a vertex still outside S would have to be at least as long. So u.d is already correct.
| Priority queue | Total time | Good for |
|---|---|---|
| Array | O(V²) | Dense graphs |
| Binary min-heap | O((V + E) lg V) = O(E lg V) | Sparse graphs |
| Fibonacci heap | O(V lg V + E) | Best asymptotically |
| Bellman-Ford | DAG | Dijkstra | |
|---|---|---|---|
| Requires | No negative cycles | Acyclic graph | Non-negative weights |
| Negative edges | Yes | Yes | No |
| Detects negative cycles | Yes | N/A | No |
| Time | O(VE) | Θ(V+E) | O(E lg V) |
| Strategy | Brute-force relaxation | Topological order | Greedy |
| Relaxations per edge | |V|-1 | Exactly 1 | Once per incident extraction |
O(VE). Need negative-cycle detection? Only Bellman-Ford offers it.Section 22.4 gives an application that is far from graphs at first sight. A system of difference constraints is a set of inequalities of the form
xⱼ - xᵢ ≤ bₖBuild a constraint graph with one vertex per variable plus a source v₀ with a zero-weight edge to every other vertex. For each constraint xⱼ - xᵢ ≤ bₖ, add edge (vᵢ, vⱼ) with weight bₖ.
xᵢ = δ(v₀, vᵢ) is a feasible solution. If it does have one, the system is infeasible. So Bellman-Ford solves linear programming feasibility for this class of constraints in O(VE).The intuition is the triangle inequality: δ(v₀, vⱼ) ≤ δ(v₀, vᵢ) + w(vᵢ, vⱼ) is literally the constraint xⱼ - xᵢ ≤ bₖ rearranged. Difference constraints appear in scheduling with relative deadlines and in temporal reasoning, and this is a nice preview of Chapter 29.
d or π. Every algorithm here differs only in the order of relaxations.-∞). Negative edges are fine; negative cycles are not.|V|-1 edges — which is exactly why Bellman-Ford runs |V|-1 passes.|V|-1 passes over all edges, plus one more to detect negative cycles. O(VE), most general.Θ(V+E) linear, negative edges welcome. Negate weights for longest path and critical-path analysis.O(E lg V) with a binary heap. Fails silently on negative edges.Chapter 23 asks for shortest paths between every pair of vertices. Running Dijkstra from each source is one option; the chapter also gives Floyd-Warshall, an elegant Θ(V³) dynamic program that handles negative edges, and Johnson’s algorithm, which reweights the graph so Dijkstra becomes usable even when negative edges are present.