25.2 The FloydWarshall algorithm
25.21
Run the FloydWarshall algorithm on the weighted, directed graph of Figure 25.2. Show the matrix $D^{(k)}$ that results for each iteration of the outer loop.
$k = 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} $$
$k = 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} $$
$k = 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} $$
$k = 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} $$
$k = 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} $$
$k = 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} $$
25.22
Show how to compute the transitive closure using the technique of Section 25.1.
We set $w_{ij} = 1$ if $(i, j)$ is an edge, and $w_{ij} = 0$ otherwise. Then we replace line 7 of $\text{EXTENDSHORTESTPATHS}(L, W)$ by $l''_{ij} = l''_{ij} \lor (l_{ik} \land w_{kj})$. Then run the $\text{SLOWALLPAIRSSHORTESTPATHS}$ algorithm.
25.23
Modify the $\text{FLOYDWARSHALL}$ procedure to compute the $\prod^{(k)}$ matrices according to equations $\text{(25.6)}$ and $\text{(25.7)}$. Prove rigorously that for all $i \in V$, the predecessor subgraph $G_{\pi, i}$ is a shortestpaths tree with root $i$. ($\textit{Hint:}$ To show that $G_{\pi, i}$ is acyclic, first show that $\pi_{ij}^{(k)} = l$ implies $d_{ij}^{(k)} \ge d_{il}^{(k)} + w_{lj}$, according to the definition of $\pi_{ij}^{(k)}$. Then, adapt the proof of Lemma 23.16.)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19  MODFLOYDWARSHALL(W) n = W.rows D(0) = W let π(0) be a new n × n matrix for i = 1 to n for j = 1 to n if i != j and D[i, j](0) < ∞ π[i, j](0) = i for k = 1 to n let D(k) be a new n × n matrix let π(k) be a new n × n matrix for i = 1 to n for j = 1 to n if d[i, j](k  1) ≤ d[i, k](k  1) + d[k, j](k  1) d[i, j](k) = d[i, j](k  1) π[i, j](k) = π[i, j](k  1) else d[i, j](k) = d[i, k](k  1) + d[k, j](k  1) π[i, j](k) = π[k, j](k  1) 
In order to have that $\pi^{(k)}_{ij} = l$, we need that $d^{(k)}_{ij} \ge d^{(k)}_{il} + w_{lj}$. To see this fact, we will note that having $\pi^{(k)}_{ij} = l$ means that a shortest path from $i$ to $j$ last goes through $l$. A path that last goes through $l$ corresponds to taking a chepest path from $i$ to $l$ and then following the single edge from $l$ to $j$. However, This means that $d_{il} \le d_{ij}  w_{ij}$, which we can rearrange to get the desired inequality. We can just continue following this inequality around, and if we ever get some cycle, $i_1, i_2, \ldots, i_c$, then we would have that $d_{ii_1} \le d_{ii_1} + w_{i_1i_2} + w_{i_2i_3} + \cdots + w_{i_ci_1}$. So, if we subtract the common term sfrom both sides, we get that $0 \le w_{i_ci_1} + \sum_{q = 1}^{c  1} w_{i_qi_{q + 1}}$. So, we have that we would only have a cycle in the precedessor graph if we ahvt that there is a zero weight cycle in the original graph. However, we would never have to go around the weight zero cycle since the constructed path of shortest weight favors ones with a fewer number of edges because of the way that we handle the equality case in equation $\text{(25.7)}$.
25.24
As it appears above, the FloydWarshall algorithm requires $\Theta(n^3)$ space, since we compute $d_{ij}^{(k)}$ for $i, j, k = 1, 2, \ldots, n$. Show that the following procedure, which simply drops all the superscripts, is correct, and thus only $\Theta(n^2)$ space is required.
1 2 3 4 5 6 7 8 FLOYDWARSHALL'(W) n = W.rows D = W for k = 1 to n for i = 1 to n for j = 1 to n d[i, j] = min(d[i, j], d[i, k] + d[k, j]) return D
With the superscripts, the computation is $d_{ij}^{(k)} = \min(d_{ij}^{(k  1)}, d_{ik}^{(k  1)} + d_{kj}^{(k  1)})$. If, having dropped the superscripts, we were to compute and store $d_{ik}$ or $d_{kj}$ before using these values to compute $d_{ij}$, we might be computing one of the following:
$$ \begin{aligned} d_{ij}^{(k)} & = \min(d_{ij}^{(k  1)}, d_{ik}^{(k)} + d_{kj}^{(k  1)}), \\ d_{ij}^{(k)} & = \min(d_{ij}^{(k  1)}, d_{ik}^{(k  1)} + d_{kj}^{(k)}), \\ d_{ij}^{(k)} & = \min(d_{ij}^{(k  1)}, d_{ik}^{(k)} + d_{kj}^{(k)}), \end{aligned} $$
In any of these scenarios, we're computing the weight of a shortest path from $i$ to $j$ with all intermediate vertices in $\{1, 2, \ldots, k\}$. If we use $d_{ik}^{(k)}$, rather than $d_{ik}^{(k  1)}$, in the computation, then we're using a subpath from $i$ to $k$ with all intermediate vertices in $\{1, 2, \ldots, k\}$. But $k$ cannot be an intermediate vertex on a shortest path from $i$ to $k$, since otherwise there would be a cycle on this shortest path. Thus, $d_{ik}^{(k)} = d_{ik}^{(k  1)}$. A similar argument applies to show that $d_{kj}^{(k)} = d_{kj}^{(k  1)}$. Hence, we can drop the superscripts in the computation.
25.25
Suppose that we modify the way in which equation $\text{(25.7)}$ handles equality:
$$ \pi_{ij}^{(k)} = \begin{cases} \pi_{ij}^{(k  1)} & \text{ if } d_{ij}^{(k  1)} < d_{ik}^{(k  1)} + d_{kj}^{(k  1)}, \\ \pi_{kj}^{(k  1)} & \text{ if } d_{ij}^{(k  1)} \ge d_{ik}^{(k  1)} + d_{kj}^{(k  1)}. \end{cases} $$
Is this alternative definition of the predecessor matrix $\prod$ correct?
If we change the way that we handle the equality case, we will still be generating a the correct values for the $\pi$ matrix. This is because updating the $\pi$ values to make paths that are longer but still tied for the lowest weight. Making $\pi_{ij} = \pi_{kj}$ means that we are making the shortest path from $i$ to $j$ passes through $k$ at some point. This has the same cost as just going from $i$ to $j$, since $d_{ij} = d_{ik} + d_{kj}$.
25.26
How can we use the output of the FloydWarshall algorithm to detect the presence of a negativeweight cycle?
Here are two ways to detect negativeweight cycles:

Check the maindiagonal entries of the result matrix for a negative value. There is a negative weight cycle if and only if $d_{ii}^{(n)} < 0$ for some vertex $i$:
 $d_{ii}^{(n)}$ is a path weight from $i$ to itself; so if it is negative, there is a path from $i$ to itself (i.e., a cycle), with negative weight.

If there is a negativeweight cycle, consider the one with the fewest vertices.
 If it has just one vertex, then some $w_{ii} < 0$, so $d_{ii}$ starts out negative, and since $d$ values are never increased, it is also negative when the algorithm terminates.
 If it has at least two vertices, let $k$ be the highestnumbered vertex in the cycle, and let $i$ be some other vertex in the cycle. $d_{ik}^{(k  1)}$ and $d_{ki}^{(k  1)}$ have correct shortestpath weights, because they are not based on negativeweight cycles. (Neither $d_{ik}^{(k  1)}$ nor $d_{ki}^{(k  1)}$ can include $k$ as an intermediate vertex, and $i$ and $k$ are on the negativeweight cycle with the fewest vertices.) Since $i \leadsto k \leadsto i$ is a negativeweight cycle, the sum of those two weights is negative, so $d_{ii}^{(k)}$ will be set to a negative value. Since $d$ values are never increased, it is also negative when the algorithm terminates.
In fact, it suffices to check whether $d_{ii}^{(n  1)} < 0$ for some vertex $i$. Here's why. A negativeweight cycle containing vertex $i$ either contains vertex $n$ or it does not. If it does not, then clearly $d_{ii}^{(n  1)} < 0$. If the negativeweight cycle contains vertex $n$, then consider $d_{nn}^{(n  1)}$. This value must be negative, since the cycle, starting and ending at vertex $n$, does not include vertex $n$ as an intermediate vertex.

Alternatively, one could just run the normal $\text{FLOYDWARSHALL}$ algorithm one extra iteration to see if any of the $d$ values change. If there are negative cycles, then some shortestpath cost will be cheaper. If there are no such cycles, then no $d$ values will change because the algorithm gives the correct shortest paths.
25.27
Another way to reconstruct shortest paths in the FloydWarshall algorithm uses values $\phi_{ij}^{(k)}$ for $i, j, k = 1, 2, \ldots, n$, where $\phi_{ij}^{(k)}$ is the highestnumbered intermediate vertex of a shortest path from $i$ to $j$ in which all intermediate vertices are in the set $\{1, 2, \ldots, k \}$. Give a recursive formulation for $\phi_{ij}^{(k)}$, modify the $\text{FLOYDWARSHALL}$ procedure to compute the $\phi_{ij}^{(k)}$ values, and rewrite the $\text{PRINTALLPAIRSSHORTESTPATH}$ procedure to take the matrix $\Phi = \big(\phi_{ij}^{(n)}\big)$ as an input. How is the matrix $\Phi$ like the $s$ table in the matrixchain multiplication problem of Section 15.2?
We can recursively compute the values of $\phi_{ij}^{(k)}$ by, letting it be $\phi_{ij}^{(k  1)}$ if $d_{ik}^{(k)} + d_{kj}^{(k)} \ge d_{ij}^{(k  1)}$, and otherwise, let it be $k$. This works correctly because it perfectly captures whether we decided to use vertex $k$ when we were repeatedly allowing ourselves use of each vertex one at a time. To modify FloydWarshall to compute this, we would just need to stick within the innermost for loop, something that computes $\phi(k)$ by this recursive rule, this would only be a constant amount of work in this innermost for loop, and so would not cause the asymptotic runtime to increase. It is similar to the s table in matrixchain multiplication because it is computed by a similar recurrence.
If we already have the $n^3$ values in $\phi_{ij}^{(k)}$ provided, then we can reconstruct the shortest path from $i$ to $j$ because we know that the largest vertex in the path from $i$ to $j$ is $\phi_{ij}^{(n)}$, call it $a_1$. Then, we know that the largest vertex in the path before $a_1$ will be $\phi_{ia_1}^{(a_1  1)}$ and the largest after $a_1$ will be $\phi_{a_1j}^{(a_1  1)}$. By continuing to recurse until we get that the largest element showing up at some point is $\text{NIL}$, we will be able to continue subdividing the path until it is entirely constructed.
25.28
Give an $O(VE)$time algorithm for computing the transitive closure of a directed graph $G = (V, E)$.
Create an $n$ by $n$ matrix $A$ filled with $0$'s. We are done if we can determine the vertices reachable from a particular vertex in $O(E)$ time, since we can just compute this for each $v \in V$. To do this, assign each edge weight $1$. Then we have $\delta(v, u) \le E$ for all $u \in V$. By Problem 244(a) we can compute $\delta(v, u)$ in $O(E)$ forall $u \in V$. If $\delta(v, u) < \infty$, set $A_{ij} = 1$. Otherwise, leave it as $0$.
25.29
Suppose that we can compute the transitive closure of a directed acyclic graph in $f(V, E)$ time, where $f$ is a monotonically increasing function of $V$ and $E$. Show that the time to compute the transitive closure $G^* = (V, E^*)$ of a general directed graph $G = (V, E)$ is then $f(V, E) + O(V + E^*)$.
First, compute the strongly connected components of the directed graph, and look at it's component graph. This component graph is going to be acyclic and have at most as many vertices and at most as many edges as the original graph. Since it is acyclic, we can run our transitive closure algorithm on it. Then, for every edge $(S_1, S_2)$ that shows up in the transitive closure of the component graph, we add an edge from each vertex in $S_1$ to a vertex in $S_2$. This takes time equal to $O(V + E')$. So, the total time required is $\le f(V, E) + O(V + E)$.