Floyd-Warshall Algorithm

The Floyd-Warshall algorithm, also variously known as Floyd's algorithm, the Roy-Floyd algorithm, the Roy-Warshall algorithm, or the WFI algorithm, is an algorithm for efficiently and simultaneously finding the shortest paths (i.e., graph geodesics) between every pair of vertices in a weighted and potentially directed graph.

The Floyd algorithm is essentially equivalent to the transitive closure algorithm independently discovered by Roy (1959) and Warshall (1962) (Pemmaraju and Skiena 2003), which is the reason it is associated with all three authors.

In Season 4 episode "Black Swan" of the television crime drama NUMB3RS, mathematical genius Charles Eppes proposed using the Floyd-Warshall algorithm to analyze the most recent destinations of a bombing suspect.

REFERENCES

Atallah, M. J. (Ed.). "Basic Graph Algorithms." Ch. 6 in Algorithms and Theory of Computation Handbook. Boca Raton, FL: CRC Press, 1998.

Floyd, R. W. "Algorithm 97." Comm. ACM 5-6, 345, 1962.

Larson, R. and Odoni, A. "Shortest Paths between All Pairs of Nodes." §6.2.2 in Urban Operations Research. 1981. http://web.mit.edu/urban_or_book/www/book/chapter6/6.2.2.html.

Loerch, U. "Floyd's Algorithm." Auckland, New Zealand: Dept. Computer Science, University of Auckland, 2000. http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/node21.html.

Pemmaraju, S. and Skiena, S. "All-Pairs Shortest Paths" and "Transitive Closure and Reduction." §8.1.2 §8.5.2 in Computational Discrete Mathematics: Combinatorics and Graph Theory in Mathematica. Cambridge, England: Cambridge University Press, pp. 330-331 and 353-356, 2003.

Preiss, B. "Floyd's Algorithm." in Data Structures and Algorithms with Object-Oriented Design Patterns in Java. 1998. http://www.brpreiss.com/books/opus5/html/page570.html.Roy, B. "Transitivité et connexité." C. R. Acad. Sci. Paris 249, 216-218, 1959.

Warshall, S. "A Theorem on Boolean Matrices." J. ACM 9, 11-12, 1962.