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|3).
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.
