Shortest Path Using Bellman Ford Algorithm

Introduction

This post about Bellman Ford Algorithm is a continuation of the post Shortest Path Using Dijkstra’s Algorithm. While learning about the Dijkstra’s way, we learnt that it is really efficient an algorithm to find the single source shortest path in any graph provided it has no negative weight edges and no negative weight cycles.

The running time of the Dijkstra’s Algorithm is also promising, O(E +VlogV) depending on our choice of data structure to implement the required Priority Queue.

Why Bellman Ford Algorithm?

There can be scenarios where a graph may contain negative weight cycles, of course we do not see this in a real life simpler graph problems where we need to find the shortest or the cheapest paths between cities etc. But yes, there are complex real life applications where we will have scenarios like negative edges and negative edge cycles. Few of them are Linear Programming or Solving the Difference Constraints (for VLSI designs etc) or Detecting Network Failures.

Understanding the meaning of negative edge weights in a graph

I am sure at first it is very difficult to understand the significance of a negative edge weight. But consider the below scenario:

A student trying to manage his expenses, where he has to work part time to pay for his fee. His situation and the maintenance of account can be represented by a graph where the money he earns during a period can be represented by a positive edge weight and the money he spends can be a negative edge weight.

There can be many similar situations where we can see negative edge weights and sometimes negative weight cycles.

What is Negative Weight Cycle

A negative weight cycle means that if we add the weights of all the edges in the cycle the sum will turn up to be a negative number. See the below graph, it contains a negative weight cycle (C, G, H, C) with weight -4.
Bellman Ford Algorithm
So, how is Bellman Ford solving the negative weight cycles problem?
Actually its not, the algorithm cannot solve this problem and cannot give you a definite path. It is theoretically impossible to find out the shortest path if there exists a negative weight cycle. If you happen to find the shortest path, then you can go through the negative cycle once more and get a smaller path. You can keep repeating this step and go through the cycle every time and reduce the total weight of the path to negative infinity.

So, in practical scenarios, this algorithm will either give you a valid shortest path or will indicate that there is a negative weight cycle.

Explanation – Shortest Path Using Bellman Ford Algorithm

We can use Bellman Ford for directed as well as un-directed graphs. Let us solve a problem using directed graphs here. The idea of the algorithm is fairly simple.

  1. It maintains a list of unvisited vertices.
  2. It chooses a vertex (the source) and assigns a maximum possible cost (i.e. infinity) to every other vertex.
  3. The cost of the source remains zero as it actually takes nothing to reach from the source vertex to itself.
  4. In every subsequent iteration of the algorithm it tries to relax each edge in the graph (by minimizing the cost of the vertex on which the edge is incident).
  5. It repeats step 4 for |V|-1 times. By the last iteration we would have gotten some shortest path from Source to each vertex.

The formula for relaxation remains same as Dijkstra’s Algorithm.

So, why does the outer loop runs |V| – 1 times?

The argument would be, that the shortest path in the graph with |V| vertices cannot be more lengthy than |V| – 1. So, if we relax all the edges |V| – 1 times, we would have covered all possibilities of relaxing the edges and we would be left with all shortest paths. There are many proofs by Induction available in case you are more interested. Or you can look forward for my next post about “The correctness of Bellman Ford Algorithm”.

Demonstration

For demonstration purpose, we would consider the following graph.

Step 1 :

Considering A as the source, assign it the cost zero. Add all the vertices (A, B, C, D, E, F, G, H) to a list. For all vertices except A assign a cost infinity. Also, it is advisable to maintain a list of edges handy. Here is the graph to start with:
Bellman Ford Algorithm

Step 2 :

Take one vertex at a time say A, and relax all the edges in the graph. Point worth noticing is that we can only relax the edges which are outgoing from the vertex A. Rest of the edges will not make much of a difference. So, the following are the sub steps for step 2.

Relax (A, E) : cost of E = MIN(current cost of E[∞] , cost of A[0] + W{A,E}[6]).Cost(E) becomes 6.
Relax (A, B) : cost of B = MIN(current cost of B[∞] , cost of A[0] + W{A,B}[8]).Cost(B) becomes 8.
Relax (B, C) : cost of C = MIN(current cost of C[∞] , cost of B[8] + W{B,C}[6]).Cost(C) becomes 14.
Relax (C, H) : cost of H = MIN(current cost of H[∞] , cost of C[14] + W{C,H}[4]).Cost(H) becomes 18.
Relax (H, G) : cost of G = MIN(current cost of G[∞] , cost of H[18] + W{H,G}[-2]).Cost(G) becomes 16.
Relax (G, C) : cost of C = MIN(current cost of C[14] , cost of G[16] + W{G,C}[-1]).Cost(C) remains 14.
Relax (G, D) : cost of D = MIN(current cost of D[∞] , cost of G[16] + W{G,D}[1]).Cost(D) becomes 17.
Relax (D, B) : cost of B = MIN(current cost of B[8] , cost of D[17] + W{D,B}[2]).Cost(B) remains 8.
Relax (E, F) : cost of F = MIN(current cost of F[∞] , cost of E[6] + W{E,F}[3]).Cost(F) becomes 9.
Relax (E, G) : cost of G = MIN(current cost of G[16] , cost of E[6] + W{E,G}[2]).Cost(G) becomes 8.
Relax (F, G) : cost of G = MIN(current cost of G[8] , cost of F[9] + W{F,G}[6]).Cost(G) remains 8.

Bellman Ford Algorithm
The image above represents the state of the graph after step 2. By this time we are done with one iteration of our algorithm. Let us try one more and see if we understand it clearly.

Also, if we analyze the above image, we understand that the cost to reach each vertex can be updated K times (where K is the number of incoming edges to this vertex). It might be possible that the first cost is so less that it is not changed by the subsequent operations. There are K numbers in the square brackets, one number is added each time an incoming edge is relaxed.

Step 3 :

Start from any one vertex, say A again and relax all the edges as below:

Relax (A, E) : cost of E = MIN(current cost of E[6] , cost of A[0] + W{A,E}[6]).Cost(E) remains 6.
Relax (A, B) : cost of B = MIN(current cost of B[8] , cost of A[0] + W{A,B}[8]).Cost(B) remains 8.
Relax (B, C) : cost of C = MIN(current cost of C[14] , cost of B[8] + W{B,C}[6]).Cost(C) remains 14.
Relax (C, H) : cost of H = MIN(current cost of H[18] , cost of C[14] + W{C,H}[4]).Cost(H) remains 18.
Relax (H, G) : cost of G = MIN(current cost of G[8] , cost of H[18] + W{H,G}[-2]).Cost(G) remains 8.
Relax (G, C) : cost of C = MIN(current cost of C[14] , cost of G[8] + W{G,C}[-1]).Cost(C) becomes 7.
Relax (G, D) : cost of D = MIN(current cost of D[17] , cost of G[8] + W{G,D}[1]).Cost(D) becomes 9.
Relax (D, B) : cost of B = MIN(current cost of B[8] , cost of D[9] + W{D,B}[2]).Cost(B) remains 8.
Relax (E, F) : cost of F = MIN(current cost of F[9] , cost of E[6] + W{E,F}[3]).Cost(F) remains 9.
Relax (E, G) : cost of G = MIN(current cost of G[8] , cost of E[6] + W{E,G}[2]).Cost(G) remains 8.
Relax (F, G) : cost of G = MIN(current cost of G[8] , cost of F[9] + W{F,G}[6]).Cost(G) remains 8.
Bellman Ford Algorithm
The image above represents the state of the graph after step 3. By this time we are done with two iterations of our algorithm. If we analyze it, we will see that not much has changed except vertices (C, D and G). Let us try one last time and see if we understand it clearly.

Step 4 :

Start from any one vertex, say A again and relax all the edges as below:

Relax (A, E) : cost of E = MIN(current cost of E[6] , cost of A[0] + W{A,E}[6]).Cost(E) remains 6.
Relax (A, B) : cost of B = MIN(current cost of B[8] , cost of A[0] + W{A,B}[8]).Cost(B) remains 8.
Relax (B, C) : cost of C = MIN(current cost of C[7] , cost of B[8] + W{B,C}[6]).Cost(C) becomes 7.
Relax (C, H) : cost of H = MIN(current cost of H[18] , cost of C[7] + W{C,H}[4]).Cost(H) becomes 11.
Relax (H, G) : cost of G = MIN(current cost of G[8] , cost of H[11] + W{H,G}[-2]).Cost(G) remains 8.
Relax (G, C) : cost of C = MIN(current cost of C[7] , cost of G[8] + W{G,C}[-1]).Cost(C) remains 7.
Relax (G, D) : cost of D = MIN(current cost of D[9] , cost of G[8] + W{G,D}[1]).Cost(D) remains 9.
Relax (D, B) : cost of B = MIN(current cost of B[8] , cost of D[9] + W{D,B}[2]).Cost(B) remains 8.
Relax (E, F) : cost of F = MIN(current cost of F[9] , cost of E[6] + W{E,F}[3]).Cost(F) remains 9.
Relax (E, G) : cost of G = MIN(current cost of G[8] , cost of E[6] + W{E,G}[2]).Cost(G) remains 8.
Relax (F, G) : cost of G = MIN(current cost of G[8] , cost of F[9] + W{F,G}[6]).Cost(G) remains 8.

Bellman Ford Algorithm
The image above represents the state of the graph after step 4. By this time we are done with three iterations of our algorithm. If we analyze it, we will see that not much has changed except vertex (H). Let us try one last time and see if we understand it clearly.

So, I hope the idea is clear now, eventually if we keep repeating this we might end up in either of the two situations:

  1. We might not notice any change in cost for any vertex in later iterations. It would be good to stop at that point for making the algorithm efficient.
  2. We might endlessly notice changes in costs of one or the other vertex in later iterations. This will be the case of negative weight cycles. Hence, we need to stop at some point and that would be the after |V| – 1 for the reason mentioned in the above section.

Once we get out of iterations, we need to do follow these steps one more time to find if the cost is still getting reduced. If we find reduction in cost, we can say that there definitely is a negative weight cycle and hence no shortest path exist.

Source Code – Shortest Path Using Bellman Ford Algorithm

To download the complete code, please visit techieme github repopsitory

 

Analysis of Algorithm

  1. The initialization loop runs |V| times.
    • The outer for loop runs |V| – 1 times.
    • The inner loop runs |E| times for each iteration of the outer loop.
  2. The last loop runs for |E| times.

Step 1 takes O(|V|) time, Step 2 takes O(|V| . |E|) times and Step 3 takes O(|E|) times. Hence the running time would be dominated by the term O(|V| . |E|).

Don’t forget to subscribe to TechieMe to get updates on latest posts.