In the Bellman Ford's Algorithm for shortest path finding, how is the test "v.d > u.d + w(u,v)" detecting cycles of negative weight? Could someone explain it with an example?
考虑此图，其中1是启动顶点。 N-1 = 2回合边缘松弛后，每个节点的最短距离为[0，-1，-2]。如果该图不包含负周期，则必须完成最短的距离，因为没有长度＆gt; = n 的最短路径。但是，考虑重量-1的边缘（3,1）。即使在2轮放松之后，我们也可以再放松这个边缘。这意味着有最短的路径，长度 n 。这意味着有一个负周期。
Consider this graph where 1 is the starting vertex. After n-1=2 rounds of edge relaxations, shortest distances to each node is [0,-1,-2]. If the graph does not contain negative cycles, shortest distances must be finalised as there is no shortest path with length >= n. However, consider the edge (3,1) with weight -1. We can relax this edge one more time, even after the 2 rounds of relaxation. That means there is a shortest path with length n. That means there is a negative cycle.
发布评论
评论（1）
考虑此图，其中1是启动顶点。 N-1 = 2回合边缘松弛后，每个节点的最短距离为[0，-1，-2]。如果该图不包含负周期，则必须完成最短的距离，因为没有长度＆gt; =
n的最短路径。但是，考虑重量-1的边缘（3,1）。即使在2轮放松之后，我们也可以再放松这个边缘。这意味着有最短的路径，长度n。这意味着有一个负周期。Consider this graph where 1 is the starting vertex. After n-1=2 rounds of edge relaxations, shortest distances to each node is [0,-1,-2]. If the graph does not contain negative cycles, shortest distances must be finalised as there is no shortest path with length >=
n. However, consider the edge (3,1) with weight -1. We can relax this edge one more time, even after the 2 rounds of relaxation. That means there is a shortest path with lengthn. That means there is a negative cycle.