Introduction

The Bellman-Ford algorithm is one of the first algorithms to find the shortest path between a source and all other vertices in a digraph without negative cycles. It is a dynamic programming algorithm that iteratively relaxes the edges of the graph. In this article, an example is shown to illustrate this algorithm!

Key steps of the Bellman-Ford algorithm

Initialization: We first consider that all vertices are infinitely far from the source, except the source itself that is of course at a distance of 0. Our goal will be to update those vertices weights iteratively.
Relaxation: This is where the magic happens. For all edges of the graph, we check if the weight of the source vertex plus the weight of the edge is less than the weight of the destination vertex. If it is the case, we update the weight of the destination vertex. For example, if the first edge is of value 4, then the weight of the destination will become 4.
Termination: We repeat the relaxation step times. This is because the shortest path between two vertices can have at most edges. If we still have a change in the weights after the iteration, it means that there is a negative cycle in the graph.

The Bellman-Ford does not work with negative cycles

A negative cycle is a cycle that has a total weight that is strictly negative. In this context, you can imagine that If you want to go from A to C, the shortest path would be to go back to A indefinitely to reduce the weight infinitely. The Bellman-Ford algorithm obviously does not work in this case.

However, since we already established that the algorithm does not need more than iterations to find the shortest path, we can use this property to detect negative cycles. If we still have a change in the weights after the iteration, it means that there is a negative cycle in the graph.

Other algorithm implementation could reduce the number of iterations.

The algorithm

Let’s dive into the algorithm!

In a python style pseudo code, the algorithm can be implemented as follows :

def bellman_ford(G: Graph, p: function(int, int) -> int, source: int) -> [prev: List[int], weight: List[int]]:
    '''Pseudo code of bellman ford.

    Args: 
        G : Graph : A graph without negative cycles
        p : function(int, int) -> int : A function that returns the weight of the edge (u, v) in O(1)
        source : int : The index of the source vertex in V
    
    Returns:
        prev : List[int] : An array containing the previous vertex of each vertex.
        weight : List[int] : An array containing, for each vertex, the weight of the shortest path (sum of weights) from the source to this vertex.
    '''

    # Initialization
    for v in G.vertices:
        weight[v] = inf
        prev[v] = '-'


    weight[source] = 0 # From source to source, the weight is 0

    for iter in [1, |V| - 1]: # Proof of the stopping condition on wikipedia
        for (u, v) in G.edges:
            if weight[u] + p(u, v) < weight[v]:
                weight[v] = weight[u] + p(u, v)
                prev[v] = u

    return prev, weight

The relaxation step if weight[u] + p(u, v) < weight[v]: is the key step of the algorithm. It is where the algorithm updates the weight of the vertices.

Corrected Exercise

Apply the Bellman-Ford algorithm to the following digraph to find the shortest path from the source s to p.

Solution

We will create two tables to keep track of the weights and the previous vertices.

The first table will contain the weights of the vertices. Is is equivalent to the current shortest distance from the source to the vertex.
The second table will contain the previous vertex that is supposed to be taken to reach the current vertex with the shortest path.

Weights table

Iteration	1	2	3	4	p
Iter 0
Iter 1	4		2
Iter 2	4	19	-2	4
Iter 3	4	19	-2	0	17
Iter 4	4	19	-2	0	17
Iter 5	4	19	-2	0	17

Non-deterministic aspect

You may have a different result from the one presented here!

The order in which the edges are relaxed can change the result. For instance, if the weight of the edge 3 -> 4 is updated before the weight of the edge 1 -> 4, the weight of 4 will be 0 instead of 4.

This algorithm will still however always converge to the same result for the weight, but the path may change. (from two cities, you can probably find two differents roads with the same lenght).

Previous table

Iteration	s	1	2	3	4	p
Iter 0	-	-	-	-	-	-
Iter 1	-	s	-	s	-	-
Iter 2	-	s	1	1	3	-
Iter 3	-	s	1	1	3	4
Iter 4	-	s	1	1	3	4
Iter 5	-	s	1	1	3	4

To compute the path, take the last line of the previous table.

From p, we have 4. From 4, we have 3. From 3, we have 1. From 1, we have s.

To go from s to p, the shortest path has for weight 4 - 6 + 2 + 17 = 17.