在 Floyd-Warshall 算法中添加边

Question

假设我们已经使用 Floyd-Warshall 算法计算了图中的所有对距离矩阵。添加新边时，我们如何有效地更新这个距离矩阵？

我们当然可以重新运行 Floyd-Warshall 算法，但这需要 O(V^3)。我们可以让它更快吗？

Answer 1

假设边从顶点 v 到顶点 w 并且成本为 c :

如果距离矩阵已经有一条从v到w的较短路径，那么添加边没有任何效果，所以没有什么可做的。

否则，新边成为从v到w的最短路径，所以将其输入到距离矩阵中，然后，对于每隔一对顶点 a 和 b，看看是否可以通过使用新边使其更短。从距离矩阵可以很容易地找到 a-v-w-b 和 a-w-v-b 的成本。请注意，一个 a 或 b 可能与 v 或 w.

因为你必须检查每一对顶点，这需要 O(V²) 时间。