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 → V_{1} → … → V_{k} is the shortest path from S → V_{k} then **D**(S, V_{i}) ≤ **D**(S, V_{j}). But in the above given graph, clearly that principle is violated. In the above graph, the shortest path from V_{1} to V_{3} is of length 3 units but the shortest path to V_{4} is of length 1 unit which means that V_{4} is actually closer to V_{1} than V_{3}, which is contradicting Dijkstra’s principle.

### Negative Cycles

A Negative Cycle is a path V_{1} → V_{ 2} → V_{3} → … V_{k} → V_{1} 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 –

/* * Bellman-Ford Algorithm * * Authored by, * Vamsi Sangam */ #include <cstdio> #include <cstdlib> #include <climits> using namespace std; // This is used to construct // the Adjacency List struct node { int vertex, weight; struct node * next; }; // This is used to construct the Shortest Paths to all // vertices, as we cannot return multiple values, // we use a struct struct pathInfo { int vertex, distance, parent; }; // Adds a new edge into the Adjacency List // Follows Head Insertion for O(1) Insertion struct node * add(struct node * head, int vertex, int weight) { struct node * p = (struct node *) malloc(sizeof(struct node)); p->vertex = vertex; p->weight = weight; p->next = head; return p; } // Bellman-Ford Algorithm which takes the Graph (adjacencyList[]), starting vertex (startVertex), // and an empty array shortestDistances[] as input. It applies the algorithm and keeps filling values // into shortestDistances[]. It returns true if there are no negative edges, and vice-versa. bool bellmanFord(struct node * adjacencyList[], int vertices, int startVertex, struct pathInfo shortestDistances[]) { struct node * traverse; int i, j, k; // Initialisation for (i = 0; i <= vertices; ++i) { shortestDistances[i].vertex = i; shortestDistances[i].distance = INT_MAX; shortestDistances[i].parent = -1; } // Setting distance to source = 0 shortestDistances[startVertex].parent = 0; shortestDistances[startVertex].distance = 0; // The Algorithm that computes Shortest Distances for (i = 1; i <= vertices - 1; ++i) { // Runs 'vertices - 1' times = O(|V|) for (j = 1; j <= vertices; ++j) { // Runs as many times as the edges = O(|E|) // The code ahead basically explores the whole of Adjcency List, // covering one edge once, so the runtime of the code in this // block is O(|E|) traverse = adjacencyList[j]; while (traverse != NULL) { if (shortestDistances[j].distance == INT_MAX) { // Important...! traverse = traverse->next; continue; } // Checking for Relaxation if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) { // Relaxation shortestDistances[traverse->vertex].distance = traverse->weight + shortestDistances[j].distance; shortestDistances[traverse->vertex].parent = j; } traverse = traverse->next; } } } // Checking for Negative Cycles for (j = 1; j <= vertices; ++j) { traverse = adjacencyList[j]; while (traverse != NULL) { // Checking for further relaxation if (traverse->weight + shortestDistances[j].distance < shortestDistances[traverse->vertex].distance) { // Negative Cycle found as further realxation is possible return false; } traverse = traverse->next; } } return true; } int main() { int vertices, edges, i, j, v1, v2, weight; printf("Enter the Number of Vertices -\n"); scanf("%d", &vertices); printf("Enter the Number of Edges -\n"); scanf("%d", &edges); struct node * adjacency_list[vertices + 1]; //Size is made (vertices + 1) to use the //array as 1-indexed, for simplicity //Must initialize your array for (i = 0; i <= vertices; ++i) { adjacency_list[i] = NULL; } printf("Enter the edges -\n\n"); for (i = 1; i <= edges; ++i) { scanf("%d%d%d", &v1, &v2, &weight); adjacency_list[v1] = add(adjacency_list[v1], v2, weight); } //Printing Adjacency List printf("\nAdjacency List -\n\n"); for (i = 1; i <= vertices; ++i) { printf("adjacency_list[%d] -> ", i); struct node * temp = adjacency_list[i]; while (temp != NULL) { printf("(%d, %d) -> ", temp->vertex, temp->weight); temp = temp->next; } printf("NULL\n"); } struct pathInfo shortestDistances[vertices + 1]; int startVertex; printf("\nEnter a Start Vertex -\n"); scanf("%d", &startVertex); if (bellmanFord(adjacency_list, vertices, startVertex, shortestDistances)) { printf("No Negative Cycles exist in the Graph -\n"); } else { printf("Negative Cycles exists in the Graph -\n"); // The Bellman-Ford Algorithm does not work with negative cycles, // all it can do is merely detect them, so when a negative cycle // is detected, the shortestDistances array has wrong values return 0; } printf("\n\nVertex Shortest Distance to Vertex %d Parent Vertex-\n", startVertex); for (i = 1; i <= vertices; ++i) { printf("%d %d %d\n", i, shortestDistances[i].distance, shortestDistances[i].parent); } return 0; }

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 ! **Commenting is super easy if you are a Facebook, Twitter or a Google+ user**…! So, don’t hesitate..! 😉 Keep practicing… Happy Coding…! 🙂

Hey Vamsi,

Do you have some good test cases for this problem?

Thanks,

Murali

LikeLike

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..! 😉

LikeLike

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?

LikeLike

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…! 🙂

LikeLike

Hey so sorry I was viewing the problem all wrong , I get it now thanks so much for your time!

LikeLike

My pleasure…! 🙂

LikeLike

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?

LikeLike

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.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 –

I hope you understood how this works. If not, or if you have more doubts, feel free to ask…! 🙂

LikeLike

Thank you very much 🙂

I understood it!

LikeLike

Happy to help Albus…! 😀

LikeLike

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?

LikeLike

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… 🙂

LikeLike

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…

LikeLike

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 –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..! 😉

LikeLike

Makes sense! Thank you 🙂

LikeLike

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….

LikeLike

Good luck….! 🙂

LikeLike

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

LikeLike

Sure…! I will…! 😀

LikeLike

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

LikeLike

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…. 😀

LikeLike