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!

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

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

Previous table

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.