为什么全源最短路径算法可处理带负权重的边？

Question

最近我一直在研究诸如弗洛伊德-沃舍尔和约翰逊算法等所有对最短路径进行计算的算法，并且我注意到这些算法即使在图中存在负权重边（但不存在负权重环）时也能产生正确的解决方案。相比之下，戴克斯特拉算法（单源最短路径）不能处理负权重边。那么是什么使得所有对最短路径进行计算的算法能够处理负权重呢？

- user1696230

---

了解为什么Dijkstra算法无法处理负权重可能会很有教益：https://dev59.com/w2Ys5IYBdhLWcg3wE_3e - Thomas

Answer 1

弗洛伊德-华沙尔算法适用于具有负边权的图，因为该算法的正确性不依赖于边的权重非负，而Dijkstra算法的正确性基于这一点。

Dijkstra算法的正确性：

在算法的任何步骤中，我们有两组顶点。集合A包含我们已经计算出最短路径的顶点。集合B包含其余的顶点。

归纳假设：在每个步骤中，我们将假定所有先前的迭代都是正确的。

归纳步骤：当我们将一个顶点V添加到集合A并设置距离为dist[V]时，我们必须证明这个距离是最优的。如果这不是最优的，那么肯定存在一些其他到顶点V的路径长度更短。

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

现在，由于 dist[V] <= dist[X]，因此除非图具有负边长度，否则到达V的任何其他路径至少会有长度dist[V]。

弗洛伊德-华沙尔算法的正确性：

从顶点S到顶点T的任何路径都会通过图的任何其他顶点U。因此，可以计算从S到T的最短路径为：

min( shortest_path(S到U) + shortest_path(U到T))，其中U是图中的所有顶点。

正如您所看到的，只要子调用正确计算路径并且已正确初始化了基本情况，就不需要依赖于图的边为非负数。

- Nikunj Banka

---

你不能只是说“现在，因为dist[V] <= dist[X]”，至少不没有更详细地限定X。我认为你需要在前一句中说“假设这条其他路径通过B中的某个顶点X”，并解释为什么不必考虑X在A中的情况。 - j_random_hacker

如果路径必须经过集合A的某个顶点，则它将直接从该顶点开始。我认为这太基础了，不需要添加。但是我已经添加了“X在集合B中”。感谢指出。 - Nikunj Banka

Answer 2

Dijkstra算法不能处理负权边，因为它基于贪心策略（一种假设），即一旦将顶点v添加到集合S中，d[v]包含可能的最小距离。

但是，如果在Q中的最后一个顶点被添加到S中，并且它具有某些出边的负权重，则由负边引起的距离影响不会计入其中。

然而，所有对最短路径算法都将捕获这些更新。

- Robert.Li