|
In computer science, the Floyd-Warshall algorithm is an algorithm for solving the all-pairs shortest path problem in a weighted, directed graph (V, E) 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
}
Implementations
Implementation in C
External links
See also
|
