> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-vi-graph-algorithms/23.-all-pairs-shortest-paths.md). # 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'\ 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)11 + (-3) - (-5)3
(2, 4)22 + (-3) - (-1)0
(3, 2)22 + 0 - (-3)5
(3, 6)-8-8 + 0 - (-8)0
(4, 1)-4-4 + (-1) - (-5)0
(4, 5)33 + (-1) - (-6)8
(5, 2)77 + (-6) - (-3)4
(6, 2)55 + (-8) - (-3)0
(6, 3)1010 + (-8) - 02
### 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).