Before reading this example, it is required to have a brief idea on edge-relaxation. You can learn it from here

Bellman-Ford Algorithm is computes the shortest paths from a single source vertex to all of the other vertices in a weighted digraph. Even though it is slower than Dijkstra’s Algorithm, it works in the cases when the weight of the edge is negative and it also finds negative weight cycle in the graph. The problem with Dijkstra’s Algorithm is, if there’s a negative cycle, you keep going through the cycle again and again and keep reducing the distance between two vertices.

The idea of this algorithm is to go through all the edges of this graph one-by-one in some random order. It can be any random order. But you must ensure, if u-v (where u and v are two vertices in a graph) is one of your orders, then there must be an edge from u to v. Usually it is taken directly from the order of the input given. Again, any random order will work.

After selecting the order, we will relax the edges according to the relaxation formula. For a given edge u-v going from u to v the relaxation formula is:

if distance[u] + cost[u][v] < d[v]
    d[v] = d[u] + cost[u][v]

That is, if the distance from source to any vertex u + the weight of the edge u-v is less than the distance from source to another vertex v, we update the distance from source to v. We need to relax the edges at most (V-1) times where V is the number of edges in the graph. Why (V-1) you ask? We’ll explain it in another example. Also we are going to keep track of the parent vertex of any vertex, that is when we relax an edge, we will set:

parent[v] = u

It means we’ve found another shorter path to reach v via u. We will need this later to print the shortest path from source to the destined vertex.

Let’s look at an example. We have a graph:

https://s3-us-west-2.amazonaws.com/secure.notion-static.com/62cc5b56-9ecb-4440-8bf2-95cea86f9a7d/Untitled.png

We have selected 1 as the source vertex. We want to find out the shortest path from the source to all other vertices.

At first, d[1] = 0 because it is the source. And rest are infinity, because we don’t know their distance yet.

We will relax the edges in this sequence:

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

You can take any sequence you want. If we relax the edges once, what do we get? We get the distance from source to all other vertices of the path that uses at most 1 edge. Now let’s relax the edges and update the values of d[]. We get:

  1. d[4] + cost[4][5] = infinity + 7 = infinity. We can’t update this one.
  2. d[2] + cost[3][4] = infinity. We can’t update this one.
  3. d[1] + cost[1][2] = 0 + 2 = 2 < d[2]. So d[2] = 2. Also parent[2] = 1.
  4. d[1] + cost[1][4] = 4. So d[4] = 4 < d[4]. parent[4] = 1.
  5. d[4] + cost[4][6] = 9. d[6] = 9 < d[6]. parent[6] = 4.