Visual walkthrough — Floyd-Warshall — all-pairs shortest paths, O(V³)

Before line one, three plain words you must own:

Our whole goal: for every ordered pair of cities $(i,j)$, find the cheapest total to get from $i$ to $j$. That cheapest number we will call $d(i,j)$.

Step 1 — Draw the map and read off the "no-stopping" costs

WHAT. We start with a tiny map: four cities $0,1,2,3$ and some one-way arrows with weights. We build a table whose cell in row $i$, column $j$ holds the best cost we currently know from $i$ to $j$.

WHY. Before we let ourselves get clever with detours, we can only trust what we can see directly: a single arrow, or staying put (cost $0$). Everything else we don't yet know — we mark it $\infty$ ("unreachable so far"). This honest starting table is the seed the whole algorithm grows from.

PICTURE. In the figure, the map is on the left, the table on the right. Green cells are the $0$ diagonal (staying home is free). Blue cells are direct arrows. Gray $\infty$ cells are pairs with no direct arrow yet.

Step 2 — Invent the subscript: "which cities am I allowed to stop at?"

WHAT. We give the subscript on $d$ a precise meaning. Define $d_k(i,j)$ = the cheapest cost from $i$ to $j$ if the only cities you may stop at along the way are $\{0,1,\dots ,k-1\}$. (Endpoints $i$ and $j$ don't count as "stops" — you always may start and end where you must.)

WHY. This is the trick that turns a huge problem into a ladder of tiny ones. Instead of solving "best path using anything," we solve a sequence: best path using no stops, then allowing stop $0$, then also $1$, then also $2$… Each rung reuses the rung below. This is the Dynamic Programming idea — see Dynamic Programming — solve a small version, then let the allowed set grow by exactly one.

PICTURE. The figure shows the SAME pair $(i,j)$ three times. On the left only direct hops are legal (a padlock on every middle city). In the middle, city $0$ is unlocked — a new detour becomes possible. On the right, city $1$ is unlocked too. The set of "keys you hold" grows left to right.

So $d_0$ (Step 1) allows no stops, and once every city is unlocked we will have the true answer. The whole algorithm is just: turn one padlock at a time.

Step 3 — Unlock ONE new city: the only two things that can happen

WHAT. Suppose we already have $d_k$ (cities $\{0,\dots ,k-1\}$ unlocked) and now we unlock city $k$. We want $d_{k+1}(i,j)$. Look at the truly-best route that is now legal. City $k$ is either used by that route, or it is not.

WHY. These two cases are exhaustive — there is no third option. So the new best must be the cheaper of the two. That "cheaper of two" is exactly what the symbol $\min$ means: $\min (a,b)$ = whichever of $a,b$ is smaller.

PICTURE. Top path: it ignores $k$ — so it was already legal before, cost $d_k(i,j)$ (orange). Bottom path: it goes through $k$ — pictured as $i\to k$ (blue) then $k\to j$ (green), cost $d_k(i,k)+d_k(k,j)$. We keep whichever is shorter.

Step 4 — Why is it legal to split the detour into two OLD problems?

WHAT. In the detour case we claimed each half ($i\to k$ and $k\to j$) may itself use only $\{0,\dots ,k-1\}$ as stops — i.e. each half is a problem we already solved. Why can we say that?

WHY. Because the best detour visits $k$ exactly once. If it visited $k$ twice, the chunk between the two visits is a loop starting and ending at $k$; as long as there are no Negative Cycles a loop only adds cost, so deleting it makes the path cheaper — contradicting "best." With $k$ visited once, cut the path at that single $k$: the first half never touches $k$ again, so its only stops are older cities. Same for the second half. Each half is a $d_k$ value — the recurrence closes on itself perfectly.

PICTURE. Left: a "bad" imagined route that loops back through $k$ twice — the red loop is wasted cost. Right: snip the loop out; now $k$ is touched once and the two clean halves each live entirely in the older allowed set.

Step 5 — Watch the table fill: a full numeric run

WHAT. Take four cities with arrows $0\to 1=3$, $0\to 3=7$, $1\to 2=2$, $2\to 3=1$. We turn the padlocks $k=0,1,2,3$ and watch cells drop.

WHY. Seeing real numbers relax convinces you the ladder actually works — abstract $\min$ becomes "5 became 4."

PICTURE. Four side-by-side tables, one per unlock. A cell turns orange the moment it improves. Trace $d(0,3)$: starts at $7$ (direct), and after enough padlocks the route $0\to 1\to 2\to 3=3+2+1=6$ wins.

Term-by-term for the winning update at $k=2$ (unlocking city $2$): $d(0,3)\leftarrow \min (\underset{\text{old }0\to 3}{\underbrace{7}},\underset{=5,0\to 1\to 2}{\underbrace{d(0,2)}}+\underset{=1}{\underbrace{d(2,3)}})=\min (7,6)=6$

• the $7$ is the direct arrow $0\to 3$;
• the $5$ is $0\to 1\to 2$, already found when city $1$ was unlocked;
• the $1$ is the arrow $2\to 3$;
• $\min$ swaps $7$ for $6$. The cell flips orange.

Step 6 — WHY the $k$-loop must be OUTERMOST (the ordering trap)

WHAT. The code is three nested loops. It is tempting to think order doesn't matter. It does: $k$ (the padlock) must be the outer loop; $i$ and $j$ inner.

WHY. The ladder is only valid because, when we unlock $k$, every pair $(i,j)$ already reflects the full set $\{0,\dots ,k-1\}$. If $k$ were an inner loop, you'd unlock city $k$ for pair $(0,1)$ but not yet for pair $(0,2)$ — reading a half-finished table. The subscript ladder would collapse.

PICTURE. Two runs of the same graph. Left: k outermost → the correct final table. Right: k innermost → a red WRONG cell where a value was read before it was ready.

for k in range(n):        # PADLOCK first — unlock one city fully
    for i in range(n):    # every origin...
        for j in range(n):#   every destination...
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

Step 7 — The degenerate cases: negatives, the diagonal, and $\infty$

WHAT. Three edge cases the pictures must cover, or you'll trip on them.

1. A negative edge (allowed). $\min$ never inspects the sign of an edge — it only compares totals. So a cheap-but-negative arrow is used automatically. This is why Floyd-Warshall beats running Dijkstra's Algorithm per source (Dijkstra breaks on negatives) and matches Bellman-Ford without its per-source cost.
2. A negative cycle (forbidden — "shortest" stops meaning anything). Detect it: after the run, if any diagonal cell $d(i,i)<0$, then leaving home and returning cost less than zero — a loop that pays you. That can only be a negative cycle.
3. Unreachable pairs stay $\infty$. In real code use a large sentinel (not literal infinity) and skip relaxation when either half is the sentinel, so $\infty +\infty$ doesn't overflow into a fake shortcut.

WHY. Case 1 is the whole reason to prefer this algorithm; case 2 is its built-in safety alarm; case 3 is the trap that silently corrupts answers in real code.

PICTURE. Left panel: a negative edge $1\to 2=-3$ making the detour $0\to 1\to 2$ beat the direct $0\to 2$. Right panel: a $-1$ triangle $0\to 1\to 2\to 0$; the diagonal cell $d(0,0)$ slides to $-1$ — the red alarm.

The one-picture summary

Everything above is one loop: turn a padlock, then for every pair ask "does the newly-open city shorten this trip?" — repeated until all padlocks are open.