In Floyd-Warshall's triple loop, why must the intermediate-vertex loop k be outermost?
answer
- The loops are not three symmetric axes
- One index counts something the others do not
- Think about what is finished when a pass ends
- Sub-distances must be ready before they are read
- Wrong order inflates multi-hop distances silently
basics
~20 sThe k loop is outermost because each pass must finish adding waypoint k for every pair before k+1 begins. That preserves the invariant that D[i][j] holds the best cost using waypoints up to k; reordering leaves distances too large.
solid answer
~50 sThe recurrence is defined over a growing set of permitted intermediate vertices, and `k` indexes that set — so a full sweep of all pairs must complete for waypoint `k` before waypoint `k+1` is opened. Only then is the invariant true: after the `k`-th outer pass, `D[i][j]` is the cheapest `i`-to-`j` cost using intermediates drawn from `{0..k}`, which is exactly what the next pass relies on when it reads `D[i][k+1]` and `D[k+1][j]`. If `k` moves inside, some pair is asked about waypoint `k` while the sub-distances feeding that comparison have not themselves been completed, and multi-hop routes never get assembled. The values written are always lengths of real paths, so the failure is silent and one-directional: distances come out too large, never too small. Worse, on small or nearly complete test graphs the wrong order often produces correct numbers by luck.
code
pseudocode · 8 lines// D[i][j] pre-filled: 0 if i == j, edge weight if an edge exists, else INF
for k in 0..n-1
for i in 0..n-1
for j in 0..n-1
if D[i][k] + D[k][j] < D[i][j]
D[i][j] = D[i][k] + D[k][j]
// invariant after outer pass k:
// D[i][j] = cheapest i-to-j cost using intermediates only from {0..k}go deeper
Memorise the shape — waypoint loop outside, the two pair loops inside — and be able to say that the outer index is the vertex allowed as a stopover. That alone separates you from candidates who recite three loops with no meaning attached.
Explain the invariant in one sentence: after the pass for waypoint k, every cell holds the best cost using stopovers up to k. Then show the failure mode of breaking it, and why the wrong order only inflates distances rather than deflating them.
Treat this as a code-review question. Say what test would catch it, why the usual small fixtures do not, and why silently-too-large distances are worse than a crash in a service that routes on the result.
The lesson generalises: a dynamic program's loop nesting encodes its dependency order, and a reordering that looks like a harmless optimisation is a correctness change. Decide where that invariant is documented and asserted so the next reviewer does not have to rediscover it.
## The recurrence, stated precisely Write `d(i, j, k)` for the cheapest cost from `i` to `j` whose **intermediate** vertices all come from `{0, 1, ..., k}`. The endpoints themselves are never restricted. The recurrence is a two-way choice on whether vertex `k` is used as a stop: ``` d(i, j, k) = min( d(i, j, k-1), // best route that skips k d(i, k, k-1) + d(k, j, k-1) ) // best route that stops at k ``` with the base case `d(i, j, -1)` equal to the direct edge weight, zero on the diagonal, infinity otherwise. The final answer is `d(i, j, n-1)`. Two details make the split legitimate. First, a shortest route that uses `k` at all can be assumed to use it **exactly once** — visiting it twice would mean a cycle in between, and dropping that cycle cannot increase the cost when no negative cycles exist. Second, the two halves of such a route each use intermediates only from `{0..k-1}`, because `k` itself sits at the join, not inside either half. So both halves are already-solved subproblems of the previous layer. ## Why that forces the loop order The recurrence has three indices, so a literal implementation would keep one matrix per value of `k`. The standard implementation collapses them into a single matrix updated in place, and the collapse is only sound if the whole `k`-th layer is completed before the `k+1`-th begins. That is what putting `k` outermost buys: it is the layer counter of the dynamic program, not a third coordinate that can be permuted with the others. The in-place trick has a subtlety worth knowing: during the pass for waypoint `k`, the cells `D[i][k]` and `D[k][j]` are read while the same matrix is being written. This is safe because those particular cells cannot change during their own pass — improving `D[i][k]` would require routing from `i` to `k` through `k`, which adds a cycle of non-negative weight. So the values read from row `k` and column `k` are the same whether taken before or after the pass, and one matrix suffices. ## What actually breaks when k moves inside Suppose the loops are ordered `i`, `j`, `k`. Now the pair `(i, j)` is finalised against every waypoint before the algorithm has ever looked at other pairs. When it evaluates `D[i][k] + D[k][j]`, those two sub-distances may still be direct-edge values, because the pairs `(i, k)` and `(k, j)` have not had their own chance to improve yet. Routes needing three or more hops are simply never assembled, and the affected cells retain a larger value. The failure is **one-directional**: every value the algorithm writes is the total weight of some genuine path in the graph, so a mis-ordered run can only report distances that are too large, never too small. That is precisely what makes the bug dangerous in review — nothing crashes, no assertion trips, and a graph whose shortest paths happen to be one or two hops long returns correct numbers. Small hand-written test fixtures are exactly the graphs where the bug hides. There is one more trap for a reviewer. Iterating the mis-ordered triple loop repeatedly until nothing changes *does* converge to the correct distances — it degenerates into a fixed-point relaxation, each full repetition propagating routes at least one hop further. So someone who wrapped the wrong-order loop in a "repeat until stable" outer loop is not wrong, merely slower and harder to reason about. The single-pass version is correct only with `k` outermost. ## What is free to reorder The `i` and `j` loops may be swapped with each other with no effect on correctness: within one waypoint layer, the update to a cell `(i, j)` never depends on another cell in the same layer, for the row-`k`/column-`k` reason above. So there is exactly one constraint to remember — `k` first — and it comes straight from the meaning of the state. ## How to answer in review When a diff reorders these loops, do not argue from "that is how it is written in the book". Argue from the state: `k` is the size of the permitted-waypoint set, the layer must be complete before the next reads it, and the symptom of getting it wrong is silently inflated distances on multi-hop routes. Then ask for a test whose shortest path is at least three hops long, because that is the smallest graph that catches it.
- Can the i and j loops be swapped with each other?Yes, freely. Within one waypoint layer no cell's update depends on another cell updated in that same layer, because the values read from row `k` and column `k` cannot change during their own pass. So the order of the two inner loops is a performance question about traversal patterns, never a correctness one. Only `k` is pinned, and it is pinned by the meaning of the state.
- What is the smallest test graph that would catch a mis-ordered loop?One whose true shortest path between some pair needs at least three edges, with the cheap multi-hop route made of edges added in an unhelpful index order and an expensive or missing direct edge. Four vertices in a chain is usually enough. Graphs where every shortest path is one or two hops return correct answers under the wrong order, which is why hand-written fixtures miss the bug.
- The same triple loop with different operators solves another classic problem. Which?Transitive closure — reachability rather than distance. Keep a boolean matrix, initialise it to the direct edges, and replace the add-and-compare with `R[i][j] = R[i][j] OR (R[i][k] AND R[k][j])`. The waypoint argument is identical: `i` reaches `j` through some intermediate from the permitted set. It is the same O(V^3) shape with cheaper cells.
saying these in an interview costs you the question
- Says the three loops are interchangeable axes
- Claims a wrong order can report distances that are too small
- Justifies the order by convention rather than by the state
- Thinks the in-place matrix update is itself unsafe
- Expects a crash or an obvious symptom from the bug