Bellman-Ford algorithm

Bellman-Ford algorithm is a procedure used to find all shortest path in a graph from one source to all other nodes. The algorithm requires that the graph does not contain any cycles of negative length, but if it does, the algorithm is able to detect it.

The algorithm was introduced by American mathematicians Richard Bellman and Lester Ford.

Description

The Bellman-Ford algorithm is based on the relaxation operation. The relaxation procedure takes two nodes as arguments and an edge connecting these nodes. If the distance from the source to the first node () plus the edge length is less than distance to the second node, than the first node is denoted as the predecessor of the second node and the distance to the second node is recalculated ( distance(A) + edge.length ). Otherwise no changes are applied.

The path from the source node to any other node can be at maximum $\\vert V \\vert - 1$ edges long, provided there is no cycle of negative length. Hence if we perform for all nodes the relaxation operation $\\vert V \\vert - 1$ , than the algorithm will find all shortest paths. We will verify the output by running the relaxation once more – if some edge will be relaxed, than the algorithm contains a cycle of negative length and the output is invalid. Otherwise the output is valid and the algorithm can return shortest path tree.

Code

Pseudocode

function <predecessors> Bellman-Ford(G, source)
    for i in 1 to |U| do
        distance[i] = +inf
        predecessors[i] = null

    distance[source] = 0

    for i in 1 to (|U| - 1) do
        for each Edge e in Edges(G) do
            if distance[e.from] + length(e) < distance[e.to] do
                distance[e.to] = distance[e.from] + length(e)
                predecessors[e.to] = e.from
                
    for each Edge e in Edges(G) do
        if distance[e.from] + length(e) < distance[e.to] do
            error("Graph contains cycles of negative length")
    
    return predecessors

Complexity

The asymptotic complexity of Bellman-Ford algorithm is $O(\\vert V\\vert \\cdot \\vert E\\vert )$ , because the inner loop is performed $\\vert V \\vert - 1$ and the inner loop iterates over all edges of the graph.

Example