Floyd-Warshall Algorithm
Find shortest paths between ALL pairs of vertices. Works with negative weights (but no negative cycles). Simple triple-nested loop.
Floyd-Warshall Algorithm
Find shortest paths between ALL pairs of vertices. Works with negative weights (but no negative cycles). Simple triple-nested loop.
Initialize distance matrix (∞ means no direct edge)
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
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