Bellman–Ford algorithm finds shortest path from the source vertex to all vertices in the graph.
The graph can contain negative-weight edges, but it should not contain a negative-weight cycle that is reachable from the source vertex.
The algorithm returns TRUE if there is no negative-weight cycle and FALSE if there is a negative-weight cycle reachable from the source vertex.
If there is a negative-weight cycle that is reachable from source vertex, then no solution exists.
In fig. (a) there is no negative-weight cycle, so Bellman Ford algorithm finds the shortest path from source .
if fig. (a) is in a graph whereas fig. (b) contains a negative-weight cycle therefore no solution exists.
In fig. (a) the graph is in inital configuration. All vertices were at distance infinity from source vertex a. Then vertices b and c are reached and their distance from vertex a is updated.
In fig. (d) the sum of distance of path a -> b -> d is 2 + 5 = 7 whereas sum of distance of path a -> c -> d is 7 + (-3) = 4. Hence path a -> c -> d is preferred which is shown in red line. In fig. (e) red line shows shortest path from a to e
0 Comments