The Bellman-Ford algorithm finds the shortest path to each vertex in the directed graph from the source vertex. Unlike Dijkstra’s algorithm, Bellman-Ford can have negative edges.

To begin, all the outbound edges are recorded in a table in alphabetical order.

Like Dijkstra’s algorithm, a table recording the distance to each vertex and the predecessor of each vertex is created. The distances for each vertex, except the source vertex, is initialized to infinity. Distance is represented by the variable d and the predecessor is represented by the variable π.

The Bellman-Ford algorithm will iterate through each of the edges. Since there are 9 edges, there will be up to 9 iterations. During each iteration, the specific edge is relaxed. During the first iteration, the cost to get to vertex C from A is -3. The current distance from the source to A is infinity. When -3 is added to infinity, the result is infinity, so the value of C remains infinity. Similarly, from A to E, the cost is 2, however, since the distance to A is infinity, the value of E remains infinity. Looking at edges B-F, C-B, C-H, F-G, G-B, and H-D, we can see that they all yield the same result, infinity. The last edge, S-A, yields a different result. The weight of edge S-A is 5. The current distance to S is 0, so the distance from S to A is 0 + 5 = 5. The predecessor to A is set to S. After the first iteration, Bellman-Ford found the path to A from S.

Since all the edges have been relaxed, Bellman-Ford starts on the second iteration. Although each edge is relaxed, the only edges that matter are the edges from S and from A since the distance to those vertices is already known. The distance to all other vertices is infinity. Looking at the table containing the edges, we start by relaxing edge A-C.

The weight of edge A-C is -3. The current distance to vertex A is 5 via edge S-A, so the distance to vertex C is 5 + (-3) = 2. The predecessor of C is A. The weight of edge A-E is 2. The distance to E is 5 + 2 = 7 via edge S-A. The predecessor of E is updated to A. Edge B-F cannot be relaxed yet.

Edge C-B can be relaxed since we know the distance to C. The distance to B is
2 + 7 = 9 and the predecessor of vertex B is C. Edge C-H can be relaxed since we know the distance to C. The distance to H is 2 + (-3) = -1 and the predecessor of vertex H is vertex C.

Edge F-G cannot yet be relaxed. Edge G-B cannot be relaxed. Edge H-D can be relaxed since we know the distance to vertex H is -1. The distance to vertex D is -1 + 1 = 0 and the predecessor to vertex D is vertex H.

The distance to A from edge S-A is already 5 so no update is necessary. This ends iteration 2.

During the third iteration, the Bellman-Ford algorithm examines all the edges again. Edges A-C and A-E yield the same results. Edge B-F can now be relaxed. The distance to B is 9, so the distance to vertex F is 9 + (-5) = 4. The predecessor to F is B.

Edges C-B and C-H yield the same results, so the table remains the same. Edge F-G can now be relaxed. The distance to vertex F is 4, so the distance to vertex G is 4 + 2 = 6. The predecessor of G is F.

Edge G-B can now be relaxed. The distance to vertex G is 6, so the distance to B is 6 + 4 = 10. Since vertex B can be reached with a shorter distance by going through edge C-B, the table remains the same.

During the fourth iteration, all the edges are examined. The algorithm sees that there are no changes, so the algorithm ends on the fourth iteration.

If this graph had a negative cycle, after the iteration is repeated n-1 times, theoretically the Bellman-Ford algorithm should have found the shortest paths to all vertices. During the nth iteration, where n represents the number of vertices, if there is a negative cycle, the distance to at least one vertex will change. Let’s look at a quick example.

The table with the distances and the predecessors is constructed. The distances are initialized to infinity for vertices A, B and C. The distance to S is 0.

Looking at the first edge, A-B cannot be relaxed yet and neither can edge B-C nor edge C-A. Edge S-A can be relaxed. The distance to S is 0, so the distance to A is 0 + 3 = 3. The predecessor of A is S.

Edge S-B can also be relaxed. The distance to vertex B is 0 + 6 = 6. Vertex B’s predecessor is S.

The first iteration is complete. During the second iteration, all of the edges are examined again.

Edge A-B can be relaxed during the second iteration. The distance to A is 3, so the distance to vertex B is 3 + 5 = 8. Since the distance to B is already less than the new value, the value of B is retained. Edge B-C can be reached in 6 + 2 = 8. Vertex C’s predecessor is vertex B.

Edge C-A is examined next. The distance to C is 8 units, so the distance to A via edge B-C is 8 + (-10) = -2. Since the distance to A via edge C-A is less than the distance to A via S-A, the distance to A is updated.

Edges S-A and S-B yield nothing better, so the second iteration is complete. The third iteration starts.

Edge A-B is relaxed. The distance to A is currently -2, so the distance to B via edge A-B is -2 + 5 = 3. Since the distance to B is less via A-B than S-B, the distance is updated to 3. Vertex B’s predecessor is updated to vertex A.

Edge B-C is relaxed next. The current distance to B is 3, so the distance to C is
3 + 2 = 5. The distance to C is updated to 5.

Edge C-A is relaxed. The distance to C is 5 + (-10) = -5. The distance to vertex A is updated to -5 units.

Edges S-A and S-B yield no better results. At this time, all shortest paths should have been found. If we examine another iteration, there should be no changes.

Edge A-B is relaxed. The distance to A is -5 so the distance to B is -5 + 5 = 0. The distance to B is updated to 0. Since the value changes on the nth iteration, values will change on the n+1th iteration as well; values will continue to change indefinitely. If we examine the graph closely, we can see that A-B-C yields a negative value: 5 + 2 + (-10) = -3.

If you liked what you read, check out my book, An Illustrative Introduction to Algorithms.