Chapter 25: All-Pairs Shortest Paths

Given a weighted, directed graph G = (V, E) with weight function w: E → ℝ, find the shortest (least-weight) path from u to v for every pair of vertices u, v ∈ V. Output is an n × n matrix D = (d_ij), where d_ij = δ(i, j).

Naive approaches:

• Run a single-source algorithm |V| times (once per source vertex)
  • Dijkstra's (no negative edges): O(V³) with linear array, O(VE lg V) with binary heap, O(V² lg V + VE) with Fibonacci heap
  • Bellman-Ford (negative edges allowed): O(V²E), which is O(V⁴) on dense graphs

Input representation: An n × n adjacency matrix W = (w_ij) where:

• w_ij = 0 if i = j
• w_ij = weight of edge (i, j) if i ≠ j and (i, j) ∈ E
• w_ij = ∞ if i ≠ j and (i, j) ∉ E

Negative-weight edges are allowed, but no negative-weight cycles.

Predecessor matrix Π = (π_ij): π_ij is NIL if i = j or no path exists; otherwise π_ij is the predecessor of j on some shortest path from i.

PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j)
1  if i == j
2      print i
3  elseif π_ij == NIL
4      print "no path from" i "to" j "exists"
5  else PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, π_ij)
6      print j

---

Shortest Paths and Matrix Multiplication

A dynamic-programming approach where each iteration resembles matrix multiplication.

Structure of a Shortest Path

All subpaths of a shortest path are shortest paths (Lemma 24.1). Decompose a shortest path p from i to j (with at most m edges) into i →(p')→ k → j, where p' has at most m − 1 edges. Then δ(i, j) = δ(i, k) + w_kj.

Recursive Solution

Let l_ij^(m) = minimum weight of any path from i to j using at most m edges.

Base case (m = 0):

• l_ij^(0) = 0 if i = j
• l_ij^(0) = ∞ if i ≠ j

Recurrence (m ≥ 1):

l_ij^(m) = min_{1 ≤ k ≤ n} { l_ik^(m−1) + w_kj }

Since any simple shortest path has at most n − 1 edges:

δ(i, j) = l_ij^(n−1) = l_ij^(n) = l_ij^(n+1) = ...

Bottom-Up Computation

Compute L^(1), L^(2), ..., L^(n−1) where L^(1) = W. The core operation extends shortest paths by one edge:

EXTEND-SHORTEST-PATHS(L, W)
1  n = L.rows
2  let L' be a new n × n matrix
3  for i = 1 to n
4      for j = 1 to n
5          l'_ij = ∞
6          for k = 1 to n
7              l'_ij = min(l'_ij, l_ik + w_kj)
8  return L'

Running time: Θ(n³) per call (three nested loops).

Analogy to Matrix Multiplication

EXTEND-SHORTEST-PATHS is identical to standard matrix multiplication with the substitutions:

• min replaces +
• + replaces ×
• ∞ (identity for min) replaces 0 (identity for +)

Slow Algorithm — Θ(n⁴)

SLOW-ALL-PAIRS-SHORTEST-PATHS(W)
1  n = W.rows
2  L^(1) = W
3  for m = 2 to n − 1
4      let L^(m) be a new n × n matrix
5      L^(m) = EXTEND-SHORTEST-PATHS(L^(m−1), W)
6  return L^(n−1)

Calls EXTEND-SHORTEST-PATHS n − 2 times → Θ(n⁴) total.

Faster Algorithm via Repeated Squaring — Θ(n³ lg n)

We only need L^(n−1), not all intermediate matrices. Since the "multiplication" is associative, use repeated squaring:

L^(1) = W, L^(2) = W·W, L^(4) = W²·W², L^(8) = W⁴·W⁴, ...

Only ⌈lg(n − 1)⌉ matrix products needed.

FASTER-ALL-PAIRS-SHORTEST-PATHS(W)
1  n = W.rows
2  L^(1) = W
3  m = 1
4  while m < n − 1
5      let L^(2m) be a new n × n matrix
6      L^(2m) = EXTEND-SHORTEST-PATHS(L^(m), L^(m))
7      m = 2m
8  return L^(m)

Running time: Θ(n³ lg n) — each of the ⌈lg(n − 1)⌉ products takes Θ(n³).

---

The Floyd-Warshall Algorithm

A different dynamic-programming formulation that runs in Θ(n³) time. Allows negative-weight edges but no negative-weight cycles.

Structure: Intermediate Vertices

An intermediate vertex of a simple path p = ⟨v₁, v₂, ..., v_l⟩ is any vertex other than v₁ or v_l (i.e., {v₂, v₃, ..., v_{l−1}}).

Consider all paths from i to j whose intermediate vertices are drawn from {1, 2, ..., k}. Let p be a minimum-weight such path:

• If k is NOT an intermediate vertex of p: all intermediate vertices are in {1, 2, ..., k−1}, so the shortest path using {1, ..., k} is the same as using {1, ..., k−1}.
• If k IS an intermediate vertex of p: decompose p into i →(p₁)→ k →(p₂)→ j, where both p₁ and p₂ use only intermediate vertices in {1, 2, ..., k−1}.

Recursive Solution

Let d_ij^(k) = weight of a shortest path from i to j with all intermediate vertices in {1, 2, ..., k}.

Base case (k = 0):

d_ij^(0) = w_ij

Recurrence (k ≥ 1):

d_ij^(k) = min( d_ij^(k−1), d_ik^(k−1) + d_kj^(k−1) )

Final answer: D^(n) = (d_ij^(n)) gives d_ij^(n) = δ(i, j) for all i, j.

The Algorithm

FLOYD-WARSHALL(W)
1  n = W.rows
2  D^(0) = W
3  for k = 1 to n
4      let D^(k) be a new n × n matrix
5      for i = 1 to n
6          for j = 1 to n
7              d_ij^(k) = min(d_ij^(k−1), d_ik^(k−1) + d_kj^(k−1))
8  return D^(n)

Running time: Θ(n³) — triply nested loops, O(1) per iteration. Tight code with small constant factor.

Space optimization: Can drop all superscripts and use a single matrix D, updating in place — only Θ(n²) space needed.

Constructing Shortest Paths

Compute predecessor matrices Π^(0), Π^(1), ..., Π^(n) alongside D^(k).

Base case (k = 0):

π_ij^(0) = NIL if i = j or w_ij = ∞ π_ij^(0) = i if i ≠ j and w_ij < ∞

Recurrence (k ≥ 1):

π_ij^(k) = π_ij^(k−1) if d_ij^(k−1) ≤ d_ik^(k−1) + d_kj^(k−1) π_ij^(k) = π_kj^(k−1) if d_ij^(k−1) > d_ik^(k−1) + d_kj^(k−1)

Final predecessor matrix: Π = Π^(n).

Transitive Closure of a Directed Graph

Given G = (V, E), the transitive closure is G* = (V, E*) where E* = {(i, j) : there is a path from i to j in G}.

Method 1: Assign weight 1 to each edge, run Floyd-Warshall. If d_ij < n, a path exists; if d_ij = ∞, no path exists.

Method 2 (more efficient in practice): Replace arithmetic with logical operations:

• ∨ (OR) replaces min
• ∧ (AND) replaces +

Define t_ij^(k) = 1 if a path from i to j exists using intermediate vertices in {1, ..., k}, else 0.

Base case:

• t_ij^(0) = 1 if i = j or (i, j) ∈ E
• t_ij^(0) = 0 otherwise

Recurrence:

t_ij^(k) = t_ij^(k−1) ∨ (t_ik^(k−1) ∧ t_kj^(k−1))

TRANSITIVE-CLOSURE(G)
1  n = |G.V|
2  let T^(0) be a new n × n matrix
3  for i = 1 to n
4      for j = 1 to n
5          if i == j or (i, j) ∈ G.E
6              t_ij^(0) = 1
7          else t_ij^(0) = 0
8  for k = 1 to n
9      let T^(k) be a new n × n matrix
10     for i = 1 to n
11         for j = 1 to n
12             t_ij^(k) = t_ij^(k−1) ∨ (t_ik^(k−1) ∧ t_kj^(k−1))
13 return T^(n)

Running time: Θ(n³), but faster in practice — logical operations on single bits are faster than arithmetic, and space usage is reduced (boolean vs. integer).

---

Johnson's Algorithm for Sparse Graphs

Finds all-pairs shortest paths in O(V² lg V + VE) time. Asymptotically faster than Floyd-Warshall or repeated squaring for sparse graphs. Uses adjacency lists.

Key idea: Reweight edges to eliminate negative weights, then run Dijkstra's algorithm from each vertex.

Reweighting — Preserving Shortest Paths

Lemma 25.1: Given any function h: V → ℝ, define new weights:

ŵ(u, v) = w(u, v) + h(u) − h(v)

Then for any path p from v₀ to v_k:

ŵ(p) = w(p) + h(v₀) − h(v_k)

Consequences:

• A path p is a shortest path under w if and only if it is a shortest path under ŵ (the h terms depend only on endpoints, not the path)
• G has a negative-weight cycle under w if and only if it has one under ŵ (for a cycle, h(v₀) − h(v_k) = 0)

Producing Nonnegative Weights

1. Construct G' = (V', E') where V' = V ∪ {s} (new vertex s) and E' = E ∪ {(s, v) : v ∈ V} with w(s, v) = 0 for all v
2. Run Bellman-Ford from s on G' to get h(v) = δ(s, v) for all v ∈ V'
3. By the triangle inequality: h(v) ≤ h(u) + w(u, v), so ŵ(u, v) = w(u, v) + h(u) − h(v) ≥ 0

The Algorithm

JOHNSON(G, w)
1  compute G' where G'.V = G.V ∪ {s},
       G'.E = G.E ∪ {(s, v) : v ∈ G.V},
       and w(s, v) = 0 for all v ∈ G.V
2  if BELLMAN-FORD(G', w, s) == FALSE
3      print "the input graph contains a negative-weight cycle"
4  else for each vertex v ∈ G'.V
5           set h(v) to the value of δ(s, v)
               computed by the Bellman-Ford algorithm
6       for each edge (u, v) ∈ G'.E
7           ŵ(u, v) = w(u, v) + h(u) − h(v)
8       let D = (d_uv) be a new n × n matrix
9       for each vertex u ∈ G.V
10          run DIJKSTRA(G, ŵ, u) to compute δ̂(u, v) for all v ∈ G.V
11          for each vertex v ∈ G.V
12              d_uv = δ̂(u, v) + h(v) − h(u)
13      return D

Running Time Analysis

With a binary min-heap: O(VE lg V) — still faster than Floyd-Warshall for sparse graphs.

---

Summary Comparison