Bellman-Ford Algorithm with Example

(8615 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.

When and Why to use Bellman Ford?

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.

Bellman-Ford Algorithm with Example
After every BCD loop, the value of node B will change. The problem with Dijkstra's algorithm is that it doesn't detects whether a graph is having this negative weight cycle or not. Bellman Ford on the other hand detects this cycle and tells us that this problem cannot be solved.

Edge Relaxation

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.

Working through the Algorithm

Consider this weighted graph,
Bellman-Ford Algorithm with Example
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.
Bellman-Ford Algorithm with Example
Similarly, lets relax all the edges.
Bellman-Ford Algorithm with Example
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
Bellman-Ford Algorithm with Example
Relaxation 3rd time
Bellman-Ford Algorithm with Example
Relaxation 4th time
Bellman-Ford Algorithm with Example
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.

Checking the presence of negative weight cycle

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.

Pseudocode for Bellman Ford:

  • Create an array dist[] of size V (number of vertices) which store the distance of that vertex from the source.
  • Initialize dist[0] to 0 and rest values to +Inf.
  • Repeat this process for V-1 times:
    1. For each edge u-v in the graph,
      If dist[u] + weight < dist[v],
      dist[v] = dist[u] + weight
  • For any edge in the graph, if dist[u] + weight < dist[v], Negative weight cycle is present
        

Solution Didn't Worked 2 DownvotesDownvote

        


Comments

1 comment
  • V Hema Sri

    Plzz give the result in table



Search


Earn Money by Submitting Articles
Start submutting articles. Click here to get started
Play 2048 Game Online

Play Duckhunt Online
Search Tags