我最近一直在研究全对最短路径算法，如 Floyd-Warshall 和 Johnson 算法，我注意到即使图形包含负权重边缘（但不是负权重循环），这些算法也能产生正确的解决方案。相比之下，Dijkstra 算法（单源最短路径）不适用于负权重边。是什么让全对最短路径算法适用于负权重？
Floyd Warshall的全对最短路径算法适用于具有负边权重的图形，因为算法的正确性不依赖于边的权重是非负的，而Dijkstra算法的正确性是基于这一事实。
Dijkstra算法的正确性：
我们在算法的任何一步都有 2 组顶点。集合 A 由我们计算出最短路径的顶点组成。集合 B 由剩余的顶点组成。
归纳假设：在每一步中，我们假设所有先前的迭代都是正确的。
归纳步长：当我们向集合 A 添加一个顶点 V 并将距离设置为 dist[V] 时，我们必须证明这个距离是最优的。如果这不是最佳的，那么一定有其他一些长度较短的顶点 V 的路径。
假设这条其他路径穿过集合 B 中的某个顶点 X。
现在，由于dist[V] <= dist[X]，因此任何其他通往 V 的路径将至少是 dist[V] 长度，除非图具有负边长度。
弗洛伊德·沃歇尔算法的正确性：从顶点 S 到顶点 T 的任何路径都将经过图的任何其他顶点 U。因此，从 S 到 T 的最短路径可以计算为
min（ shortest_path（S to U） + shortest_path（U to T）） 表示图形中的所有顶点 U。
如您所见，只要 sub 调用正确计算路径，就不依赖于图形的边缘是非负的。只要基本情况已正确初始化，子调用就会正确计算路径。
Dijkstra 算法不适用于负权重边，因为它基于贪婪策略（假设），一旦将顶点 v 添加到集合 S，d[v] 就包含可能的最小距离。
但是，如果将 Q 中的最后一个顶点添加到 S 中，并且它具有一些传出的负权重边。负边对距离的影响不计算在内。
但是，所有对最短路径算法都将捕获这些更新。