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 edgess may have negative weights, but no negative weight cycless. The time complexity is Θ(|V|³). The algorithm is based on the following observation: Assuming the verticess 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 n <- rows[W];\n D0 <- W;\n for k <- 1 to n\n   do for i <- 1 to n\n      do for j <- 1 to n\n         do dijk <- min(dijk-1, dikk-1+dkjk-1)\n return Dn\n }

\nThis is also called the All-Pairs-Shortest-Path(APSP) algorithm.

External links

\n* Interactive animation of Floyd-Warshall algorithm Category:Graph algorithms