Floyd-Warshall algorithm

We want to determine the shortest paths between all pairs of vertices. We could use Dijkstra of Bellman-Ford, with each vertex in turn as the source. Can we do better ? In the Floyd-Warshall algorithm, we assume we are access to a graph with n vertices as a n² adjacency matrix W.

The Floyd-Warshall algorithm takes as input a directed and valued graph, described by an adjacency matrix giving the weight of an arc when it exists and the value ∞ otherwise. The weight of a path between two vertices is the sum of the weights on the arcs constituting this path. The arcs of the graph may have negative weights, but the graph must not have a circuit of strictly negative weight. The algorithm calculates, for each pair of vertices, the minimum weight among all the paths between these two vertices.

Conditions.

  • No restriction

We suppose that the vertices of G are {1, 2, 3, 4, …, n}. the algorithm successively solves the following subproblems:

Wkij is the minimum weight of a path from vertex i to vertex j only taking intermediate vertices in{1, 2, 3, …, k} if it exists, ∞ otherwise. We note Wk the matrix of all Wkij.

For k = 0, W0 is the adjacency matrix.

FW1

To find a recurrence relation, we consider a path p between i and j of minimum weight whose intermediate vertices are in {1, 2, 3, …, k}:

  • either p does not borrow the vertex k
  • either p borrows only one time k and p is the sum of two paths, from i to k and from k to j.

Let p be a shortest path from i to j with all intermediate vertices in the set {1, . . . , k}. If k is not an intermediate vertex of p, then p is also a shortest path with all intermediate vertices in the set {1, . . . , k − 1}. If k is an intermediate vertex of p, then we decompose p into a path p1 between i and k, and a path p2 between k and j; they are shortest paths.

The above observation gives the recurrence relation:

Wkij=min( Wk-1ij, Wk-1ik + Wk-1kj ), for all i, j and k in {1, 2, 3, 4…, n}.

Thus we solve the sub-problems by increasing value of k.

dujap

The first matrix is the adjacency matrix and then the shortest paths. The second matrix presents the predecessors. It is initialized by a value z that is equal to the line’s number if a value exist in the adjacency matrix (at initial state). The predecessors matrix is updated each time a value at (i,j) is changed. The corresponding value at (i,j) of the predecessors matrix is equals to the number of iteration (i.e the value of the matrix’ power).

Optimality

Initially, we have the shortest size 1 paths starting from all the vertices. Next, we compute the next higher-order paths through vertex 1, and keep only the shortest paths. The new iteration displays the shortest paths of size 1 and those of size 2 passing through the vertex 1. By recurrence, we deduce that the last matrix displays the shortest path between any vertex pair .

W is the adjacency matrix
For k from 1 to n
   For i from 1 to n
      For j from 1 to n
          Wkij=min( Wk-1ij, Wk-1ik + Wk-1kj )
      end
   end
end
return W

 

Publicités