Floyd-Warshall Algorithm
Software Engineer path · lesson 26 of 99Find shortest paths between ALL pairs of vertices. Works with negative weights (but no negative cycles). Simple triple-nested loop.
Directed and weighted. Keep it to 6 nodes or fewer so the matrix stays readable.
Start with direct edge weights; ∞ where there is no edge.
- 1d[i][j] = w(i, j), d[i][i] = 0, else ∞
- 2for k in nodes:
- 3 for i in nodes:
- 4 for j in nodes:
- 5 if d[i][k] + d[k][j] < d[i][j]: d[i][j] = d[i][k] + d[k][j]
- Checks
- 0 / 15
- Improvements
- 0 / 7
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
All pairs, one vertex at a time
Order how Floyd-Warshall fills the distance matrix.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
- 1Drop a step here
- 2Drop a step here
- 3Drop a step here
- 4Drop a step here
- 5Drop a step here
Test your knowledge
What is the recurrence relation in Floyd-Warshall?
The short version
Imagine finding shortcuts between cities. For each intermediate city K, you check: 'Is going through K faster than the direct route?' You do this for EVERY pair of cities, considering EVERY possible intermediate stop.
In more depth
The Triple Loop
for k in 0..n:
for i in 0..n:
for j in 0..n:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Key Insight
The outermost loop (k) represents: "Consider paths that go through nodes 0, 1, ..., k"
Use Cases
When to reach for this
- Need shortest path between ALL pairs
- Graph is small (V ≤ 400)
- Graph is dense (many edges)
- Transitive closure queries
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required