retagged by
323 views

1 Answer

0 votes
0 votes
v.d > u.d + w(u,v) condition ensures there is no v.d left still needed to Relax ( v.d = u.d + w(u,d)) . If condition evaluated to be true suggests we have not yet relaxed all the edges which in turn suggests the presence of negative edge cycle.

If we change condition as v.d >= u.d + w(u,v). We declare unsuccessful relaxation of edges which in turn means presence of negative edge cycle just because graph contains the edge of the form (u,v) such that u-v = 1, when the graph doesn't have negative weight cycle in real though have negative weight edge.

Related questions

1 votes
1 votes
1 answer
1
Jithin Jayan asked Jul 23, 2016
391 views
If a graph contains a positive weight cycle reachable from source, Can we find a well defined shortest path using Dijkstra/Bellman-Ford algorithm?
1 votes
1 votes
1 answer
4