■ Floyd-Warshall

Picture a printed table of driving times between every pair of towns. You know the times on the direct roads, but some towns have no direct road, and sometimes a direct road is slow. Floyd-Warshall fills in the whole table by asking one simple question, over and over: "Could I get from town $i$ to town $j$ faster if I passed through some other town along the way?"

Name the pieces. Lay the towns out in a grid. Let $dist[i][j]$ be the best travel time found so far from $i$ to $j$. Start with the direct-road times: $dist[i][i]=0$, and "no road yet" counts as $\infty$. Now pick one town $k$ and let it be a possible stopover. For every pair $(i,j)$, compare the route you already have against the detour that goes through $k$: $$dist[i][j] \;\leftarrow\; \min\big(dist[i][j],\; dist[i][k] + dist[k][j]\big).$$ Worked number: suppose the direct road A→B takes 9, but A→C takes 4 and C→B takes 3. Going through C costs $4+3 = 7$, which beats 9, so $dist[A][B]$ drops from 9 to 7.

The trick is the order. Wrap that one-line update in three nested loops, with the stopover $k$ on the OUTSIDE: "for each $k$, then for every $i$, then every $j$." This gives a dynamic-programming guarantee: after the $k$-th pass, $dist[i][j]$ holds the shortest trip that is allowed to use only towns $\{1,\dots,k\}$ as intermediate stops. Once $k$ has swept through all $V$ towns, every vertex is a legal stopover and the table holds the true shortest paths. Three loops of size $V$ cost $O(V^3)$ time, while reusing one grid keeps space at $O(V^2)$. The method even tolerates negative edge weights; the one thing it cannot handle is a negative cycle, which reveals itself afterwards as some $dist[i][i] < 0$.

Try this in the panel above. Step forward with ▶│ and watch the Operations and Comparisons counters climb — each step stands for one comparison the algorithm makes as it grinds through the table pair by pair. Next, drag the $n$ slider from 4 up toward 16 and watch the step count climb steeply — a hint of how all-pairs work explodes with size (the true Floyd-Warshall cost is $O(V^3)$, so tripling the vertices multiplies the work about $27$-fold, since $3^3 = 27$). Finally, set the speed to 0.25× and replay to follow each comparison one at a time.

Step 1 -- DP Formulation. Let dist_k[i][j] = shortest path from i to j using only vertices {1,...,k} as intermediates. Base case: dist_0[i][j] = w(i,j) (direct edge or INF). Recurrence: dist_k[i][j] = min(dist_{k-1}[i][j], dist_{k-1}[i][k] + dist_{k-1}[k][j]).

Step 2 -- Optimal Substructure. The shortest path from i to j using {1,...,k} either: (a) doesn't use vertex k -- same as dist_{k-1}[i][j], or (b) goes through k -- dist_{k-1}[i][k] + dist_{k-1}[k][j]. Taking minimum gives the recurrence.

Step 3 -- Space Optimization. The k-th update of dist[i][j] only reads dist[i][k] and dist[k][j]. Since dist[i][k] and dist[k][j] are not updated when the outer loop has index k (dist[x][k] is unchanged), we can use a single 2D array instead of a 3D array.

Step 4 -- Time O(V^3) Space O(V^2). Three nested loops, each iterating V times: O(V^3). Single 2D distance matrix: O(V^2). For V=1000: 10^9 operations -- may be slow. For V=500: feasible.

Step 5 -- Negative Cycle Detection. After algorithm runs: if dist[i][i] < 0 for any vertex i, there is a negative cycle containing i. Initially dist[i][i]=0; only becomes negative if i is on a negative cycle.

Step 6 -- vs Running Dijkstra/Bellman-Ford V times. V x Dijkstra: O(V(V+E) log V). V x Bellman-Ford: O(V^2 E). Floyd-Warshall: O(V^3). For dense graphs (E=V^2): V x Dijkstra = O(V^3 log V) > Floyd-Warshall. For sparse graphs: V x Dijkstra wins.