Main Page | See live article | Alphabetical index

Floyd-Warshall algorithm

In computer science, the Floyd-Warshall algorithm is an algorithm to solve the all pairs shortest path problem in a weighted, directed graph by multiplying an adjacency-matrix representation of the graph multiple times. The edges may have negative weights, but no negative weight cycles. The time complexity is θ(V3).

The algorithm is based on the following observation: Assuming the vertices of a directed graph G are V = {1,2,3,4,.....,n}, consider a subset {1,2,3,...,k}. For any pair of vertices i,j in V, consider all paths from i to j whose intermediate vertices are all drawn from {1,2,...,k}, and p is a minimum weight path from among them. The algorithm exploits a relationship between path p and shortest paths from i to j with all intermediate vertices in the set {1,2,...,k-1}. The relationship depends on whether or not k is an intermediate vertex of path p.

Here is a pseudo-algorithm of the Floyd-Warshall algorithm:

W is a n-by-n matrix

FW(W) {
n <- rows[W];
D0 <- W;
for k <- 1 to n
  do for i <- 1 to n
     do for j <- 1 to n
        do dijk <- min(dijk-1, dikk-1+dkjk-1)
return Dn
}