Data Structures and Algorithms Made Easy with Java : Learn Data Structure using Java in 7 Days: Data Structures and Algorithmic Puzzles for Beginners to Professional by Maurya Rahul

Author:Maurya, Rahul [Maurya, Rahul]
Language: eng
Format: epub, pdf
Publisher: UNKNOWN
Published: 2020-07-12T16:00:00+00:00

This is how the graph looks like after (V-1) = 3 iterations. It should be the result since there are 4 edges, we need at most 3 iterations to find out the shortest path. So either this is the answer, or there is a negative weight cycle in the graph. To find that, after (V-1) iterations, we do one more final iteration and if the distance continues to decrease, it means that there is definitely a negative weight cycle in the graph.

For this example: if we check 2-3 , d[2] + cost[2][3] will give us 1 which is less than d[3] . So we can conclude that there is a negative cycle in our graph.

So how do we find out the negative cycle? We do a bit modification to Bellman-Ford procedure:

Procedure NegativeCycleDetector ( Graph, source): n := number of vertices in Graph

for i from 1 to n

d [ i] := infinity

end for

d[ source] := 0

for i from 1 to n- 1

flag := false

for all edges from ( u,v) in Graph

if d[ u] + cost[ u][ v] < d[ v]

d[ v] := d[ u] + cost[ u][ v]

flag := true

end if

end for

if flag == false

break

end for

for all edges from ( u,v) in Graph

if d[ u] + cost[ u][ v] < d[ v]

Return "Negative Cycle Detected" end if

end for

Return "No Negative Cycle"

This is how we find out if there is a negative cycle in a graph. We can also modify Bellman-Ford Algorithm to keep track of negative cycles.

Section 20.3: Why do we need to relax all the edges at most (V-1) times

To understand this example, it is recommended to have a brief idea on Bellman-Ford single source shortest path algorithm which can be found here

In Bellman-Ford algorithm, to find out the shortest path, we need to relax all the edges of the graph. This process is repeated at most (V-1) times, where V is the number of vertices in the graph.

The number of iterations needed to find out the shortest path from source to all other vertices depends on the order that we select to relax the edges.

Let's take a look at an example:

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.