algorithm - 为什么全对最短路径算法使用负权重？

Question

我最近一直在研究全对最短路径算法，例如 Floyd-Warshall 和 Johnson 的算法，我注意到即使图包含负权重边(但不包含负权重循环)，这些算法也会产生正确的解决方案.作为比较，Dijkstra 算法(单源最短路径)不适用于负权重边。什么使全对最短路径算法适用于负权重？

Answer 1

Floyd Warshall 的所有对最短路径算法适用于边权为负的图，因为该算法的正确性不依赖于边权为非负，而 Dijkstra 算法的正确性基于这一事实。

Dijkstra 算法的正确性:

我们在算法的任何一步都有 2 组顶点。集合 A 由我们计算出的最短路径的顶点组成。集合 B 由剩余的顶点组成。

归纳假设:在每一步，我们都假设所有先前的迭代都是正确的。

Inductive Step:当我们在集合A中加入一个顶点V并设置距离为dist[V]时，我们必须证明这个距离是最优的。如果这不是最优的，那么必须有一些其他路径到顶点 V 的长度更短。

假设这条其他路径经过集合 B 中的某个顶点 X。

现在，自 dist[V] <= dist[X] ，因此到 V 的任何其他路径至少为 dist[V] 长度，除非图形具有负边长。

Floyd Warshall 算法的正确性:从顶点 S 到顶点 T 的任何路径都将经过图中的任何其他顶点 U。因此，从 S 到 T 的最短路径可以计算为

min( shortest_path(S to U) + shortest_path(U to T)) for all vertices U in the graph.

如您所见，只要子调用正确计算路径，就不会依赖图形的边为非负数。只要基本情况​​已正确初始化，子调用就会正确计算路径。