如果我们得到一个图表,现在从源头我们将计算最短路径.现在,如果边缘具有负权重,但是在到达目的地时有边缘到边缘以回到该边缘,我的意思是如果没有循环,那么我们没有负循环.但这里在维基百科上,从源运行给定的算法,从而再次检测到下降沿的重量,但不是消极的循环.我的问题是,如何确定负循环？
小智 22
负权重周期是权重总和为负数的周期.Bellman-Ford算法以V-1步长向图中的所有节点传播正确的距离估计,除非存在负权重周期.如果负重周期,您可以无限期地放松其节点.因此,如在维基百科算法中所见,在V-1步骤之后放松边缘的能力是对负权重循环的存在的测试.所以Bellman-Ford算法测试负重量周期.