Why k is Outermost

The loop order in Floyd-Warshall is critical: $k$ must be the outer loop. Why?

Because paths using vertices $\{0, \ldots, k\}$ depend on paths using $\{0, \ldots, k-1\}$. If you loop $i$ or $j$ first, you break the dependency order. Always write: for k, for i, for j. Any other order gives wrong answers. This is not a performance improvement, it affects correctness. Get the order wrong and you get incorrect shortest paths.