From Wikipedia, the free encyclopedia

Graph search algorithms
Search A* Bellman-Ford algorithm Best-first search Bidirectional search Breadth-first search Depth-first search Depth-limited search Dijkstra's algorithm Floyd-Warshall algorithm Iterative deepening depth-first search Johnson's algorithm Uniform-cost search

In computer science, the Floyd–Warshall algorithm (sometimes known as the Roy–Floyd algorithm, since Bernard Roy described this algorithm in 1959) is an algorithm for solving the all-pairs shortest path problem on weighted, directed graphs in cubic time.

Contents 1 Algorithm 1.1 Analysis 2 Applications and generalizations 3 Implementations 4 References 5 See Also 6 External links

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 Θ(n³) (see the Analysis below for details). 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.

Let be the zero-one matrix that has a "1" in its (i,j) position there is a path from v_i to v_j with interior vertices from the set {v₁,v₂,...,v_k}. Then , whenever i, j, and k are positive integers not exceeding n. Therefore, we can efficiently compute the matrices , k = {12...n}. Example psuedocode 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)

procedure Warshall ( :  zero-one matrix)

for k: = 1 to n
begin
    for i: = 1 to n
    begin
        for j: = 1 to n
        
   end
end

To find all n² of from those of requires 2n² bit operations. Since we begin with and compute the sequence of n zero-one matrices , , ..., , the total number of bit operations used is .

The Floyd-Warshall algorithm can be used to solve the following problems, among others:

• Shortest paths in directed graphs (Floyd's algorithm).
• 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.

• 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

• 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", in 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.
• Kenneth H. Rosen (2003). Discrete Mathematics and Its Applications, 5th Edition.. Addison Wesley. ISBN 0-07-119881-4 (ISE).

• Robert Floyd
• Stephen Warshall

• Analyze Floyd's algorithm in an online Javascript IDE
• Interactive animation of Floyd-Warshall algorithm