Finds shortest paths between all pairs of vertices
Time: O(V³)
Space: O(V²)
Use Case: All-pairs shortest paths, transitive closure
Algorithm Execution
Select an algorithm and generate steps to begin visualization
About Floyd-Warshall Algorithm
The Floyd-Warshall algorithm computes shortest paths between every pair of vertices in a weighted graph in a single run. It is a classic example of dynamic programming on graphs and handles negative edge weights as long as there are no negative cycles.
How it works
The algorithm iterates over every vertex k and asks, for every pair (i, j), whether the path from i to j improves by passing through k. The update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) is applied for all pairs, growing the set of allowed intermediate vertices one at a time. Three nested loops over the vertices give O(V cubed) time and O(V squared) space, which is practical for dense graphs of up to a few thousand nodes.
Applications
Floyd-Warshall answers all-pairs distance queries in route planning, computes the transitive closure of relations, finds graph diameters, and supports arbitrage detection across all currency pairs at once. It is a favorite interview topic for testing dynamic programming intuition on graphs.