Shortest paths between every pair of vertices — by running a single-source algorithm |V| times, by a five-line dynamic program, or by reweighting the graph so the fast algorithm becomes legal.
Chapter 22 computed distances from one source. Now compute them from all sources at once, producing a |V| × |V| matrix. The obvious approach is to run a single-source algorithm from every vertex, and for non-negative weights that is genuinely competitive. The chapter’s two original contributions are Floyd-Warshall, a Θ(V³) dynamic program of remarkable brevity, and Johnson’s algorithm, which uses a clever reweighting to make Dijkstra usable on graphs with negative edges.
Input: a weighted directed graph given as an n × n adjacency matrix W, where
wᵢⱼ = 0 if i == j
= w(i,j) if i ≠ j and (i,j) ∈ E
= ∞ if i ≠ j and (i,j) ∉ EOutput: an n × n matrix D with dᵢⱼ = δ(i,j), plus a predecessor matrix Π for reconstructing the paths.
| Baseline approach | Time | Allows negative edges? |
|---|---|---|
| Dijkstra from each vertex, binary heap | O(V E lg V) | No |
| Dijkstra from each vertex, Fibonacci heap | O(V² lg V + V E) | No |
| Bellman-Ford from each vertex | O(V² E), i.e. O(V⁴) on a dense graph | Yes |
O(V⁴) on a dense graph. The rest of the chapter beats that: Floyd-Warshall gets Θ(V³) with negative edges allowed, and Johnson gets down to repeated-Dijkstra speed while allowing negative edges.Section 23.1 builds a first dynamic program that turns out to have a surprising algebraic shape.
Let lᵢⱼ(m) be the minimum weight of any path from i to j using at most m edges. Then
lᵢⱼ(m) = min over 1 ≤ k ≤ n of ( lᵢₖ(m-1) + wₖⱼ )cᵢⱼ = ∑ₖ aᵢₖ·bₖⱼ. Replace + by min and · by + and you get exactly the recurrence above. Shortest paths live in the (min, +) semiring, and extending paths by one edge is matrix multiplication in that algebra.Since shortest paths are simple and use at most n-1 edges, L(n-1) is the answer. Computing it by repeated multiplication takes n-1 products at Θ(n³) each, giving Θ(n⁴) — no better than repeated Bellman-Ford.
But the operation is associative, so use repeated squaring: compute L(1), L(2), L(4), L(8), … and stop once the exponent reaches n-1. That is only ⌈lg(n-1)⌉ multiplications:
Θ(n³ lg n)(min, +) semiring has no inverse for min — you cannot “un-min” a value. So sub-cubic matrix multiplication does not transfer to shortest paths. This is a genuinely instructive limitation, and CLRS points it out explicitly.A different and better dynamic program. Instead of bounding the number of edges, bound which vertices may appear as intermediates.
dᵢⱼ(k) be the weight of a shortest path from i to j all of whose intermediate vertices are drawn from {1, 2, …, k}. Then either the shortest such path avoids vertex k entirely, or it goes through k exactly once — splitting into i ↝ k and k ↝ j, both using only intermediates from {1, …, k-1}. ╱ wᵢⱼ if k == 0
dᵢⱼ(k) = │
╱ min( dᵢⱼ(k-1), dᵢₖ(k-1) + dₖⱼ(k-1) ) if k ≥ 1FLOYD-WARSHALL(W, n)
1 D(0) = W
2 for k = 1 to n
3 let D(k) = (dᵢⱼ(k)) be a new n × n matrix
4 for i = 1 to n
5 for j = 1 to n
6 dᵢⱼ(k) = min( dᵢⱼ(k-1), dᵢₖ(k-1) + dₖⱼ(k-1) )
7 return D(n)Θ(V³) time, and with in-place update only Θ(V²) space. Three nested loops and one min — among the shortest non-trivial algorithms in the book.
k must be the outermost loop. Writing for i { for j { for k } } compiles, runs, and produces wrong answers, because the recurrence requires all of D(k-1) to be complete before any entry of D(k) is computed. This is the single most common Floyd-Warshall bug.Negative edges are fine, and negative cycles are detectable: after the algorithm, if any diagonal entry dᵢᵢ < 0, there is a negative-weight cycle through vertex i. That check is one pass over the diagonal.
A pleasing specialisation. To decide merely whether a path exists between each pair, run Floyd-Warshall with booleans: replace min by logical OR and + by logical AND.
tᵢⱼ(k) = tᵢⱼ(k-1) ∨ ( tᵢₖ(k-1) ∧ tₖⱼ(k-1) )Still Θ(V³), but with single-bit values instead of weights, which is faster in practice and allows bitset tricks that process many j values per machine word.
The most ingenious result in the chapter. Goal: get repeated-Dijkstra speed on a graph that has negative edges.
The obvious fix — add a constant to every edge to make all weights non-negative — does not work, because it penalises paths with more edges. A 3-edge path gains 3c while a 1-edge path gains only c, so the shortest path can change.
h(v) and defineŵ(u,v) = w(u,v) + h(u) - h(v)Sum this along any path v₀ → v₁ → … → vₖ and the h terms telescope:
ŵ(p) = w(p) + h(v₀) - h(vₖ)What remains is choosing h so that all ŵ are non-negative. Johnson’s answer: add a new vertex s with a zero-weight edge to every vertex, run Bellman-Ford once from s, and set h(v) = δ(s,v). The triangle inequality then gives δ(s,v) ≤ δ(s,u) + w(u,v), which rearranges to exactly ŵ(u,v) ≥ 0.
JOHNSON(G, w)
1 form G′ by adding a new vertex s with a 0-weight edge to every v ∈ G.V
2 if BELLMAN-FORD(G′, w, s) == FALSE
3 report "the input graph contains a negative-weight cycle"
4 else
5 for each v ∈ G′.V: h(v) = δ(s, v)
6 for each edge (u,v) ∈ G′.E: ŵ(u,v) = w(u,v) + h(u) - h(v)
7 for each vertex u ∈ G.V
8 run DIJKSTRA(G, ŵ, u) to compute δ̂(u,v) for all v
9 for each v ∈ G.V
10 dᵘᵛ = δ̂(u,v) + h(v) - h(u) // undo the reweighting
11 return D| Step | Cost |
|---|---|
| One Bellman-Ford | O(V E) |
| Reweighting all edges | O(E) |
|V| runs of Dijkstra with a Fibonacci heap | O(V² lg V + V E) — dominates |
| Total | O(V² lg V + V E) |
|V| times. On a sparse graph with E = O(V) that is O(V² lg V), dramatically better than Floyd-Warshall’s Θ(V³). This pattern — a cheap preprocessing pass that converts a hard instance into an easy one — is worth carrying beyond this chapter.| Algorithm | Time | Negative edges | Best for |
|---|---|---|---|
| Repeated Dijkstra | O(V² lg V + V E) | No | Non-negative weights |
| Repeated Bellman-Ford | O(V² E) | Yes | Nothing — Johnson dominates it |
| Matrix squaring | Θ(V³ lg V) | Yes | Conceptual interest |
| Floyd-Warshall | Θ(V³) | Yes | Dense graphs; simplest to write |
| Johnson | O(V² lg V + V E) | Yes | Sparse graphs with negative edges |
|V| priority-queue algorithms with scattered access. For graphs up to a few thousand vertices, the five-line version usually beats the asymptotically better one.|V| × |V| matrix, so this chapter uses adjacency matrices throughout.(min, +) semiring. Repeated squaring gives Θ(V³ lg V). Strassen does not apply, because min has no inverse.dᵢⱼ(k) = min(dᵢⱼ(k-1), dᵢₖ(k-1) + dₖⱼ(k-1)).Θ(V³), Θ(V²) space in place, negative edges allowed. k must be the outermost loop or the answers are silently wrong.min/+ for OR/AND gives transitive closure.ŵ(u,v) = w(u,v) + h(u) - h(v) telescopes along any path, so the correction depends only on the endpoints and shortest paths are preserved. Naively adding a constant to every edge does not work.h, then |V| Dijkstras: O(V² lg V + V E). Better than Floyd-Warshall on sparse graphs.Chapter 24 changes the question from distance to throughput. In a flow network, edges have capacities and the goal is to push as much as possible from a source to a sink. The Ford-Fulkerson method and the max-flow min-cut theorem are the core, and Chapter 25 then shows that bipartite matching is a flow problem in disguise.