| • Science | • People | • Locations | • Timeline |
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 }
This is also called the All-Pairs-Shortest-Path(APSP) algorithm.