4 algorithm graph shortest-path
我最近一直在研究全对最短路径算法,例如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的最短路径可以计算为
对于图中的所有顶点U,min(shortest_path(S到U)+ shortest_path(U到T)).
正如您所看到的,只要子调用正确地计算路径,就不会将图的边缘依赖为非负的.只要基本案例已正确初始化,子调用就会正确计算路径.