See the course in PDF
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.
Initially, the distance is initialized to 0 for the origin and to infinity for the other vertices.
We will examine all the arcs and, if possible, improve the value of the paths. The new value for each vertex is the minimum distance of all paths of size k-1 to which we add the edges entering in the cooresponding vertex. As there can be circuits, we must start again.
For practical reasons, the resolution of Ford’s algorithm only returns one array. It corresponds to a current column of the table presented.
The shortest path from origin to itself is 0. Then size 1 paths are calculated so that we keep only the shortest path from the origin to any other vertex.
The algorithm calculates the shortest paths of the k-sized paths (for the iteration k) from the shortest paths of the k-1 size paths, it is therefore optimal whatever the stopped iteration of the algorithm.
If there is not this absorbing circuit, a shorter path is necessarily elementary. It is therefore certain that a shorter path must then be found in at most n-1 stages of iteration. If a value of D is improved, there is an absorbing circuit.
For each vertex u of the graph
d[u, 0] = +∞
d[s, 0] = 0
For k = 1 to Number of vertices - 1 do
For each arc (u, v) do
d[v, k] := min(d[v, k-1], d[u, k-1] + weight(u, v))