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

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-1内距离的原始矩阵中的k？

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

Answer 1

您是对的，因为原始公式要求 step 的计算k需要使用 step 中的计算k-1：

如果正如您所说，第一个矩阵用于存储来自步骤的值，第二k-1个矩阵用于存储来自 的值k，第一个矩阵再次用于存储来自等的值，k+1那么可以很容易地组织起来。

但是，如果我们在更新值时使用相同的矩阵，在上面的公式中我们可能会意外地使用代替如果索引值i,k在本轮中已经更新k，或者我们可能会得到代替索引值是否k,j已更新。这会不会违反算法，因为我们使用了错误的递归更新公式？

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

现在，我们将第一个公式替换j为k：

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

所以，基本上，将具有相同的值和将具有相同的值，因此这些值在循环“k”期间是否更新并不重要，因此您可以在读取时更新相同的矩阵，而不会破坏算法。

Answer 2

你在这里部分正确。

\n\n

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

\n\n

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

\n\n

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

\n\n

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

\n