c++ - 为什么弗洛伊德战争只使用一个距离矩阵？

Question

我阅读了 floyd warshall 算法的伪代码， 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each vertex v 3 dist[v][v] ← 0 4 for each edge (u,v) 5 dist[u][v] ← w(u,v) // the weight of the edge (u,v) 6 for k from 1 to |V| 7 for i from 1 to |V| 8 for j from 1 to |V| 9 if dist[i][j] > dist[i][k] + dist[k][j] 10 dist[i][j] ← dist[i][k] + dist[k][j] 11 end if 但它只使用一个 dist 矩阵来节省距离。我认为应该有 n 个 dist 矩阵，其中 n 是顶点的数量，或者至少我们需要两个 dist 矩阵。一个将当前的最短路径存储在顶点 k-1 内，另一个存储在顶点 k 内的最短路径，然后第一个存储在 k+1 内的最短路径，.... 我们如何才能将新的最短路径距离存储在顶点内k 在原始矩阵中的顶点 k-1 内的距离？

这张图片显示我们需要 D0, D1, D2....D(n)

Answer 1

从某种意义上说，您是对的，原始公式要求 step 的计算k需要使用 step 的计算k-1：

正如您所说，如果第一个矩阵用于存储来自步骤的值，则可以轻松组织第二k-1个矩阵用于存储来自的值，第一个矩阵k再次用于存储来自k+1等的值。

但是，如果我们在更新值时使用相同的矩阵，在上面的公式中，我们可能会不小心使用if value for index i,khas been updated during current round来代替k，或者我们可能会 get而不是if value for indexk,j已经更新。这会不会违反算法，因为我们使用了错误的递归更新公式？

嗯，不是真的。请记住，Floyd-Warshall 算法处理“无负循环”约束，这意味着不存在边缘总和为负值的循环。这意味着对于任何k从节点k到节点的最短路径k是0（否则这将意味着存在一条从k到的路径，k其边的总和为负值）。所以根据定义：

现在，让我们采用第一个公式并替换j为k：

然后让我们将同一个公式中的“i”替换为“k”：

因此，基本上，将具有与 相同的值，并且具有与 相同的值，因此这些值是否在周期“k”期间更新并不重要，因此您可以在读取时更新相同的矩阵而无需打破算法。

Answer 2

你在这里是部分正确的。

Floyd Warshall 算法的输出（即 NxN 矩阵）无助于重建任意两个给定顶点之间的实际最短路径。

如果我们保留一个父矩阵 P，则可以恢复这些路径，以便它存储用于每个顶点对 (x, y) 的最后一个中间顶点。假设这个值为 k。

从 x 到 y 的最短路径是从 x 到 k 的最短路径与从 k 到 y 的最短路径的串联，可以在给定矩阵 P 的情况下递归地重构。

但是请注意，大多数全对应用程序只需要得到的距离矩阵。这些工作正是 Floyd 算法的设计目的。