Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Compute shortest paths between every pair of vertices with one triple loop. The outer loop fixes an intermediate vertex k; for every pair (i, j) you ask whether routing through k beats the current best: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). O(V³) time, O(V²) space, handles negative edges.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you can state the intermediate-vertex DP, explain precisely why k is the outer loop, and recognize when O(V³) all-pairs beats running a single-source algorithm V times.
Where candidates slip
Ordering the loops i, j, k instead of k, i, j, which computes the wrong recurrence and gives wrong distances.
How to stand out
Explain the DP invariant ('shortest path using only intermediates from {0..k}'), mention negative-cycle detection via the diagonal, and compare O(V³) against V × Dijkstra to justify the choice.
Choose
Compare the available approaches
Use constraints and trade-offs to select the route you can defend in an interview.
Interactive decision treeInteractiveChoose the right approachFirst decision previewShortest paths?All pairs or single source?SingleAll pairsExplore the full treeCollapse the tree
How to read it:Four vertices. Floyd-Warshall finds that 0→1→2→3 (cost 6) beats the direct 0→3 edge (cost 7).
Learn & trace
Build each solution step by step
Move from the core idea to a visual trace, implementation, proof, and edge cases.
Approach 1 of 2
Run Dijkstra From Every Vertex (Baseline)
1Hint 1Explore hintHide hint
You already know how to get shortest paths from one source. How do you get them from every source?
2Hint 2Explore hintHide hint
Just loop the single-source algorithm over all V sources, storing each result as one row of the matrix.
3Hint 3Explore hintHide hint
If edges are non-negative, use Dijkstra per source. If they are negative, you'd need Bellman-Ford per source — V × O(V·E), which is worse.
A · Core idea
The most direct route to all-pairs shortest paths is to reuse a single-source algorithm and run it once per vertex, treating each run as a row of the output matrix.
Why it is the obvious baseline. You don't need a new idea — you already have Dijkstra (non-negative) or Bellman-Ford (negative). All-pairs is 'do the thing you know V times'. Each source produces its own distance vector; stack them into the V × V matrix.
When it actually wins. On sparse graphs (E ≈ V), V Dijkstra runs cost about O(V² log V), dramatically better than Floyd-Warshall's fixed O(V³). So for large sparse graphs this baseline is the right answer, not Floyd-Warshall.
Where it struggles. With negative edges you must swap Dijkstra for Bellman-Ford, making it V × O(V·E) = O(V²·E) — on a dense graph that is O(V⁴), far worse. And the bookkeeping of building adjacency lists and a heap per source is more code than three nested loops. That trade — simpler code and negative-edge support on small dense graphs — is exactly what Floyd-Warshall buys.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1,4],[0,2,5],[1,2,-3]], all pairs (use Bellman-Ford per source for negatives)Array state
row 0
from source 0
matrix rows assembled from V single-source runsC · Code with teaching comments
Reference implementation previewpublic int[][] allPairsViaDijkstra(int n, int[][] edges) { List<int[]>[] adj = new List[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>(); for (int[] e : edges) adj[e[0]].add(new int[]{e[1], e[2]}); // non-negative only Explore the full codeHide the full code
D · Why it works and complexityO(V · (V + E) log V) timeO(V²) spaceOpen the invariant and proofExplore the proofHide the proof
All-pairs is not always a special algorithm — sometimes it is just 'single-source, V times'. The deciding factors are density (sparse favors repeated Dijkstra) and edge sign (negative favors Floyd-Warshall or repeated Bellman-Ford).
ComplexityO(V · (V + E) log V) time, O(V²) space — V independent Dijkstra runs, each O((V + E) log V). On a sparse graph this beats O(V³); on a dense graph (E ≈ V²) it becomes O(V³ log V), worse than Floyd-Warshall.
E · Edge cases and pitfalls3Using Dijkstra per source when edges are negative — silently wrong.Explore edge casesHide edge cases
Pitfalls
- Using Dijkstra per source when edges are negative — silently wrong.
- On dense graphs this becomes slower than Floyd-Warshall.
- Forgetting to map unreachable infinity to -1 in each row.
Approach 2 of 2 · Optimal
Floyd-Warshall — DP Over Intermediate Vertices (Optimal for Small Dense)
1Hint 1Explore hintHide hint
Define dist_k[i][j] = shortest i→j path that only uses intermediate vertices from the set {0, 1, ..., k−1}. What is dist_0?
2Hint 2Explore hintHide hint
To allow vertex k as a new intermediate: either the best path skips k (dist_k[i][j]) or it goes i → k → j (dist_k[i][k] + dist_k[k][j]). Take the min.
3Hint 3Explore hintHide hint
Loop k on the outside, then i and j inside. After k runs through all vertices, every vertex is allowed as an intermediate, so the matrix is the true all-pairs answer.
A · Core idea
Floyd-Warshall is a dynamic program where the dimension we grow is which vertices are allowed to appear in the middle of a path. Define dist_k[i][j] as the length of the shortest path from i to j whose intermediate vertices all come from {0, 1, ..., k−1}. We start with k = 0 (no intermediates allowed — only direct edges) and finish with k = V (every vertex allowed), at which point dist[i][j] is the unrestricted shortest path.
The recurrence. When we newly allow vertex k as an intermediate, the shortest i→j path either still does not use k — value unchanged — or it does, in which case it splits cleanly into a best i→k path and a best k→j path, neither of which uses k as an intermediate (a simple path visits k once). So: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). That single line, applied for all pairs, promotes the allowed set from {0..k−1} to {0..k}.
Why k MUST be the outermost loop. The recurrence for the (i, j) entry at stage k depends on the entries dist[i][k] and dist[k][j] at the same stage k. Processing k outermost guarantees that when you compute any (i, j), the row k and column k you read are already the correct stage-k values. Conveniently, dist[i][k] and dist[k][j] never change during stage k (the path i→k would have to route through k, contributing nothing), so the in-place update is safe and you do not need two matrices. Swap the loop order — put i or j outermost — and you read half-updated values, computing a recurrence that simply isn't Floyd-Warshall, and you get wrong distances.
Initialization. dist[i][i] = 0 (a vertex reaches itself for free), dist[u][v] = w for each direct edge, and everything else is infinity. Use the smaller of parallel edges if any.
The overflow guard. Infinity is a sentinel, so dist[i][k] + dist[k][j] must be skipped when either operand is infinity; otherwise the sum overflows and looks like a short path. The cleanest guard is to only attempt the relaxation when both dist[i][k] and dist[k][j] are finite.
Negative-cycle detection, for free. If, after the run, any dist[i][i] < 0, there is a negative cycle through i — a path that leaves i and returns with negative total cost. The triple loop is iterative with no recursion, so there is no stack-overflow concern regardless of graph size; the only limit is the O(V³) time and O(V²) memory.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1,4],[0,2,5],[1,2,-3]]Array state
init / k=0
direct edge 0→2
dist[0] = [0, 4, 1]C · Code with teaching comments
D · Why it works and complexityO(V³) timeO(V²) spaceOpen the invariant and proofExplore the proofHide the proof
The elegance is in the indexing: the DP grows along 'allowed intermediate vertices', not path length or hop count. That is why a graph-distance problem collapses into three plain loops. Memorize the loop order k-i-j and the reason for it — interviewers probe exactly that.
ComplexityO(V³) time, O(V²) space — Three nested loops over V vertices → V³ constant-time min operations. The matrix is V² entries, so space is O(V²). No heap, no recursion.
E · Edge cases and pitfalls7negative edge, no cycle — Handled directly — unlike Dijkstra, relaxation works with negative weights.Explore edge casesHide edge cases
Edge cases handled
negative edge, no cycleHandled directly — unlike Dijkstra, relaxation works with negative weights.disconnected pair (i, j)Stays at INF → reported as -1.negative cycle presentSome dist[i][i] becomes < 0 after the run, flagging the cycle.
Pitfalls
- Wrong loop order — k must be outermost; i-j-k computes the wrong recurrence.
- Adding two infinities and overflowing — guard with a headroom sentinel or skip checks.
- Forgetting dist[i][i] = 0 initialization.
- Using it on a large graph where O(V³) is too slow — prefer V × Dijkstra when sparse.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[][] floydWarshall(int n, int[][] edges) { final long INF = Long.MAX_VALUE / 4; // headroom so INF + INF won't overflow long[][] dist = new long[n][n]; for (long[] row : dist) Arrays.fill(row, INF); for (int i = 0; i < n; i++) dist[i][i] = 0;Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Wrong loop order (k not outermost)
The recurrence at stage k reads dist[i][k] and dist[k][j] at that same stage. Only k-outermost guarantees those are the correct values; any other order reads half-updated entries and yields wrong distances.
Explore the code comparisonHide the code comparison
Wrong loop order (k not outermost)
The recurrence at stage k reads dist[i][k] and dist[k][j] at that same stage. Only k-outermost guarantees those are the correct values; any other order reads half-updated entries and yields wrong distances.
Don't write this
for i in range(n):
for j in range(n):
for k in range(n): # k innermost — WRONG
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Write this instead
for k in range(n): # k outermost — correct DP
for i in range(n):
for j in range(n):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])2Infinity overflow
Using Integer.MAX_VALUE as INF and adding two of them overflows to a large negative number, which looks like a very short path and corrupts the matrix.
Explore the code comparisonHide the code comparison
Infinity overflow
Using Integer.MAX_VALUE as INF and adding two of them overflows to a large negative number, which looks like a very short path and corrupts the matrix.
Don't write this
final int INF = Integer.MAX_VALUE;
if (dist[i][k] + dist[k][j] < dist[i][j]) { /* overflow when both INF */ }Write this instead
final long INF = Long.MAX_VALUE / 4; // headroom
if (dist[i][k] != INF && dist[k][j] != INF
&& dist[i][k] + dist[k][j] < dist[i][j]) { /* safe */ }3Missing diagonal initialization
If dist[i][i] is left at infinity, paths that legitimately pass through i and back, or self-distances, compute incorrectly.
Explore the code comparisonHide the code comparison
Missing diagonal initialization
If dist[i][i] is left at infinity, paths that legitimately pass through i and back, or self-distances, compute incorrectly.
Don't write this
dist = [[INF] * n for _ in range(n)]
# forgot the diagonalWrite this instead
dist = [[INF] * n for _ in range(n)]
for i in range(n):
dist[i][i] = 0Revise
Carry the pattern into the interview
Pattern to remember
DP over allowed intermediate vertices
Code pattern to memorize
dist[i][j] = weight(i, j) or INF, dist[i][i] = 0
for k in 0..V-1:
for i in 0..V-1:
for j in 0..V-1:
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Rules to remember
- 1k must be the outermost loop. Putting i or j outside silently breaks the DP.
- 2Initialize
dist[i][i] = 0, direct edges to their weight, everything else to infinity. - 3Guard the addition: skip if either
dist[i][k]ordist[k][j]is infinity to avoid overflow. - 4A negative value on the diagonal (
dist[i][i] < 0) after the run means a negative cycle. - 5Use it only for small, dense graphs —
O(V³)is brutal past a few hundred vertices.
Use this pattern when
- You need shortest paths between **all pairs**, not from a single source
- Graph is **small and dense** (V up to a few hundred)
- Edges may be **negative** (no negative cycle), where repeated Dijkstra is awkward
- Transitive closure / reachability between every pair
Choose another pattern when
- Single source only → Dijkstra or Bellman-Ford, far cheaper
- Large or sparse graph → V Dijkstra runs O(V·(E log V)) beats O(V³)
- Unweighted reachability on a big graph → BFS per source or DSU
- Memory tight and V large → O(V²) matrix may not fit
Interview takeaway
Floyd-Warshall is three nested loops that quietly solve all-pairs shortest paths by growing the set of allowed intermediate vertices one at a time. The whole correctness argument hinges on k being the outermost loop.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical DP over intermediate vertices. Reach for it on all-pairs shortest paths in small dense graphs or with negative edges. The same k-i-j triple loop, with OR instead of min, computes transitive closure, and with min-of-max computes minimax / bottleneck paths.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Dijkstra's Shortest PathSingle-source non-negative weights; run V times for sparse all-pairs.
- Bellman-Ford Shortest PathSingle-source with negative edges; Floyd-Warshall is its all-pairs cousin.
- Find the City With the Smallest Number of NeighborsComing soonClassic Floyd-Warshall application — all-pairs distances, then count reachable-within-threshold neighbors.
- Transitive Closure / Reachability MatrixComing soonSame triple loop with boolean OR instead of min-plus.