23. All-Pairs Shortest Paths

Exercises

23.1-1

Each iteration of Slow-APSP produces the following matrices:

1. $L^{(1)} = \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ 1 & 0 & \infty & 2 & \infty & \infty \\ \infty & 2 & 0 & \infty & \infty & -8 \\ -4 & \infty & \infty & 0 & 3 & \infty \\ \infty & 7 & \infty & \infty & 0 & \infty \\ \infty & 5 & 10 & \infty & \infty & 0 \end{pmatrix}$

2. $L^{(2)} = \begin{pmatrix} 0 & 6 & \infty & \infty & -1 & \infty \\ -2 & 0 & \infty & 2 & 0 & \infty \\ 3 & -3 & 0 & 4 & \infty & -8 \\ -4 & 10 & \infty & 0 & -5 & \infty \\ 8 & 7 & \infty & 9 & 0 & \infty \\ 6 & 5 & 10 & 7 & \infty & 0 \end{pmatrix}$

3. $L^{(3)} = \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -2 & -3 & 0 & -1 & 2 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 5 & 0 \end{pmatrix}$

4. $L^{(4)} = \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -3 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix}$

5. $L^{(5)} = \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -6 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix}$

The Faster-APSP algorithm achieves the same result more efficiently by repeatedly squaring the matrices:

1. $L^{(2)} = L^{(1)} \cdot L^{(1)}$

2. $L^{(4)} = L^{(2)} \cdot L^{(2)}$

3. $L^{(8)} = L^{(4)} \cdot L^{(4)}=L^{(5)}$ by equation (23.4)

23.1-2

Available in the latest revision of the IM.

23.1-3

Available in the latest revision of the IM.

23.1-4

Available in the latest revision of the IM.

23.1-5

Available in the latest revision of the IM.

23.1-6

Slow-APSP still works correctly, although not producing the same intermediary matrices as the original variant (it "converges" faster). The core insight is that $l_{ij}^{(r-1)}+w_{jj}=l_{ij}^{(r-1)}$ represents the "old" value at the start of the procedure. Obviously, $l_{ij}^{(r)} \le l_{ij}^{(r-1)}$ (this is how Relax behaves), so initially "setting" $l_{ij}^{(r)} = l_{ij}^{(r-1)}$ is safe. During the updates of some row $i$ (rows are independent of each other) it could happen that $l_{ij}$ uses an already updated value $l_{ij'}$ where $j'<j$. But this doesn't cause any issue at the end, just that some temporary values may be fast forwarded in time.

Faster-APSP doesn't need the matrix $M$ neither. For the same reason as above, relying on the Relax feature, it can only converge faster.

The Extend-Shortest-Paths procedure operates within a mathematical structure often called a min-plus algebra (or tropical semiring). Because the operations are associative (see Exercise 23.1-4) and bounded by the true shortest-path weights, any sequence of valid edge relaxations that covers the graph will reach the correct answer. The in-place "fast-forwarding" is simply a mathematically valid, albeit less uniform, traversal of these associative path groupings.

See also Exercise 23.2-4.

23.1-7

Available in the latest revision of the IM.

23.1-8

Available in the latest revision of the IM.

23.1-9

Available in the latest revision of the IM.

23.1-10

Available in the latest revision of the IM.

23.2-1

• $D^{(0)} = \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ 1 & 0 & \infty & 2 & \infty & \infty \\ \infty & 2 & 0 & \infty & \infty & -8 \\ -4 & \infty & \infty & 0 & 3 & \infty \\ \infty & 7 & \infty & \infty & 0 & \infty \\ \infty & 5 & 10 & \infty & \infty & 0 \end{pmatrix}$

• $D^{(1)} = \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ 1 & 0 & \infty & 2 & 0 & \infty \\ \infty & 2 & 0 & \infty & \infty & -8 \\ -4 & \infty & \infty & 0 & -5 & \infty \\ \infty & 7 & \infty & \infty & 0 & \infty \\ \infty & 5 & 10 & \infty & \infty & 0 \end{pmatrix}$

• $D^{(2)} = \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ 1 & 0 & \infty & 2 & 0 & \infty \\ 3 & 2 & 0 & 4 & 2 & -8 \\ -4 & \infty & \infty & 0 & -5 & \infty \\ 8 & 7 & \infty & 9 & 0 & \infty \\ 6 & 5 & 10 & 7 & 5 & 0 \end{pmatrix}$

• $D^{(3)} = \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ 1 & 0 & \infty & 2 & 0 & \infty \\ 3 & 2 & 0 & 4 & 2 & -8 \\ -4 & \infty & \infty & 0 & -5 & \infty \\ 8 & 7 & \infty & 9 & 0 & \infty \\ 6 & 5 & 10 & 7 & 5 & 0 \end{pmatrix}$

• $D^{(4)} = \begin{pmatrix} 0 & \infty & \infty & \infty & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ 0 & 2 & 0 & 4 & -1 & -8 \\ -4 & \infty & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix}$

• $D^{(5)} = \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ 0 & 2 & 0 & 4 & -1 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix}$

• $D^{(6)} = \begin{pmatrix} 0 & 6 & \infty & 8 & -1 & \infty \\ -2 & 0 & \infty & 2 & -3 & \infty \\ -5 & -3 & 0 & -1 & -6 & -8 \\ -4 & 2 & \infty & 0 & -5 & \infty \\ 5 & 7 & \infty & 9 & 0 & \infty \\ 3 & 5 & 10 & 7 & 2 & 0 \end{pmatrix}$

23.2-2

Available in the latest revision of the IM.

23.2-3

FLOYD-WARSHALL-WITH-PI(W, n)
1  let D^(0) = (d_ij^(0)) and Pi^(0) = (pi_ij^(0)) be new n x n matrices
2  D^(0) = W
3  // Initialize the Pi^(0) matrix according to equation (23.7)
4  for i = 1 to n
5      for j = 1 to n
6          if i == j or w_ij == \infty
7              pi_ij^(0) = NIL
8          else
9              pi_ij^(0) = i
10 // Iteratively update D^(k) and Pi^(k)
11 for k = 1 to n
12     let D^(k) = (d_ij^(k)) and Pi^(k) = (pi_ij^(k)) be new n x n matrices
13     for i = 1 to n
14         for j = 1 to n
15             // Update condition according to equation (23.8)
16             if d_ij^(k-1) > d_ik^(k-1) + d_kj^(k-1)
17                 d_ij^(k) = d_ik^(k-1) + d_kj^(k-1)
18                 pi_ij^(k) = pi_kj^(k-1)
19             else
20                 d_ij^(k) = d_ij^(k-1)
21                 pi_ij^(k) = pi_ij^(k-1)
22 return D^(n), Pi^(n)

We first prove the hint $\pi_{ij}^{(k)} = l \implies d_{ij}^{(k)} \ge d_{il}^{(k)} + w_{lj}$ by induction on $k$.

• Base Case ($k=0$): If $\pi_{ij}^{(0)} = l$, equation (23.7) implies that $l = i$, $i \neq j$, and $w_{ij} < \infty$. Substituting $l$ with $i$, the inequality becomes $d_{ij}^{(0)} \ge d_{ii}^{(0)} + w_{ij}$, which is trivially true.

• Inductive Step: Assume the claim holds for $k-1$. If $\pi_{ij}^{(k)} = l$, equation (23.8) dictates two possible cases:

  1. $k$ is not an intermediate vertex: Here, $\pi_{ij}^{(k)} = \pi_{ij}^{(k-1)} = l$ and $d_{ij}^{(k)} = d_{ij}^{(k-1)}$. By the inductive hypothesis, $d_{ij}^{(k-1)} \ge d_{il}^{(k-1)} + w_{lj}$. Because shortest-path distances never increase as $k$ grows, $d_{il}^{(k-1)} \ge d_{il}^{(k)}$. Therefore, $d_{ij}^{(k)} = d_{ij}^{(k-1)} \ge d_{il}^{(k-1)} + w_{lj} \ge d_{il}^{(k)} + w_{lj}$.

  2. $k$ is an intermediate vertex: Here, $\pi_{ij}^{(k)} = \pi_{kj}^{(k-1)} = l$ and $d_{ij}^{(k)} = d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$. Applying the inductive hypothesis to the subpath from $k$ to $j$ gives $d_{kj}^{(k-1)} \ge d_{kl}^{(k-1)} + w_{lj}$. Substituting this into the $d_{ij}^{(k)}$ equation yields $d_{ij}^{(k)} \ge d_{ik}^{(k-1)} + d_{kl}^{(k-1)} + w_{lj}$. We know that $d_{il}^{(k)} = \min(d_{il}^{(k-1)}, d_{ik}^{(k-1)} + d_{kl}^{(k-1)})$, which means $d_{il}^{(k)} \le d_{ik}^{(k-1)} + d_{kl}^{(k-1)}$. Therefore, $d_{ij}^{(k)} \ge d_{il}^{(k)} + w_{lj}$.

The inequality holds for both cases, completing the induction.

Assume for contradiction that $G_{\pi, i}$ contains a cycle $c = \langle v_0, v_1, \dots, v_p \rangle$ where $v_0 = v_p$. For every edge $(v_{m-1}, v_m)$ in this cycle, the predecessor of $v_m$ is $v_{m-1}$, meaning $\pi_{i, v_m}^{(n)} = v_{m-1}$. Applying our previously proven inequality with $j = v_m$ and $l = v_{m-1}$ yields:

$$d_{i, v_m}^{(n)} \ge d_{i, v_{m-1}}^{(n)} + w(v_{m-1}, v_m).$$

Summing this inequality for all edges around the cycle $c$:

$$\sum_{m=1}^p d_{i, v_m}^{(n)} \ge \sum_{m=1}^p d_{i, v_{m-1}}^{(n)} + \sum_{m=1}^p w(v_{m-1}, v_m).$$

Because $v_0 = v_p$, the sum of the distances on the left side is identical to the sum of the distances on the right side. Assuming the graph contains no negative-weight cycles, these distances are finite. Subtracting them from both sides gives:

$$0 \ge \sum_{m=1}^p w(v_{m-1}, v_m) = w(c).$$

Thus, $w(c)$ would have to be exactly 0. However, the strict inequality condition $d_{ij}^{(k-1)} > d_{ik}^{(k-1)} + d_{kj}^{(k-1)}$ guarantees that predecessor pointers are only updated when a strictly shorter path is found. A 0-weight cycle offers no strict improvement, meaning the algorithm will not alter pointers to form one. Therefore, $G_{\pi, i}$ cannot contain any cycles and is acyclic.

Because $G_{\pi, i}$ is a connected, acyclic subgraph where every reachable vertex has exactly one predecessor leading back to $i$, it forms a tree rooted at $i$. Since the distances correspond to the proven final shortest paths calculated by Floyd-Warshall, it is indeed a shortest-paths tree.

23.2-4

Available in the latest revision of the IM.

23.2-5

Available in the latest revision of the IM.

23.2-6

Available in the latest revision of the IM.

23.2-7

The recurrence formula is

$$\phi_{ij}^{(k)} = \begin{cases} \text{NIL} & \text{if } k = 0 \\ k & \text{if } k \ge 1 \text{ and } d_{ij}^{(k-1)} > d_{ik}^{(k-1)} + d_{kj}^{(k-1)} \\ \phi_{ij}^{(k-1)} & \text{otherwise}\end{cases}$$

MODIFIED-FLOYD-WARSHALL(W, n)
1  let D^(0) = W
2  let Phi^(0) be a new n x n matrix initialized to NIL
3  for k = 1 to n
4      let D^(k) and Phi^(k) be new n x n matrices
5      for i = 1 to n
6          for j = 1 to n
7              if d_ij^(k-1) > d_ik^(k-1) + d_kj^(k-1)
8                  d_ij^(k) = d_ik^(k-1) + d_kj^(k-1)
9                  phi_ij^(k) = k
10             else
11                 d_ij^(k) = d_ij^(k-1)
12                 phi_ij^(k) = phi_ij^(k-1)
13 return D^(n), Phi^(n)

The following procedure assumes we already know a valid path exists.

PRINT-ALL-PAIRS-SHORTEST-PATH(Phi, i, j)
1  print i
2  PRINT-INTERMEDIATE(Phi, i, j)
3  if i != j
4      print j

PRINT-INTERMEDIATE(Phi, i, j)
1  if Phi[i, j] == NIL
2      return
3  k = Phi[i, j]
4  PRINT-INTERMEDIATE(Phi, i, k)
5  print k
6  PRINT-INTERMEDIATE(Phi, k, j)

The $\Phi$ matrix is conceptually identical to the $s$ table used in the matrix-chain multiplication algorithm:

• Optimal Splitting: In matrix-chain multiplication, the $s[i, j]$ table stores the optimal index $k$ used to split the product sequence $A_i \dots A_j$ into two smaller halves.

• Divide and Conquer: Similarly, the $\Phi[i, j]$ matrix stores the optimal vertex $k$, or NIL, that strictly splits the shortest path from $i$ to $j$ into two optimal subpaths: $i \leadsto k$ and $k \leadsto j$. Both tables act as blueprints for reconstructing a solution recursively from the top down.

23.2-8

Available in the latest revision of the IM.

23.2-9

Available in the latest revision of the IM.

23.3-1

$(u,v)$	$w(u,v)$	$w(u,v)+h(u)−h(v)$	$\hat w(u,v)$
$(1, 5)$	$-1$	$-1 + (-5) - (-6)$	$0$
$(2, 1)$	$1$	$1 + (-3) - (-5)$	$3$
$(2, 4)$	$2$	$2 + (-3) - (-1)$	$0$
$(3, 2)$	$2$	$2 + 0 - (-3)$	$5$
$(3, 6)$	$-8$	$-8 + 0 - (-8)$	$0$
$(4, 1)$	$-4$	$-4 + (-1) - (-5)$	$0$
$(4, 5)$	$3$	$3 + (-1) - (-6)$	$8$
$(5, 2)$	$7$	$7 + (-6) - (-3)$	$4$
$(6, 2)$	$5$	$5 + (-8) - (-3)$	$0$
$(6, 3)$	$10$	$10 + (-8) - 0$	$2$

23.3-2

Available in the latest revision of the IM.

23.3-3

Available in the latest revision of the IM.

23.3-4

Available in the latest revision of the IM.

23.3-5

Available in the latest revision of the IM.

23.3-6

Available in the latest revision of the IM.

Problems

23-1 Transitive closure of a dynamic graph

Available in the latest revision of the IM.

23-2 Shortest paths in ϵ-dense graphs

a.

A $d$-ary min-heap containing $n$ elements has a height of $\Theta(\log_d n)$:

• INSERT: Adding an element at the bottom and bubbling it up takes time proportional to the height of the tree. The running time is $O(\log_d n)$.

• EXTRACT-MIN: Removing the root, replacing it with the last leaf, and trickling it down requires comparing up to $d$ children at each level to find the minimum. Over the height of the tree, this yields a running time of $O(d \log_d n)$.

• DECREASE-KEY: Decreasing a key's value and bubbling it up towards the root takes time proportional to the height. The running time is $O(\log_d n)$.

The running times when $d = \Theta(n^\alpha)$ for a constant $0 < \alpha \le 1$ are based on the next observation:

$$\log_d n = \frac{\lg n}{\lg(n^\alpha)} = \frac{\lg n}{\alpha \lg n} = \frac{1}{\alpha} = O(1).$$

Applying this constant height to the standard operations:

• INSERT: $O(1)$

• EXTRACT-MIN: $O(n^\alpha \cdot 1) = O(n^\alpha)$

• DECREASE-KEY: $O(1)$

A Fibonacci heap has amortized running times of $O(1)$ for INSERT, $O(1)$ for DECREASE-KEY, and $O(\log n)=o(n^\alpha)$ for EXTRACT-MIN.

b.

Run Dijkstra's algorithm using a $d$-ary min-heap where $d = \vert{}V\vert{}^\epsilon$:

• Each of the $\vert{}E\vert{}$ DECREASE-KEY operations takes $O(1)$ time. The total time for all DECREASE-KEY operations is $O(E)$.

• Each of the $\vert{}V\vert{}$ EXTRACT-MIN operations takes $O(d \log_d \vert{}V\vert{})=O(\vert{}V\vert{}^\epsilon)$ time. The total time for all EXTRACT-MIN operations is $O(\vert{}V\vert{}^{1+\epsilon})=O(E)$.

Summing the costs of both primary operations yields a final asymptotic running time of $O(E)$.

c.

Run the algorithm of part (b) from each vertex resulting in $O(VE)$ total time.

d.

Apply the idea from Johnson’s algorithm for sparse graphs by first reweighting the edges and then running part (c).