对最短路径算法使用负权重？

2018-06-12 07:24:38

我一直在研究最近的所有对最短路径算法，例如Floyd-Warshall和Johnson的算法，我注意到即使图形包含负权重边（但不是负权重循环），这些算法也会产生正确的解。为了比较，Dijkstra算法（它是单源最短路径）不适用于负权重边缘。什么使全对最短路径算法与负权重一起工作？

Floyd Warshall的所有对最短路径算法都适用于负边权重的图，因为算法的正确性不取决于边的权重是否定的，而Dijkstra算法的正确性是基于这个事实。

Dijkstra算法的正确性：

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

归纳假设 ：在每一步我们都会假设所有以前的迭代都是正确的。

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

假设这个其他路径通过集合B中的某个顶点X.

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

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

min（最短路径（S到U）+最短路径（U到T））。

正如你所看到的，只要子调用正确地计算路径，就不会依赖于图的边是非负的。只要基础案例已经正确初始化，子调用就可以正确计算路径。

Dijkstra算法不适用于负权重边缘，因为它基于贪婪策略（假设），一旦顶点v被添加到集合S中，d [v]包含可能的最小距离。

但是，如果Q中的最后一个顶点被添加到S并且它有一些输出的负权重边缘。由负边缘造成的距离影响不计算在内。

但是，所有对最短路径算法都会捕获这些更新。

链接地址: http://www.djcxy.com/p/35217.html