Floyd-Warshall algorithm

See this course in PDF

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.


  • 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. 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.

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.


The first matrix is the adjacency matrix and then the shortest paths. The second matrix presents the predecessors.


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 )
return W