# Ford-Bellman algorithm

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.

Conditions.

• No restriction

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.

Optimality

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))
End
End
return d```

## Example

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:

 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

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.