java - 带负循环的贝尔曼福特算法

Question

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

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

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

Answer 1

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

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