Bellman Ford 的负循环算法

Question

因此，如果我尝试使用 Bellman Ford 算法找到最短路径，使用此方法来测试是否存在路径：

public boolean hasPath(int v){
    return distTo[v] < Double.POSITIVE_INFINITY;
}

如果我有一个负循环那么这个算法会发生什么？它仍然 return 正确吗，因为我知道 Dijkstra 的算法不适用于负循环，但 Ford 的算法呢？

Answer 1

它会起作用，但该值可能是也可能不是最短路径。真正的最短路径实际上可能是负无穷大，因为如果负圆到达目的节点，总会有比当前最短路径更短的路径。

这实际上就是您使用 Bellman-Ford 检测负圆的方式。如果在 |V| 之后循环，第(|V|+1)次仍然更新一些最短路径，图中有一个负圆。