Floyd Warshall algorithm (transitive closure)

Contents

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 as source. Can we do better? In Floyd Warshall's algorithm, we assume that we have access to a graph with n vertices as n² adjacency matrix.

Floyd Warshall's 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 can 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.

Extended general case

We suppose that the vertices of G are {1, 2, 3, 4, ..., not}. It successively solves the following sub-problems:

W^k_ij is the minimum weight of a path from vertex i to vertex j borrowing only intermediate vertices in {1, 2, 3,…, k} if there is one, and ∞ otherwise. We denote by W^k the matrix of W^k_ij.

For k = 0, W⁰ is the adjacency matrix defining the graph.

shortest path floyd-warshall algorithm transitive closure

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

that is p do not take the summit k
that is p borrows exactly once the summit k and p is therefore the concatenation of two paths, between i and k and k and j respectively, whose intermediate vertices are in {1, 2, 3,…, k-1}.

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

The above observation gives the recurrence relation:

W^k_ij= min (W^k-1_ij, W^k-1_ik + W^k-1_{K J} ), for everyone i, j and k in {1, 2, 3, 4…, not}.

Thus we solve the subproblems by increasing value of k.

Which gives on the first two stages:

Example of the Floyd Warshall algorithm

The first matrix is the adjacent matrix then the shortest paths. The second matrix presents the predecessors. It is initialized by a value z which is equal to the number of the row if a value exists in the adjacency matrix (in the initial state). The matrix of predecessors is updated each time a value in (i, j) is modified. The corresponding value in (i, j) of the matrix of the predecessors is equal to the number of iterations (that is to say the value of the power of the matrix).

Optimality of the Floyd Warshall algorithm

Initially, we have the shortest size 1 trails starting from all peaks. Next, we compute the larger-sized paths through vertex 1, and we keep only the shortest paths. The new iteration therefore displays the shortest paths of size 1 and those of size 2 passing through the vertex 1. By induction, we deduce that the last matrix displays the shortest paths of size less than the number of vertices between any pair of vertices .

CODE W is the adjacency matrix
for k from 1 to n
   for i from 1 to n
      for j from 1 to n W^k_ij= min (W^k-1_ij, W^k-1_ik + W^k-1_{K J} )
      end
   end
end
return W