如果给定一张图，现在我们要从源头计算最短路径。现在，如果一条边的权重为负，但是在到达目的地时有边到后端可以回到该边，我的意思是如果没有循环，那么我们就没有负循环。但是在维基百科中，给定的算法再次从源代码运行，因此它检测到负边权重而不是负循环。我的问题是，如何确定负循环？
问问题
24701 次
2 回答
25
负权重循环是权重总和为负数的循环。Bellman-Ford 算法以 V-1 步将正确的距离估计传播到图中的所有节点，除非存在负权重循环。如果存在负权重循环，您可以无限期地放松其节点。因此，在 V-1 步之后放松边缘的能力是对负权重循环存在的测试，如 Wikipedia 算法中所见。因此，Bellman-Ford 算法测试负权重循环。
于 2013-11-04T01:37:05.663 回答
2
您可以参考此链接来确定实际的负循环。 https://cp-algorithms.com/graph/finding-negative-cycle-in-graph.html 在算法的最后一次迭代中。我们只知道受影响的节点。由于负循环而受到影响。实际的负循环形成了 parent[parent[parent] 的无限循环。
代码的第二个循环就像从顶部扔一个弹球，一段时间后，球无限绕着一个圆形迷宫旋转。我们找到了那个圆形迷宫。
于 2020-01-02T13:04:09.660 回答