Hello people…! In this post I will talk about another single source shortest path algorithm, the Bellman Ford Algorithm. Unlike Dijkstra’s Algorithm, which works only for a graph positive edge weights, the Bellman Ford Algorithm will give the shortest path from a given vertex for a graph with negative edge weights also. Due to this, the Bellman Ford Algorithm is more versatile, but, it’s speciality comes at a cost. The runtime complexity of Bellman Ford Algorithm is O(|V||E|), which is substantially more than that of Dijkstra’s Algorithm. Sometimes this algorithm is called Bellman Ford Moore Algorithm, as the same algorithm was published by another researcher.
Before we get started, there are a couple of things that we must understand. Firstly, why does Dijkstra’s Algorithm fail for negative edge weights and second, the concept of Negative Cycles.
Why does Dijkstra fail?
Consider, the graph below,
The Dijkstra’s Algorithm is based on the principle that, if S → V1 → … → Vk is the shortest path from S → Vk then D(S, Vi) ≤ D(S, Vj). But in the above given graph, clearly that principle is violated. In the above graph, the shortest path from V1 to V3 is of length 3 units but the shortest path to V4 is of length 1 unit which means that V4 is actually closer to V1 than V3, which is contradicting Dijkstra’s principle.
A Negative Cycle is a path V1 → V 2 → V3 → … Vk → V1 where the total sum of the edge weights in the path is negative. Consider the graph below –
The path B → C → D is a negative cycle as the path’s total weight would be -2. So, the distance from A → B is 2, but if we circle the cycle once, we would get the distance as 0, if we circle once more, we would get -2. Like this we could keep on circling as much as we want to reduce the shortest distance. Hence the shortest distance to the vertex B, E becomes indeterminate.
So, we want Bellman Ford Algorithm to solve these two issues. We want it to compute the shortest path even for a graph with negative edges and negative cycles. The Bellman Ford will accurately compute the shortest path for a graph with negative edges but the algorithm fails for a graph with negative cycles. But, the algorithm can tell you if a negative cycle exists or not. If it exists the solution it puts up is incorrect, otherwise, the solution given by Bellman Ford Algorithm is perfect. This sounds fine because logically there will be no shortest paths for a graph with negative cycles.
Unlike the Dijkstra’s Algorithm where we had to use a priority queue, we will require no additional data structure to code Bellman Ford Algorithm. This makes writing the code much easier. And the algorithm is pretty straight-forward too. Take a look at the pseudo-code of the Bellman Ford Algorithm given below –
bellmanFord(G, s) for all edges in G(V) D(V) = INT_MAX parent[V] = -1 D(s) = 0 for i = 1 to |G(V)| - 1 for each edge (u, v) in G(E) if edge can be Relaxed D(v) = D(u) + weight of edge (u, v) parent[v] = u for each edge in G(E) if edge can be Relaxed return false return true
You may not understand the pseudo-code at the first look, here’s a step-by-step representation of it –
- Initialise the array which contains the shortest distances to infinity (a high integer value in the pseudo-code).
- Initialise the parent array which contains the parent vertices in the shortest path to NULL (or -1 if it is an integer array).
- Set the shortest distance of starting vertex to 0.
- Explore all the edges, and see if you can relax them. If you can, relax the edge and proceed with the exploration.
- Do the above operation |V| – 1 times.
- After that, do another exploration on the graph checking all the edges if they can be relaxed. If they can be relaxed, you can a negative cycle in the graph. Hence, return false.
- If the exploration gets finished successfully, the graph has no negative cycles and the data that you compute dis correct, so return true.
Now, what does exploring all the edges mean? If you are implementing the graph using an Adjacency List, it means to iterate over all the linked lists associated with all vertices. Now, what will be the sum of all the nodes in all Linked Lists in a given Adjacency List? Number of edges off course! So, we check all the edges from, edges of vertex 1 to vertex |V| in a linear manner. This whole operation takes O(|E|) time, which is repeated |V| – 1, so this part of the code takes O(|E||V|) time. Now, analyse the pseudo-code for a few minutes. Ask yourself how would you code this-ans-that. Now, when your mind is filled with the pseudo-code, look at the sketch below. The sketch below is sort of, “dry run” of the pseudo-code stated above –
The above sketch is self-explanatory. I hope you understand how the iterations go. In a way it looks like a very ordinary algorithm, without any greedy steps or partitions or so. The Bellman Ford Algorithm is pretty easy to code too. If you can work hard for an hour or two I’m sure you can code this algorithm. It does not require any priority queue or other tools. All you need to code Bellman Ford Algorithm is the pseudo-code. The pseudo-code is very important. Keep looking at the pseudo-code again-and-again whenever you get a doubt. I have put my code below for a reference, it is a C++ code –
If you have any doubts regarding the algorithm feel free to drop a comment. I’ll surely reply to them. I hope my post helped you in learning the Bellman Ford Algorithm. If it did, let me know by commenting! Keep practising… Happy Coding…! 🙂