Floyd-Warshall algorithm
From Wikipedia, the free encyclopedia
-
"Floyd's algorithm" redirects here. For cycle detection, see Floyd's cycle-finding algorithm.
| Graph search algorithms |
|---|
| Search |
In computer science, the Floyd-Warshall algorithm (sometimes known as the Roy-Floyd algorithm or Warshall's algorithm) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time.
Contents |
[edit] Algorithm
The Floyd–Warshall algorithm takes as input an adjacency matrix representation of a weighted, directed graph (V, E). The weight of a path between two vertices is the sum of the weights of the edges along that path. The edges E of the graph may have negative weights, but the graph must not have any negative weight cycles. The algorithm computes, for each pair of vertices, the minimum weight among all paths between the two vertices. The running time complexity is Θ(n3). 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.
Note that the pseudocode assumes the input graph is an adjacency matrix representation of a directed graph, with the value ∞ (infinity) as the weight between vertices which have no edge that directly connects them and 0 on the diagonal (distance from a vertex to itself)
function fw(int[1..n,1..n] graph) {
// Initialization
var int[1..n,1..n] dist := graph
var int[1..n,1..n] pred
for i from 1 to n
for j from 1 to n
pred[i,j] := nil
if (dist[i,j] > 0) and (dist[i,j] < Infinity)
pred[i,j] := i
// Main loop of the algorithm
for k from 1 to n
for i from 1 to n
for j from 1 to n
if dist[i,j] > dist[i,k] + dist[k,j]
dist[i,j] = dist[i,k] + dist[k,j]
pred[i,j] = pred[k,j]
return ( dist, pred ) // Tuple of the distance and predecessor matrices
}
[edit] Applications and generalizations
The Floyd-Warshall algorithm can be used to solve the following problems, among others:
- Shortest paths in directed graphs (Floyd's algorithm). For this to work, the weights of all edges are set to the same positive number. That number is usually chosen to be one, so that the weight of a path coincides with the number of edges along the path.
- Transitive closure of directed graphs (Warshall's algorithm). In Warshall's original formulation of the algorithm, the graph is unweighted and represented by a Boolean adjacency matrix. Then the addition operation is replaced by logical conjunction (AND) and the minimum operation by logical disjunction (OR).
- Finding a regular expression denoting the regular language accepted by a finite automaton (Kleene's algorithm)
- Inversion of real matrices (Gauss-Jordan algorithm).
- Optimal routing. In this application one is interested in finding the path with the maximum flow between two vertices. This means that, rather than taking minima as in the pseudocode above, one instead takes maxima. The edge weights represent fixed constraints on flow. Path weights represent bottlenecks; so the addition operation above is replaced by the minimum operation.
- Testing whether an undirected graph is bipartite.
[edit] Implementations
- A Perl implementation is available in the Graph module
- A Javascript implementation is available at Alex Le's Blog
- A Python implementation is available in the NetworkX package
[edit] References
- Cormen, Thomas H., Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms, first edition, MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
- Section 26.2, "The Floyd-Warshall algorithm", pp. 558–565;
- Section 26.4, "A general framework for solving path problems in directed graphs", pp. 570–576.
- Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM 5 (6): 345. DOI:10.1145/367766.368168.
- Kleene, S. C. (1956). “Representation of events in nerve nets and finite automata”, C. E. Shannon and J. McCarthy Automata Studies. Princeton University Press, pp. 3–42.
- Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM 9 (1): 11–12. DOI:10.1145/321105.321107.
