Floyd–Warshall algorithm
Algorithm for all-pairs shortest paths in weighted graphs.
The Floyd–Warshall algorithm is an algorithm in computer science for finding shortest paths in a directed weighted graph with positive or negative edge weights, provided there are no negative cycles. A single execution finds the lengths of shortest paths between all pairs of vertices, and versions of the algorithm can also be used for finding the transitive closure of a relation or widest paths between all pairs of vertices in a weighted graph. The algorithm is an example of dynamic programming. Its currently recognized form was published by Robert Floyd in 1962, though it is essentially the same as algorithms published by Bernard Roy in 1959 and Stephen Warshall in 1962 for finding transitive closure. It is also closely related to Kleene's algorithm for converting a deterministic finite automaton into a regular expression, differing in its use of a min-plus semiring. The modern formulation of three nested for-loops was first described by Peter Ingerman, also in 1962. The algorithm incrementally improves an estimate of the shortest path between two vertices until it is optimal, using a recursive formula that considers paths using an increasing set of intermediate vertices. It guarantees finding all shortest paths with a number of comparisons that is cubic in the number of vertices, even when the graph has many edges. The correct order of the triply nested loops is KIJ; incorrect orders like IJK and IKJ do not give correct solutions for some instances, though repeating them three times can yield correct results. The algorithm can detect negative cycles by checking the diagonal of the distance matrix after execution: a negative value on the diagonal indicates a negative cycle exists. When such cycles are present, there is no shortest path between vertices that form part of the cycle, as path lengths can become arbitrarily negative.
- field
- Computer science
- known_for
- All-pairs shortest path algorithm, transitive closure, widest paths
Lore & Background
The Floyd–Warshall algorithm, a dynamic programming method, finds shortest paths between all pairs of vertices in a directed weighted graph, handling positive or negative edge weights as long as no negative cycles exist. It incrementally improves an estimate of the shortest path between two vertices until optimal, using a recursive formula where the shortest path from i to j using only vertices up to k is the minimum of the path using vertices up to k-1 and the sum of paths from i to k and k to j using vertices up to k-1. The base case is the direct edge weight between vertices, or infinity if no edge exists. The algorithm executes in Θ(|V|³) comparisons, even with Θ(|V|²) edges. While it does not return path details, simple modifications allow path reconstruction. Versions also compute transitive closure of a relation or, in the Schulze voting system, widest paths. Published in its current form by Robert Floyd in 1962, it is essentially the same as algorithms by Bernard Roy (1959) and Stephen Warshall (1962) for transitive closure, and is related to Kleene's algorithm (1956) for converting deterministic finite automata to regular expressions, differing by using a min-plus semiring. The modern three nested loops formulation was first described by Peter Ingerman in 1962. The correct loop order is KIJ; incorrect orders (IJK, IKJ) require repeating three times to yield correct solutions. Negative cycles can be detected by checking if any diagonal entry of the distance matrix becomes negative after execution, indicating a cycle with negative total weight.
Reader's Guide
The Floyd–Warshall algorithm is significant as a foundational dynamic programming solution for the all-pairs shortest path problem. Its ability to handle positive or negative edge weights (without negative cycles) makes it versatile, though its Θ(|V|³) time complexity limits it to graphs of moderate size. Beyond shortest paths, the algorithm's variants serve other purposes: finding transitive closure of a relation and, in connection with the Schulze voting system, computing widest paths between all pairs of vertices. Its legacy lies in its simplicity, elegance, and broad applicability across graph theory, network analysis, and voting systems.
Did You Know?
- The algorithm is also known as Floyd's algorithm, the Roy–Warshall algorithm, the Roy–Floyd algorithm, or the WFI algorithm.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record