Contenus

Toggle## 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.

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.

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.

foreachvertex u of the graph d [u, 0] = + ∞ d [s, 0] = 0fork = 1up toNumber of vertices - 1to dofor eacharc (u, v) of the graphto dod [v, k]: = min (d [v, k-1], d [u, k-1] + weight (u, v))endendreturn d

## Example

Let us take the following graph as an example:

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

*Iteration** 1*: Bows (*u*_{5},*u*_{2}) and (*u*_{5},*u*_{4}) are relaxed, we update distances and predecessors.

*Iteration** 2*: Bows (*u*_{2},*u*_{1}), (*u*_{4},*u*_{2}) and (*u*_{4},*u*_{3}) are relaxed, we update the distances to nodes 1, 2, and 4. Note that (*u*_{4},*u*_{2}) finds a shorter path to 2 through node 4.

*Iteration** 3*: Bows (*u*_{2},*u*_{1}) are relaxed (because we found a shorter path to go to node 2 in the last iteration).

*Iteration** 4*: No arc is relaxed.

The shortest paths starting from node 5 are:

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

Iteration | 1 | 2 | 3 | 4 | 5 |

0 | inf | inf | inf | inf | 0 |

1 | inf | 4(5) | inf | 2(5) | 0 |

2 | 7(2) | 3(4) | 3(4) | 2(5) | 0 |

3 | 6(2) | 3(4) | 3(4) | 2(5) | 0 |

4 | 6(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.