Bellman–Ford algorithm

Imagine you are working on a chemistry project. After numerous experiments, your fellow chemists have collected the necessary data and represented it in a graph as shown in the picture below. The nodes are the compounds, while the weights stand for the amount of energy needed to convert one node to another: if negative, energy is released during the reaction.

Given a certain type of reactant, your task is to obtain all compounds by spending as little energy as possible. In situations where negative weights are present, negative cycles can occur. The Bellman-Ford algorithm is designed to detect the presence of such cycles. In the contrary case, it finds the shortest paths from a given node to all other nodes of the graph.

Description of the algorithm

In a weighted directed graph $G =(V, E)$, we need to find the shortest paths from the source node $s$ to all other nodes. $w_{u,v}$ denotes the weight of the edge $(u, v)$. If there is no such edge, we assume $w_{u, v} = \infty$. Let $d_v$ represent the weight of the shortest currently known path from node $s$ to node $v$. If no such path has been found yet, we set $d_v = \infty$. For the source itself, $d_s = 0$.

The main idea is to apply the process of relaxation along edges until necessary. Relaxing along the edge $(u, v)$ is an attempt to get a shorter path from $s$ to $v$ using the given edge. In other words, if $d_u + w_{u,v} < d_v$, we update $d_v$ to a smaller value, namely $d_u + w_{u,v}$, hence we include the edge $(u,v)$ in our shortest path. In this case, we call the relaxation process successful. Otherwise, the process is said to be unsuccessful, as we don't change anything.

Let's take a look at a simple example to illustrate this new concept. Assume we have previously calculated the current shortest paths from $s$ to $u$ and $v$ respectively, say $d_u = 5$, $d_v = 8$. Given $w_{u,v} = 1$, we want to relax along the edge $(u,v)$, i.e., we need to understand whether it is more efficient to go through the old blue path, for which $d_v = 8$, or the new path, which uses the existing green path from $s$ to $u$ and the red edge $(u,v)$. Obviously $d_u + w_{u,v} = 5 + 1 = 6 < 8 = d_v$, hence we conclude that the new path is cheaper. The relaxation process is successful, update $d_v = 6.$

In more detail, the Bellman-Ford algorithm can be described as follows:

1. Initialize the distances: $d_v = \infty, \;d_s = 0$.
2. Apply the process of relaxation to every edge exactly $|V| - 1$ times, where $|V|$ represents the number of nodes in graph $G$.
3. After step 2, we already have the final values of shortest paths $d_v$. However, there might be negative cycles. As we already noted, they can infinitely reduce the size of our shortest path, therefore it is necessary and sufficient to apply the relaxation process one last time. If any changes are observed in at least one of the shortest paths, we may confirm the presence of such cycle. Otherwise, we are done.

Why $|V| - 1$ applications of relaxation are sufficient? It is not difficult to understand that after the $i^{th}$ application, the algorithm correctly finds all the shortest paths consisting of no more than $i$ edges. Bearing in mind that cycles cannot serve as shortest paths, every path consists of $|V|-1$ edges or less, therefore the algorithm works correctly.

Example 1: 'No bad cycles'

Let's get back to the graph we introduced at the beginning of this topic. Set node $1$ as the source node. Our task is to find the shortest paths from this node to all other vertices using the Bellman-Ford algorithm.

1. Initialize the values of the shortest paths. We will write these values above/below the corresponding nodes.
2. Fix some order in which the edges will be processed, say $(1,2), (1,3), (2,5), (3,4), (5,6), (4,6), (2,3), (4,5)$. Perform relaxation $6-1=5$ times. For the sake of better understanding, we will explain only the first few iterations in detail. We notice that $d_2 = \infty > 3 = 0 + 3 = d_1 + w_{1, 2}$. Therefore, we update the value of $d_2$ by setting it equal to $3$. Analogously, we set $d_3 = 1$, as while relaxing along $(2,3)$ we end up with $d_3 = w_{1,3} = 4 > 1 = 3 + (-2) = d_2 + w_{2,3}$. Some of the edges will contribute nothing to our relaxation process. For example, while relaxing along $(4, 6)$, we get $d_6 = 10 < 11 = 3 + 8 = d_4 + w_{4, 6}$. All in all, we get $d_4 = 3, \; d_5 = 5, \; d_6 = 10$, as shown in picture 1.
3. The second iteration is done similarly. For example, we get a shorter path to the fourth node, as $d_4 = 3 > 0 = 1 + (-1) = d_3 + w_{3, 4}$. We continue until the fifth iteration is done. The distances for each iteration are shown in the pictures below:

   

4. Just in case, we check for the presence of negative cycles. Perform relaxation once again. We see that none of the values of $d_v$ changes, hence no negative cycles are found in our graph. The algorithm returns the array of shortest paths $d_v$. As we mentioned in the previous paragraph, it is quite easy to restore the paths themselves. Try it!

Example 2: 'Catch those negative cycles'

What if there are negative cycles? How does the algorithm detect them? Let's consider the following example:

We are given a graph consisting of $4$ nodes. As in the previous example, repeat relaxation $4-1=3$ times. Take the following ordering of edges: $(1, 3), (2, 3), (1, 2), (3, 4), (4, 2)$. The results are shown in the images below.

The final step: checking for our main enemy $-$ negative cycles. Perform relaxation one more time. We notice a change in the weight of the shortest path to nodes $2,3$ and $4$.

This means that the algorithm has detected the presence of a negative cycle. Indeed, we can all see it standing right in front of us, can't we? The algorithm can be easily modified to explicitly return the cycle itself using the backtracking method.

Pseudocode

Having explored the Bellman-Ford algorithm in the preceding sections, we now delve into its practical implementation through pseudocode. The Bellman-Ford algorithm stands as a robust tool for finding shortest paths in weighted directed graphs, addressing even the challenge of negative cycles. Let's articulate its procedural details to enhance our understanding of its application in various scenarios.

// Function to perform Bellman-Ford algorithm on a weighted directed graph
function bellmanFord(graph, source):
    // Step 1: Initialize distances
    distances = new Map<Node, Integer>()
    predecessors = new Map<Node, Node>()

    for each node in graph.nodes:
        distances.put(node, INFINITY)
        predecessors.put(node, null)

    distances.put(source, 0)

    // Step 2: Relaxation process
    for i in [1, graph.nodes.size() - 1]: // for loop iteration (|graph.nodes| - 1) times
        for each edge in graph.edges:
            if relax(edge) == false:
                // Negative cycle detected, stop the algorithm
                print("Negative cycle detected. Unable to find shortest paths.")
                return

    // Step 3: Check for negative cycles
    for each edge in graph.edges:
        if relax(edge) == true:
            // Negative cycle detected
            print("Negative cycle detected. Unable to find shortest paths.")
            return

    // Function to perform relaxation along an edge
    function relax(edge):
        u = edge.source
        v = edge.target
        weight = edge.weight

        if distances[u] + weight < distances[v]:
            distances[v] = distances[u] + weight
            predecessors[v] = u
            return true  // Relaxation successful
        else:
            return false  // Relaxation unsuccessful

    // Function to restore the shortest path
    function restorePath(node):
        path = new List<Node>()
        while node != null:
            path.add(node)
            node = predecessors[node]
        return reverse(path)

// Example usage
sourceNode = graph.getNode(1)
bellmanFord(graph, sourceNode)

Complexity Analysis

For a graph with $|V| = n$ nodes and $|E| = m$ edges, the time complexity of Bellman-Ford is $O(n\cdot m)$. Indeed, we apply the process of relaxation $n-1$ times along every edge, i.e., $(n-1)\cdot m$ times. Afterward, we do one more step of relaxation along every edge. Relaxation consists of a single comparison, therefore its complexity is $O(1)$. Overall, our algorithm will perform $O(n\cdot m)$ steps.

Conclusion

Here is a brief summary of what we discussed in this topic. The Bellman-Ford algorithm is a powerful shortest path solving tool. Unlike some other algorithms, it works correctly for graphs containing negative cycles as well. It consists of three easily realizable steps:

1. Initialize the values of shortest paths.
2. Apply the relaxation process $|V|-1$ times to get the final weights of shortest paths from the source to every other node.
3. Relax along every edge one last time to check for negative cycles. If any changes are observed, confirm their presence.

For a more interactive example of how the algorithm works, check out a visualization.