(12666 Views)
Bellman Ford is an algorithm used to compute single source shortest path. This means that starting from a single vertex, we compute best distance to all other vertices in a weighted graph. This is done by relaxing all the edges in the graph for n-1 times, where n is the number of vertices in the graph. Dijkstra's algorithm also achieves the same goal, but Bellman ford removes the shortcomings present in the Dijkstra's.
As stated above, Dijkstra's also achieves the same goal, but if any negative weight cycle is present, it doesn't work as required. A negative weight cycle is a loop in the graph with some negative weight attatched to an edge. sum of weights in this loop is negative. A node's value decrease once we go around this loop. A graph having negative weight cycle cannot be solved. Consider this graph, it has a negative weight cycle in it.
If we have an edge between vertices u and v (from u to v), dist[u] represents the distance of the node u, and weight[uv] represents the weight on the edge, then mathematically, edge relaxation can be written as,
If dist[u] + weight < dist[v], then
dist[v] = dist[u] + weight
Consider this graph, we're relaxing the edge.
Consider this weighted graph,
Initially we've set the distance of source as 0, and all other vertices are at +Infinity distance from the source. We will now relax all the edges for n-1 times. Here n = 7, so 6 times.
Look at the edge AB,
dist[A] = 0, weight = 6, and dist[B] = +Infinity
Since the relaxation condition is true, we'll reset the distance of the node B.
Similarly, lets relax all the edges.
We can see that in the first iteration itself, we relaxed many edges. Now we have to continue doing this for 5 more times.
Relaxation 2nd time
Relaxation 3rd time
Relaxation 4th time
We notice that edges have stopped changing on the 4th iteration itself. This means that all the edges have now relaxed. A graph without any negative weight cycle will relax in n-1 iterations.
If after n-1 iterations, on the nth iteration any edge is still relaxing, we can say that negative weight cycle is present. Once it's confirmed that there's a negative weight cycle present in the graph, an error message is shown denoting that this problem cannot be solved.
10 UpvotesUpvote |
2 DownvotesDownvote |
Plzz give the result in table