因此,如果我尝试使用 Bellman Ford 算法找到最短路径,使用此方法来测试是否存在路径:
public boolean hasPath(int v){
return distTo[v] < Double.POSITIVE_INFINITY;
}
如果我有一个负循环,那么这个算法会发生什么?它是否仍然返回 true,因为我知道 Dijkstra 的算法不适用于负循环,但 Ford 的算法呢?
最佳答案
它会起作用,但该值可能是也可能不是最短路径。真正的最短路径实际上可能是负无穷大,因为如果负圆到达目的节点,总会有比当前最短路径更短的路径。
这实际上就是您使用 Bellman-Ford 检测负圆的方式。如果在 |V| 之后循环,第 (|V|+1) 次仍然更新一些最短路径,图中有一个负圆圈。
关于java - Bellman Ford 的负循环算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36091329/