To understand this example, it is recommended to have a brief idea on Bellman-Ford single source shortest path algorithm which can be found here (opens new window)

In Bellman-Ford algorithm, to find out the shortest path, we need to relax all the edges of the graph. This process is repeated at most (V-1) times, where V is the number of vertices in the graph.

The number of iterations needed to find out the shortest path from source to all other vertices depends on the order that we select to relax the edges.

Let's take a look at an example:

(opens new window)

Here, the source vertex is 1. We will find out the shortest distance between the source and all the other vertices. We can clearly see that, to reach vertex 4, in the worst case, it'll take (V-1) edges. Now depending on the order in which the edges are discovered, it might take (V-1) times to discover vertex 4. Didn't get it? Let's use Bellman-Ford algorithm to find out the shortest path here:

We're going to use this sequence:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  3->4  |  2->3  |  1->2  |
+--------+--------+--------+--------+

For our first iteration:

1. d[3] + cost[3][4] = infinity. It won't change anything.
2. d[2] + cost[2][3] = infinity. It won't change anything.
3. d[1] + cost[1][2] = 2 < d[2]. d[2] = 2. parent[2] = 1.

We can see that our relaxation process only changed d[2]. Our graph will look like: (opens new window)

Second iteration:

1. d[3] + cost[3][4] = infinity. It won't change anything.
2. d[2] + cost[2][3] = 5 < d[3]. d[3] = 5. parent[3] = 2.
3. It won't be changed.

This time the relaxation process changed d[3]. Our graph will look like: (opens new window)

Third iteration:

1. d[3] + cost[3][4] = 7 < d[4]. d[4] = 7. parent[4] = 3.
2. It won't be changed.
3. It won't be changed.

Our third iteration finally found out the shortest path to 4 from 1. Our graph will look like: (opens new window)

So, it took 3 iterations to find out the shortest path. After this one, no matter how many times we relax the edges, the values in d[] will remain the same. Now, if we considered another sequence:

+--------+--------+--------+--------+
| Serial |    1   |    2   |    3   |
+--------+--------+--------+--------+
|  Edge  |  1->2  |  2->3  |  3->4  |
+--------+--------+--------+--------+

We'd get:

1. d[1] + cost[1][2] = 2 < d[2]. d[2] = 2.
2. d[2] + cost[2][3] = 5 < d[3]. d[3] = 5.
3. d[3] + cost[3][4] = 7 < d[4]. d[4] = 5.

Our very first iteration has found the shortest path from source to all the other nodes. Another sequence 1->2, 3->4, 2->3 is possible, which will give us shortest path after 2 iterations. We can come to the decision that, no matter how we arrange the sequence, it won't take more than 3 iterations to find out shortest path from the source in this example.

We can conclude that, for the best case, it'll take 1 iteration to find out the shortest path from source. For the worst case, it'll take (V-1) iterations, which is why we repeat the process of relaxation (V-1) times.

Remarks

Given a directed graph G, we often want to find the shortest distance from a given node A to rest of the nodes in the graph. Dijkstra algorithm is the most famous algorithm for finding the shortest path, however it works only if edge weights of the given graph are non-negative. Bellman-Ford however aims to find the shortest path from a given node (if one exists) even if some of the weights are negative. Note that, shortest distance may not exist if a negative cycle is present in the graph (in which case we can go around the cycle resulting in infinitely small total distance ). Bellman-Ford additionally allows us to determine the presence of such a cycle.

Total complexity of the algorithm is O(V*E), where V - is the number of vertices and E number of edges