The problem of shortest paths from an origin has a solution unless there is an absorbable circuit. The Bellman-Ford algorithm verifies that there is no absorbent circuit that can be reached from s. If so, it returns the shortest paths from s. Bellman-Ford’s algorithm is a greedy dynamic programming algorithm that computes shortest paths of increasing size. It is suitable to any graph.
Initially, the distance is initialized to 0 for the origin and to infinity for the other vertices.
For practical reasons, the resolution of Ford’s algorithm only returns one array. It corresponds to a current column of the table presented.
Given the following directed graph:
Using vertex 5 as the source, we initialize all other distances to inf. is the array of predecessors.
Iteration 1: Edges (u5,u2) and (u5,u4) relax updating the distances to 2 and 4.
Iteration 2: Edges (u2,u1), (u4,u2) and (u4,u3) relax updating the distances to 1, 2, and 4 respectively. Note edge (u4,u2) finds a shorter path to vertex 2 by going through vertex 4.
Iteration 3: Edge (u2,u1) relaxes (since a shorter path to vertex 2 was found in the previous iteration) updating the distance to 1.
Iteration 4: No edges are relaxed
The final shortest path from vertex 5 with corresponding distances is
The algorithm can be computed in a single table as follows:
Elements in red denote an update in the current iteration, for the following iteration, all incident nodes from the selected ones are updated (by the min with the previous iteration). If the value changes, we mark it.