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.
Initially, the distance is initialized to 0 for the origin and to infinity for the other vertices.
For practical reasons, solving the Ford-Bellman algorithm only returns a vector. This corresponds to a current column of the table presented.
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 (u5,u2) and (u5,u4) are relaxed, we update distances and predecessors.
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.
Iteration 3: Bows (u2,u1) 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:
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.