History
Robert Floyd published the algorithm in 1962, building on ideas by Stephen Warshall, whose closely related algorithm handled transitive closure. The combined Floyd-Warshall name is now standard for the weighted shortest-path version.
Graph algorithms / interactive lesson
Floyd-Warshall Algorithm
Learn Floyd-Warshall step by step through an animated directed graph and distance matrix. Watch how each intermediate vertex k lets the algorithm improve all-pairs shortest-path distances.
University
Guided lesson
Snapshot 1/139
Left: directed weighted graph · Right: evolving distance matrix dist[i][j]
Decision timelineproblem
About the algorithm
Floyd-Warshall is a dynamic-programming algorithm for all-pairs shortest paths. It fills a distance matrix so that, at the end, every cell dist[i][j] contains the shortest path cost from vertex i to vertex j.
How it works
The algorithm uses three nested loops. The outer loop chooses an intermediate vertex k. For every ordered pair (i, j), it tests whether the route i → k → j is shorter than the currently known best distance from i to j. If it is, the cell is updated. The key invariant is that after finishing round k, every path may use only intermediates among the first k vertices. When the last round finishes, all vertices have been allowed, so the matrix is globally optimal.
Where it is used
Floyd-Warshall is used when you need shortest paths between every pair of vertices: routing analysis, transportation networks, reachability preprocessing, centrality metrics, transitive closure, and dense-graph dynamic programming problems.
Code companion
Connect each visual decision to an implementation pattern.
initialize dist from the adjacency matrix
initialize next for path reconstruction
for k from 0 to n - 1:
for i from 0 to n - 1:
for j from 0 to n - 1:
if dist[i][k] and dist[k][j] are reachable:
candidate = dist[i][k] + dist[k][j]
if dist[i][j] is unreachable or candidate < dist[i][j]:
dist[i][j] = candidate
next[i][j] = next[i][k]
return dist, next