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.

ford1

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.

ford2

ford3

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:

bellman1

Using vertex 5 as the source, we initialize all other distances to inf.   is the array of predecessors.

bellman2

Iteration 1: Edges (u5,u2) and (u5,u4) relax updating the distances to 2 and 4.

bellman3

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.

bellman4

Iteration 3: Edge (u2,u1) relaxes (since a shorter path to vertex 2 was found in the previous iteration) updating the distance to 1.

bellman5

Iteration 4: No edges are relaxed

bellman6

The final shortest path from vertex 5 with corresponding distances is

bellman7

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.

Publicités