The Floyd–Warshall algorithm is an algorithm for solving the all-pairs shortest-path problem in a weighted graph. It uses dynamic programming to compute a matrix of shortest-path distances, progressively allowing more vertices to serve as intermediate stops. For a graph with vertices, its standard implementation takes time and space. It supports directed graphs and negative edge weights, provided that no negative-weight cycle lies on a route for which a finite shortest-path distance is required.
Problem and representation
Let be a directed graph whose vertices are numbered . Each edge has a weight , representing a cost, distance, or other additive quantity. The task is to determine the minimum total weight of a route from every vertex to every vertex .
The algorithm stores these values in an matrix. Initially:
- Each diagonal entry is zero, representing the empty path from a vertex to itself.
- Each existing edge contributes its weight to the corresponding entry.
- An entry is if there is no direct edge.
- If parallel edges exist, only their minimum weight is needed.
- A negative-weight self-loop must be preserved rather than overwritten with zero.
Equivalently, initialize all entries to , set the diagonal to zero, and then take the minimum with every edge weight.
Undirected graphs can be represented by including both directions of each edge. However, a negative-weight undirected edge permits a negative closed walk by traversing the edge in both directions. Consequently, ordinary shortest-walk distances are unbounded below for pairs that can reach and leave that edge.
Dynamic programming recurrence
The essential idea is to restrict which vertices may appear inside a path, excluding its two endpoints.
Define as the shortest distance from to when intermediate vertices may only come from the set . The initial matrix contains direct-edge distances and the zero-length diagonal paths.
When vertex becomes available as an intermediate vertex, a shortest path either:
- Does not use , so its distance remains ; or
- Uses , splitting into a path from to and another from to .
This gives the recurrence
After processing all vertices, contains all shortest-path distances, assuming there are no negative-weight cycles.
The correctness argument uses a loop invariant: after iteration , the matrix contains optimal distances among paths whose intermediate vertices belong to the first vertices. In the absence of negative cycles, a shortest route can be chosen without repeated vertices, which justifies splitting a route at a single occurrence of .
Standard implementation
The recurrence appears to require a separate matrix for every stage, but the standard algorithm updates one matrix in place. The following pseudocode includes reachability checks to avoid adding an infinity sentinel:
dist = n × n matrix filled with INF
for i = 1 to n:
dist[i][i] = 0
for each edge (u, v, weight):
dist[u][v] = min(dist[u][v], weight)
for k = 1 to n:
for i = 1 to n:
if dist[i][k] == INF:
continue
for j = 1 to n:
if dist[k][j] == INF:
continue
candidate = dist[i][k] + dist[k][j]
if candidate < dist[i][j]:
dist[i][j] = candidate
Without negative cycles, the pivot diagonal remains zero. Updating through therefore does not change the pivot row or column, making in-place evaluation consistent with the recurrence.
The loop over must remain the outermost loop in this standard one-pass formulation. The loops over and may be exchanged. Moving inside either of them generally breaks the dynamic programming invariant and may produce incorrect results.
Example
Consider three vertices with directed edges of weight , of weight , and of weight . The initial matrix is
When vertex becomes available as an intermediate vertex, the algorithm discovers
The resulting matrix is
Thus, the shortest route from to goes through , despite the existence of a direct edge.
Negative cycles
Negative edges alone do not invalidate the algorithm. A negative cycle, whose edge weights sum to a negative value, causes a different problem: repeatedly traversing it makes a route's total weight arbitrarily small.
After the standard computation, a negative diagonal entry,
indicates the presence of a negative cycle. A graph contains a negative cycle if and only if at least one diagonal entry is negative after Floyd–Warshall completes, assuming exact arithmetic.
Not every source–destination pair is necessarily affected. The distance from to is unbounded below if there is some vertex such that
Such pairs can be marked as having distance . This marking is a separate postprocessing step; the ordinary relaxation loop does not itself produce a complete matrix of negative-infinity values.
An implementation must distinguish three outcomes:
- A finite shortest-path distance.
- , meaning the destination is unreachable.
- , meaning reachable negative cycles make the route cost unbounded below.
Reconstructing paths
The distance matrix alone does not directly record the corresponding routes. Path reconstruction can be supported with an additional matrix, often called a next-hop matrix.
For each direct edge , initialize . Whenever a strict improvement through is found, update
To reconstruct a route from to , repeatedly follow the next-hop entry toward . Unreachable pairs have no next hop, and pairs affected by negative cycles do not have a finite shortest route.
Using strict improvement avoids unnecessary changes between equal-length alternatives. The extra matrix requires space, and reconstructing one finite shortest path takes time proportional to the number of vertices it contains.
Complexity and practical considerations
The standard three nested loops perform distance comparisons. Its time complexity does not improve merely because the input graph has few edges. The distance matrix requires space, whether or not actual paths are also stored.
These bounds count arithmetic and comparisons as constant-time operations. If weights require arbitrary-precision arithmetic, the cost of operating on their representations must also be considered.
Several implementation details are important:
- Infinity representation: A finite sentinel must exceed every relevant finite distance. Sentinel values should not be added as though they were ordinary weights.
- Overflow: Even finite operands may produce integer overflow, especially when negative cycles cause repeated decreases.
- Floating-point arithmetic: Rounding can affect comparisons and the classification of nearly zero-weight cycles.
- Memory access: The contiguous traversal of matrix rows can improve CPU cache utilization.
- Blocking: Partitioning the matrix into tiles can improve locality, but pivot tiles and dependent row and column tiles must be processed in an order that preserves dependencies.
- Parallel execution: Parallel computing can accelerate updates within appropriately synchronized stages. Arbitrarily distributing all iterations without respecting pivot dependencies is not equivalent to the algorithm.
Related algorithms and extensions
Warshall's transitive-closure algorithm
Replacing numerical distances with Boolean reachability gives the closely related algorithm for transitive closure:
Here, records whether is reachable from . Initializing the diagonal to true includes zero-length paths and produces reflexive transitive closure; leaving it initially false instead records reachability by positive-length paths, with diagonal entries becoming true when cycles exist.
The numerical shortest-path version uses minimum and addition where the Boolean version uses logical OR and AND.
Comparison with other shortest-path methods
Dijkstra's algorithm solves the single-source problem with nonnegative edge weights. Repeating it from every vertex is often preferable on sparse graphs.
The Bellman–Ford algorithm permits negative edges and detects reachable negative cycles from a single source, but repeating it for all sources is often more expensive than Floyd–Warshall.
Johnson's algorithm combines Bellman–Ford reweighting with repeated Dijkstra searches. It supports negative edges when there are no negative cycles and is often better suited to sparse all-pairs problems.
Floyd–Warshall remains useful for dense graphs, moderate-sized inputs, and applications requiring a complete distance matrix. Examples include distance-table preprocessing, analysis of weighted networks, and checking systems of difference constraints.
Historical development
The algorithm's history includes several closely related formulations. Bernard Roy published a related path-finding method in 1959. In 1962, Stephen Warshall published a Boolean-matrix algorithm for transitive closure, while Robert W. Floyd published the numerical shortest-path formulation.
The compound name Floyd–Warshall reflects the shared intermediate-vertex recurrence. Names including Roy acknowledge the earlier contribution, although naming conventions vary across textbooks and software libraries.