Floyd-Warshall All-Pairs
Shortest paths between every pair.
Floyd-Warshall All-Pairs is a free Coding Interview Prep lesson on CoddyKit — lesson 4 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Every Pair at Once
Sometimes you need the shortest path between every pair of nodes, not just from one source. That is the all-pairs problem.
Meet Floyd-Warshall
Floyd-Warshall fills a full distance table for all pairs with three tidy nested loops and almost no setup.
The Distance Matrix
Use a matrix where dist[i][j] is the best known cost from i to j. Start it from the direct edges you are given.
dist = [[INF] * n for _ in range(n)]Set the Diagonal
Every node reaches itself for free, so set the diagonal dist[i][i] to zero before you begin relaxing.
for i in range(n):
dist[i][i] = 0The Intermediate Idea
The trick: allow paths to pass through an intermediate node k, then ask if routing via k is cheaper than going direct.
Loop Order Matters
The outer loop is k, the chosen midpoint. Inner loops i and j try every pair against that midpoint.
for k in range(n):
for i in range(n):
for j in range(n):The Relaxation Step
For each pair, relax through k: if i to k to j is shorter, update dist[i][j] to that combined cost.
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]Why k Goes Outside
By the time k finishes, all pairs may use intermediates up to k. Putting k outermost keeps that guarantee correct.
Negative Edges Are Fine
Floyd-Warshall accepts negative edges, just not negative cycles. A negative cycle leaves some diagonal entry below zero.
The Running Time
Three loops over n nodes give O(n^3) time and O(n^2) space, practical only when n stays a few hundred.
When to Choose It
Pick Floyd-Warshall when the graph is small and dense and you truly need every pairwise distance, not a single source.
Quick Check
Which loop must be the outermost in Floyd-Warshall?
Recap: Floyd-Warshall
Init a matrix, zero the diagonal, then loop k, i, j and relax through k. All-pairs shortest paths in O(n^3). 🧮
Frequently asked questions
Is the “Floyd-Warshall All-Pairs” lesson free?
Yes — the full text of “Floyd-Warshall All-Pairs” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Floyd-Warshall All-Pairs”?
Shortest paths between every pair. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 4 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Floyd-Warshall All-Pairs” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- Dijkstra with a Heap
- 0-1 BFS with a Deque
- Bellman-Ford & Negative Edges
- Floyd-Warshall All-Pairs