1. k is outermost
k is the intermediate node allowed so far; it must be the outermost loop.
for (let k = 0; k < n; k += 1)Typorithm · medium
Floyd-Warshall
▷ Interactive algorithm labfloyd-warshallgraph-algorithmsall-pairsdynamic-programmingrelaxation
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Floyd-Warshall
Graph Algorithms
Compute all-pairs shortest paths with a triple loop, relaxing dist[i][j] through each intermediate node k, with k outermost.
Floyd-Warshall finds the shortest path between every pair of nodes in one pass.
It builds up the answer by allowing one more intermediate node k on each outer iteration.
For each pair (i, j) it checks whether routing through k beats the current best distance.
Preparing algorithm lab…
01
k must be the outermost loop.
02
Relax dist[i][j] through k.
03
Handles all pairs at once.
function floydWarshall(dist, n) {
for (let k = 0; k < n; k += 1) {
for (let i = 0; i < n; i += 1) {
for (let j = 0; j < n; j += 1) {
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
return dist;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Source i
i ranges over every possible source node.
for (let i = 0; i < n; i += 1)3. Target j
j ranges over every possible destination node.
for (let j = 0; j < n; j += 1)4. Relax through k
Going i to k to j may be shorter than the current best i to j.
if (dist[i][k] + dist[k][j] < dist[i][j])5. Update
Record the shorter path that routes through intermediate node k.
dist[i][j] = dist[i][k] + dist[k][j]A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.