检测负权重循环的Bellman ford算法

Question

我读过贝尔曼·福特最短路径算法，它可以检测负权重循环。link

该算法运行(顶点-1)次，以避免无限循环，并成功地检测到负权重循环。这很好，但是，我的疑问是，检测负权重循环的必要性是什么？当算法运行固定次数并自行终止时？

Answer 1

如果存在负循环，则最短路径没有意义。你可以通过传递它来找到更短的路径。如果存在最短路径(没有负循环)，或者告诉你没有最短路径，那么贝尔曼福特就会给你找出最短路径。

如果没有负循环，答案将永远不会使用超过V-1个边，因此算法在V-1次迭代后不会找到任何更好的路径。然而，如果存在一个负循环，那么我们总是可以通过通过它来减少任何路径的长度，因此算法不会停止。

Answer 2

Bellman-Ford找到从一个给定顶点到图中所有其他顶点的最短路径。

如果存在负循环，则至少有一个顶点的距离与该负循环至少走过一个的路径相对应。如果您增加运行的第一次迭代不是|V|-1，而是2*(|V|-1)，则到此顶点的距离将会减少！如果增加到3*(|V|-1)，距离将再次减小！您可以无限增加迭代次数，并且到此顶点的距离将无限减少。

换句话说，算法不会收敛到最短路径。

这就是为什么您需要使用以下命令检测负循环

    for each edge (u, v) with weight w in edges:
           if distance[u] + w < distance[v]:
               error "Graph contains a negative-weight cycle"

在维基百科的案例中，它被认为是一个错误，但该算法可以用于有目的地检测负循环。