Ford-Bellman algorithm

Ford-Bellman algorithm

The problem of shortest paths from an origin can only be solved if there is no reachable absorbing circuit. The Ford-Bellman algorithm verifies that there is no absorbing circuit reachable from s. If so, it returns the shortest paths from s. The Ford-Bellman algorithm is a algorithm of dynamic programming greedy which calculates shortest paths of increasing size. It is suitable for any graph.

Conditions.

  • General case

Initially, the distance is initialized to 0 for the origin and to infinity for the other vertices.

shortest path Ford-Bellman algorithm ford

We will examine all the arcs and improve the value of the paths if possible. The new value for each vertex is the minimum distance of all the paths of size k-1 to which we add the edges entering the vertex. As there may be circuits, you have to start over.

shortest path Ford-Bellman algorithm ford
shortest path Ford-Bellman algorithm

For practical reasons, solving the Ford-Bellman algorithm only returns a vector. This corresponds to a current column of the table presented.

Optimality.

The shortest path from the origin to itself is 0. Then the paths of size 1 are calculated such that we only keep the shortest way from the origin to any other vertex.

the algorithm calculates the shortest paths of paths of size k (for iteration k) from the shortest paths of paths of size k-1, so it is optimal regardless of the stop iteration of the algorithm.

If there is not this absorbing circuit, a shorter path is necessarily elementary. We are therefore sure that a shorter path must then be found in at most n-1 steps of the iteration. If a value of D is improved, it means that there is an absorbing circuit.

for each vertex u of the graph d [u, 0] = + ∞ d [s, 0] = 0
for k = 1 up to Number of vertices - 1 to do
    for each arc (u, v) of the graph to do
        d [v, k]: = min (d [v, k-1], d [u, k-1] + weight (u, v))
    end
end
return d

Example

Let us take the following graph as an example:

shortest path Ford-Bellman algorithm ford

Let us take node 5 as the source, then we initialize the other distances to infinity. The vector π represents the predecessors.

shortest path Ford-Bellman algorithm ford

Iteration 1: Bows (u5,u2) and (u5,u4) are relaxed, we update distances and predecessors.

shortest path Ford-Bellman algorithm ford

Iteration 2: Bows (u2,u1), (u4,u2) and (u4,u3) are relaxed, we update the distances to nodes 1, 2, and 4. Note that (u4,u2) finds a shorter path to 2 through node 4.

shortest path Ford-Bellman algorithm ford

Iteration 3: Bows (u2,u1) are relaxed (because we found a shorter path to go to node 2 in the last iteration).

shortest path Ford-Bellman algorithm ford

Iteration 4: No arc is relaxed.

shortest path Ford-Bellman algorithm ford

The shortest paths starting from node 5 are:

shortest path Ford-Bellman algorithm ford

The algorithm is presented in the form of a table as below:

Iteration12345
0infinfinfinf0
1inf4(5)inf2(5)0
27(2)3(4)3(4)2(5)0
36(2)3(4)3(4)2(5)0
46(2)3(4)3(4)2(5)0

The distances in red show the nodes that have undergone a change in the current iteration. For the following iteration, the arcs coming from these nodes must therefore be relaxed. The algorithm stops when there is no more change.