如果我们有一个图，现在我们要从源计算最短路径。现在，如果一条边具有负权重，但是有一条边到回边可以返回到该边并到达目的地，我的意思是如果没有循环，则我们没有负循环。但是，这里 维基百科给出的算法再次从源运行，因此它检测到负边缘权重，但未检测到负循环。我的问题是，如何确定负循环？
2个回答
28
负权重环是一种总权重为负数的环。Bellman-Ford算法会在V-1次步骤中将正确的距离估计值传播到图中的所有节点，除非存在负权重环。如果有负权重环，则可以无限放松其节点。因此，在V-1步后仍能放松边缘的能力是检测负权重环存在的测试，如维基百科算法所示。因此，Bellman-Ford算法用于检测负权重环。
- James Candy
2
您可以参考以下链接来确定实际的负环。
https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html
在算法的最后一次迭代中，我们只能知道受到负环影响的节点。
实际的负环形成了一个父亲[父亲[父亲]]的无限循环。
代码的第二个循环就像从顶部扔出弹球，一段时间后，球会无限绕着圆形迷宫旋转。我们找到了这个圆形迷宫。
代码的第二个循环就像从顶部扔出弹球，一段时间后，球会无限绕着圆形迷宫旋转。我们找到了这个圆形迷宫。
- siddharthabhi30
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接