Floyd-Warshall algorithm
|
|
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 taken 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:
function fw(int[0..n,0..n] graph) {
var int[0..n,0..n] dist := graph
for k from 0 to n
for i from 0 to n
for j from 0 to n
if dist[i,j] > dist[i,k] + dist[k,j]
dist[i,j] = dist[i,k] + dist[k,j]
return dist
}
| Contents |
Implementations
References
- Robert W. Floyd: Algorithm 97 (SHORTEST PATH), in Communications of the ACM, 5(6), p. 345, 1962.
- Stephen Warshall: A Theorem on Boolean Matrices, in Journal of the ACM, 9(1), pp. 11-12, 1962.
See also
External links
- Interactive animation of Floyd-Warshall algorithm (http://www.pms.informatik.uni-muenchen.de/lehre/compgeometry/Gosper/shortest_path/shortest_path.html#visualization)de:Algorithmus von Floyd und Warshall