Floyd-Warshall Algorithm
All-pairs shortest-path algorithm
The Floyd-Warshall algorithm is a dynamic-programming algorithm that computes the shortest paths between all pairs of vertices in a weighted graph, including graphs with negative edge weights (but no negative cycles).
Definition
The Floyd-Warshall algorithm is a dynamic-programming algorithm that computes the shortest paths between all pairs of vertices in a weighted graph, including graphs with negative edge weights (but no negative cycles).
Overview
Floyd-Warshall solves the all-pairs shortest path problem by progressively considering each vertex as a potential intermediate point on the path between every pair of vertices. It maintains a distance matrix initialized with direct edge weights (and infinity where no direct edge exists), then for each vertex k, checks whether routing through k produces a shorter path between every pair (i, j) than the currently known distance. After considering all vertices as intermediates, the matrix holds the shortest distance between every pair of vertices in the graph. The algorithm's elegance lies in its simplicity: it is expressed as three nested loops over all vertices, giving it a straightforward O(V^3) time complexity and O(V^2) space complexity for the distance matrix. This makes it well suited to dense graphs and smaller vertex counts, where its cubic complexity is acceptable, but less practical than running Dijkstra's algorithm from every vertex on large sparse graphs. Like Bellman-Ford, it can detect negative cycles, indicated by a negative value appearing on the diagonal of the resulting distance matrix. Floyd-Warshall is widely used in network routing analysis, transitive closure computation, and any scenario where shortest distances between every pair of nodes are needed simultaneously rather than from a single source. Variants of the algorithm can also reconstruct the actual shortest paths, not just their lengths, by tracking a predecessor matrix alongside the distance matrix. The algorithm is named after Robert Floyd and Stephen Warshall, who published related formulations in 1962, building on earlier work by Bernard Roy.
Key Concepts
- Computes shortest paths between all pairs of vertices simultaneously
- Uses dynamic programming with vertices as intermediate waypoints
- Runs in O(V^3) time and O(V^2) space using a simple distance matrix
- Handles negative edge weights, provided no negative cycle exists
- Detects negative cycles via negative values on the matrix diagonal
- Can be extended with a predecessor matrix to reconstruct actual paths
- Simple three-nested-loop implementation with no auxiliary data structures
- Well suited to dense graphs and transitive closure problems