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 θ(V³).

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
}