A dynamic-programming algorithm that computes the shortest path between every pair of vertices in a weighted graph at once, running in cubic time in the number of vertices regardless of how many edges the graph has.
Facts
Classification
Design Technique Connections
Invented
Robert W. Floyd published the all-pairs shortest path algorithm in 1962, building on a related result by Stephen Warshall.
Sources
1. Wikipedia, Floyd-Warshall algorithm
History and naming
The Floyd-Warshall algorithm is an example of dynamic programming, and was published in its currently recognized form by Robert Floyd in 1962.
entity record, description (design-technique)
A dynamic-programming algorithm that computes the shortest path between every pair of vertices in a weighted graph at once, running in cubic time in the number of vertices regardless of how many edges the graph has.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.