如果给定一个图，现在我们要从源头计算最短路径。现在，如果一条边具有负权重，但在到达目的地时有边到后边返回到该边，我的意思是如果没有循环，那么我们就没有负循环。但是here http://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm在维基百科中，给定的算法再次从源运行，因此它检测到负边缘权重，但不是负循环。我的问题是，如何确定负循环？
负权重循环是权重总和为负数的循环。 Bellman-Ford 算法以 V-1 步将正确的距离估计传播到图中的所有节点，除非存在负权重循环。如果存在负权重循环，您可以无限期地继续放松其节点。因此，在 V-1 步骤后松弛边缘的能力是对是否存在负权重循环的测试，如维基百科算法中所示。因此贝尔曼-福特算法测试负权重循环。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
