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

Credited To

Robert W. Floyd, Pioneers
Source Wikipedia, Floyd-Warshall algorithm

In Field

Algorithms and Complexity Theory, Fields
Source Wikipedia, Floyd-Warshall algorithm

Invented By

Robert W. Floyd, Pioneers

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

Uses Design Technique

Dynamic Programming, Concepts
Sources
1. Floyd-Warshall Algorithm (Wikipedia)
  • Wikipedia infobox: time complexity cubic
    cubic
  • 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.
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.
  • In Field: Algorithms and Complexity Theory, Lead sentence
    Floyd-Warshall algorithm (also known as Floyd's algorithm, the Roy-Warshall algorithm, the Roy-Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no ne
  • In Group: Shortest Path Algorithms, Lead
    In computer science, the Floyd-Warshall algorithm (also known as Floyd's algorithm, the Roy-Warshall algorithm, the Roy-Floyd algorithm, or the WFI algorithm) is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles).
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.