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.
Contact the MathWorld Team
Hamilton-laceable
graph
