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.
Negative Cycles
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…! 🙂
24 thoughts on “Bellman Ford Algorithm”
Vamsi,I request you to give stl version of the algorithm also.STL version is quite comfortable and keep code cleaner.That will be really awesome!!! 🙂
Sure..! Thanks a lot for the suggestion..!! 😀
Hey Vamsi,
Do you have some good test cases for this problem?
Thanks,
Murali
Hi Murali..! 🙂 … I am sorry for my late reply… I got caught up in exams..! 😛 … Well I don’t have many corner test cases… But I think you’ll find Albus’ test case useful… Find it in the comments… And I promise I’ll add to the test cases soon..! 🙂 … Have a nice day..! 😉
Hi! sorry to bother I am now studying the Bellman-ford algorithm in school and trying to code it myself and your code helped me a lot! I have just a quick question, I used your code to try to find the vertices that are in the negative cycle and if you have a vertex that is reachable/adjacent from another but his adjacencyList is null the PrintNegativeCycle doesn’t contemplate him like in this example
9 8
7
2 3 -100
3 4 -100
1 2 -100
4 5 -100
5 1 -300
7 8 100
5 6 400
7 1 100
the 6 is on the negative cycle but is not printed out. Can you explain me why please?
Hello @janep..! Correct me if I am wrong, but the your input gives this graph, where the vertex 6 is clearly not a part of the negative cycle…
Feel free to ask if you have anymore doubts…! 🙂
Hey so sorry I was viewing the problem all wrong , I get it now thanks so much for your time!
My pleasure…! 🙂
Hi,
thanks for the explanation!
Do you know how can I identify all the vertices in the Negative weight Cycle, instead of just report there is a negative weight cycle?
Hello Albus..! I am happy that my post could help you… 🙂 … Coming to your doubt, you can print the vertices of the Negative Cycle too…! In my code for the Bellman-Ford Algorithm, at line number 96, instead of returning false, you must return the value of ‘j‘ at that iteration, which would have the vertex number at which you found that further relaxation was possible.
if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) { // Negative Cycle found as further relaxation is possible return j; }That would definitely be a vertex of the Negative Cycle. Now, once you get it, keep looking at it’s parent recursively, until you reach the same vertex again. This is your Negative Cycle..! This recursive procedure does that job for you –
// call from main() --> PrintNegativeCycle(shortestDistances, shortestDistances[j].parent, j); void PrintNegativeCycle(struct pathInfo shortestDistances[], int vertex, int startVertex) { if (vertex == startVertex) { printf("%d ", vertex); return; } else { PrintNegativeCycle(shortestDistances, shortestDistances[vertex].parent, startVertex); printf("%d ", vertex); } }I hope you understood how this works. If not, or if you have more doubts, feel free to ask…! 🙂
Thank you very much 🙂
I understood it!
Happy to help Albus…! 😀
Hi!
Sorry to bother, I’m having a problem with the printNegativeCycle function.
With the edges: (1 2 -10), (2 3 -10), (3 1 -10) everything works fine, but if I reverse the arrows like this: (2 1 -10), (3 2 -10), (1 3 -10) I get Segmentation fault. I don’t understand why. Any idea how can I fix it?
Ok…. The input seems fine… I’ll need the source code to assist you further, Albus…. Can you post the source code here….? Or an Ideone / PasteBin link would be better… 🙂
https://ideone.com/kGZUKe
Here it is, it’s your code, but I added a global variable named “GLOBAL” that is the vertex found in the last cycle of bellman-ford and I also scan the source vertex for bellman-ford in main.
It gives me segmentation fault…
There was just a small flaw in my code for printing the negative cycle… The test case which you gave is a pretty interesting one..! In your test case… Bellman Ford returns the vertex 1, who’s parent is vertex 2, who’s parent is vertex 3, who’s parent is “vertex 0“..! Why is it “vertex 0″… That’s because in the initialization part of Bellman Ford, we set the startVertex’s parent to zero… In this case it remains unchanged, because in such test cases, for all the (|V| – 1) times we perform an exploration, only one vertex is visited… In your case, |V| – 1 = 2… When we check twice, only the edges, (3 → 2) and (2 → 1) are visited, but not the edge (1 → 3)… So, the parent of vertex 3 is never touched. In general, all parents of all the vertices in the cycle get set to some value… But this one’s an exceptional case… Thanks for letting me know..! This modified procedure, works with the special test case too –
void PrintNegativeCycle(struct pathInfo shortestDistances[], int vertex, int startVertex) { if (vertex == startVertex) { printf("%d ", vertex); } else if (shortestDistances[vertex].parent == 0) { PrintNegativeCycle(shortestDistances, startVertex, startVertex); printf("%d ", vertex); } else { PrintNegativeCycle(shortestDistances, shortestDistances[vertex].parent, startVertex); printf("%d ", vertex); } }If you don’t understand, what’s really happening, print the intermediate results such as the parents and distances of all the vertices…. I’m sure you’ll get the idea..! 😉
Makes sense! Thank you 🙂
I am just going through perterson Computer Networks book and algorithm CLRS and trying to compare these two.. but they are quite different in approach.. Anyway i am preparing for tech interviews….
Good luck….! 🙂
Thank you for your wishes vamsi.
please go through this below link , if not visited yet.. most of the stories are really inspirational …..
http://www.quora.com/What-are-the-most-inspirational-success-stories-ever-around-the-world
Sure…! I will…! 😀
Hi Vamsi,
Thank you for your clear cut simple explanation of Bellman ford algorithm.
I got doubt here you mentioned under negative cycle paragraph B->C->D cicle once it becomes 1. i thought it is 2 . how it will be 1 please reply me..
Oops..! That was a mistake @srikanta … Thanks for correcting me….! Looks like you understood the algorithm pretty well…! 😛 🙂 … Let me know if you have any other doubts…. 😀