在 Floyd-Warshall 算法中构建最短路径的另一个办法是使用 φ(k)，其中 i, j, k = 1, 2, · · · , n， ij φ(k) 是从结点 i 到结点 j 的一条中间所有结点都取自集合 {1, 2, · · · , k} 的最短路径上编号最大的 ij 中间结点。请给出 φ(k) 的一个递归公式，并修改 Floyd-Warshall 过程来计算 φ(k) 的值，并重写 ij ij PRINT-ALL-PAIRS-SHORTSET-PATH 过程，使其以矩阵 Φ = (φ(k)) 作为输入。矩阵 Φ 与 15.2 ij 节所讨论的链式矩阵乘法中的表格存在何种相似点?

φ(k) 的递归公式为：

φ(i,j,k) =
if k = 0, then
if i = j, then 0
else if (i, j) ∈ E, then w(i, j)
else ∞
else
if d(i, j, k-1) ≤ d(i, φ(i, j, k-1), k-1) + d(φ(i, j, k-1), j, k-1), then φ(i, j, k-1)
else φ(i, j, k-1)

其中，d(i, j, k) 表示从结点 i 到结点 j 且所有中间结点都来自集合 {1,2,...,k} 的最短路径的长度。

Floyd-Warshall 算法可以修改为计算 φ(k) 的值。对于每个 k，需要使用动态规划的思想来计算 φ(i, j, k) 的值。具体而言，可以使用一个三维数组 phi 来保存 φ(i, j, k) 的值。初始时，phi[i][j][0] = i，phi[i][j][k] = ∞（当 k > 0）。然后，使用以下递推公式计算 phi[i][j][k] 的值：

phi[i][j][k] =
if d(i, j, k-1) ≤ d(i, phi[i][j][k-1], k-1) + d(phi[i][j][k-1], j, k-1),
then phi[i][j][k-1]
else phi[i][j][k-1]

计算出所有的 φ(i, j, k) 后，可以使用类似于 PRINT-ALL-PAIRS-SHORTSET-PATH 的方法，根据矩阵 Φ = (φ(k)) 来输出所有结点对之间的最短路径。

与链式矩阵乘法中的表格相似之处在于，都是使用动态规划的思想来计算矩阵中的值，并且都需要用到前面计算出的值。在链式矩阵乘法中，每个子问题的解决都需要用到前面的子问题的解决；而在 Floyd-Warshall 中，计算出 φ(i, j, k) 的值也需要用到前面计算出的值。