Computing Atlas

How Computing Was Built
Sign In
Text size
100%
Theme

Switch Atlas

Algorithm

Floyd-Warshall Algorithm

Graph Algorithm

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
Time Complexity
Time Complexity (category)
Cubic Time -- O(n^3) 1
Classification
Design Technique
Dynamic Programming 1
Credited To
Robert Floyd (1962) 2
Connections

Invented

Robert W. Floyd, Pioneers

Robert W. Floyd published the all-pairs shortest path algorithm in 1962, building on a related result by Stephen Warshall.

Sources
1. Floyd-Warshall Algorithm (Wikipedia)
  • Wikipedia infobox: time complexity cubic
    cubic
  • Wikipedia: design technique dynamic-programming
    dynamic-programming
View the Source
2. 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 Source
Wikidata: Floyd-Warshall Algorithm
Wikidata Q1047576, class allow-list match (w-wdresolver-0926)View the Source
Comments (0)
No comments yet. Be the first to share a thought.
Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.