Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Answer many shortest-path queries on a directed weighted graph. Precompute all-pairs shortest paths once with Floyd-Warshall: a triple loop over an intermediate node k that relaxes dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After the O(V³) precompute, every query is an O(1) table lookup; report -1 when the entry is still infinity (unreachable). Crucial: the k loop must be outermost.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you recognize a many-queries all-pairs setting as Floyd-Warshall, can state the DP meaning of the loops, get the k-outermost loop order right, and handle unreachable pairs and overflow.
Where candidates slip
Putting the k loop inside (wrong answers), letting INF + INF overflow, treating a directed graph as undirected, or running a fresh Dijkstra per query when there are too many queries.
How to stand out
Explain the loop order via the DP invariant ('after iteration k, dist[i][j] uses only intermediates ≤ k'), justify Floyd over per-query Dijkstra by the query count and small V, and mention the negative-cycle diagnostic (any dist[i][i] < 0).
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-path queriesMany queries, small V?YesNoExplore the full treeCollapse the tree
How to read it:All edges are one-way. The shortest 1→4 route is 1→2→4 (11), beating the direct edge (24). Node 1 has no incoming edge, so nothing reaches it.
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
Per-Query Dijkstra (Baseline)
1Hint 1Explore hintHide hint
Each query (a, b) is just a single-source shortest path from a. What's the standard tool for non-negative weights?
2Hint 2Explore hintHide hint
Run Dijkstra from a, then read dist[b]. Weights are positive here, so Dijkstra is valid.
3Hint 3Explore hintHide hint
If queries are few this is great; if there are 10⁵ queries you may re-run Dijkstra from the same source repeatedly — wasteful, motivating an all-pairs precompute.
A · Core idea
A query asks one source-to-target distance, which is exactly what Dijkstra computes.
Per query. For query (a, b), run Dijkstra from a: seed dist[a] = 0, pop the closest unsettled node from a min-heap, relax its outgoing edges. When done, return dist[b], or -1 if it stayed infinite.
Why it's correct. Weights are non-negative, so Dijkstra's greedy 'settle nearest first' is valid and yields exact shortest distances from a to every node — in particular to b.
Why it can be wasteful. With up to 10⁵ queries spread over many sources, you may run full Dijkstra runs that recompute overlapping information. Memoizing by source bounds it at V runs, but when the graph is small and queries are many, one O(V³) precompute that answers every pair in O(1) is simpler and often faster overall.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
queries on n = 4, edges = [[1,2,5],[1,4,24],[2,4,6],[3,4,4],[3,2,7]]Array state
settle 1
relax → dist[2]=5, dist[4]=24
[5, -1, 11]C · Code with teaching comments
Reference implementation previewpublic int[] answerQueries(int n, int[][] edges, int[][] queries) { List<List<int[]>> adj = new ArrayList<>(); for (int i = 0; i <= n; i++) adj.add(new ArrayList<>()); for (int[] e : edges) adj.get(e[0]).add(new int[]{e[1], e[2]}); // directed int[] ans = new int[queries.length];Explore the full codeHide the full code
D · Why it works and complexityO(q · (V + E) log V) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Per-query Dijkstra is the right instinct for one-off shortest paths, and it scales to large graphs where V³ is impossible. The decision hinges on the query count and graph size: many queries on a small graph flips the economics toward all-pairs precomputation.
ComplexityO(q · (V + E) log V) time, O(V + E) space — Each Dijkstra is O((V + E) log V). Doing it per query is O(q · (V + E) log V). With q up to 10⁵ and a dense graph (E ≈ V²), this balloons; caching results per distinct source helps but Floyd-Warshall is cleaner when queries hit many sources.
E · Edge cases and pitfalls3Adding edges both directions on a directed graph.Explore edge casesHide edge cases
Pitfalls
- Adding edges both directions on a directed graph.
- Re-running Dijkstra for repeated sources instead of caching — wasteful at 10⁵ queries.
- Forgetting the stale-entry skip in Dijkstra.
Approach 2 of 2 · Optimal
Floyd-Warshall All-Pairs (Optimal)
1Hint 1Explore hintHide hint
Queries hit many different sources. Instead of one source at a time, can you compute the shortest path between every pair up front?
2Hint 2Explore hintHide hint
Build an n×n matrix: dist[i][j] = edge weight (min over parallels), 0 on the diagonal, infinity otherwise. Then improve it by allowing intermediate stops.
3Hint 3Explore hintHide hint
For each candidate intermediate node k (outer loop), every pair (i, j) can try routing i→k→j: dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]). After all k, the matrix holds all shortest paths.
A · Core idea
When queries are numerous and the graph is small, computing all pairs once beats per-query work.
The DP meaning. Let dist_k[i][j] be the shortest path from i to j using only nodes 1..k as intermediate stops. With no intermediates allowed (k = 0), it's just the direct edge (or infinity). Adding node k as an allowed waypoint gives two choices: ignore it (keep dist_{k-1}[i][j]) or route through it (dist_{k-1}[i][k] + dist_{k-1}[k][j]). Take the min. After k = n, all nodes are allowed and dist[i][j] is the true shortest path.
Why the k loop is outermost. k indexes the DP layers — the set of permitted intermediates. The invariant 'after iteration k, every entry uses only intermediates ≤ k' holds only if we finish all (i, j) updates for a given k before moving to k+1. Because the in-place update dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) reads row k and column k, and those entries are not improved further within the same k iteration (a shortest path through k doesn't use k twice), updating in place is safe. Put k inner and you allow paths that revisit intermediates inconsistently — wrong answers.
Overflow guard. Initialize unreachable entries to a sentinel and only relax when both dist[i][k] and dist[k][j] are finite; otherwise INF + INF can overflow or create bogus 'shorter' paths. Using a large-but-safe sentinel (well under MAX/2) or an explicit finite check both work.
Answering queries. Each (a, b) is dist[a][b], or -1 if it's still the sentinel. Directed edges set only dist[u][v]; parallel edges keep the minimum.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2,5],[1,4,24],[2,4,6],[3,4,4],[3,2,7]]; queries (1,2),(3,1),(1,4)Array state
init
direct edges from 1
[5, -1, 11]C · Code with teaching comments
D · Why it works and complexityO(V³ + q) timeO(V²) spaceOpen the invariant and proofExplore the proofHide the proof
Floyd-Warshall is DP over a third dimension you don't store — the allowed-intermediate set. The triple loop with k outermost literally builds shortest paths layer by layer. The same matrix, with a tiny tweak (replace +/min by OR/AND), computes transitive closure (reachability) — and dist[i][i] < 0 after the run flags a negative cycle.
ComplexityO(V³ + q) time, O(V²) space — Initialization is O(V² + E). The triple loop is O(V³) = 400³ ≈ 6.4 × 10⁷ — fast in both Java and Python-with-care. Each of the q queries is an O(1) lookup, so total O(V³ + q). Space is the O(V²) matrix.
E · Edge cases and pitfalls7query (a, a) — dist[a][a] = 0 from initialization — a node reaches itself at zero cost.Explore edge casesHide edge cases
Edge cases handled
query (a, a)dist[a][a] = 0 from initialization — a node reaches itself at zero cost.unreachable targetEntry stays at the INF sentinel; the query returns -1.parallel edges [1,2,3] and [1,2,10]Initialization keeps min(3, 10) = 3, so the heavier edge never affects results.
Pitfalls
- Putting the k loop anywhere but outermost — produces wrong distances.
- Letting INF + INF overflow — use a sentinel below MAX/2 or guard with a finite check.
- Initializing the matrix as undirected on a directed graph.
- Returning the sentinel value instead of mapping it to -1 for unreachable pairs.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] answerQueries(int n, int[][] edges, int[][] queries) { final long INF = Long.MAX_VALUE / 4; // safe sentinel, no overflow on a sum long[][] dist = new long[n + 1][n + 1]; for (long[] row : dist) Arrays.fill(row, INF); for (int i = 1; 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 indexes the DP layer (allowed intermediates). It must be the outermost loop so all (i, j) pairs are updated for a given k before k advances. Putting k inside lets paths use intermediates inconsistently and yields wrong distances.
Explore the code comparisonHide the code comparison
Wrong loop order
k indexes the DP layer (allowed intermediates). It must be the outermost loop so all (i, j) pairs are updated for a given k before k advances. Putting k inside lets paths use intermediates inconsistently and yields wrong distances.
Don't write this
for i in range(1, n + 1):
for j in range(1, n + 1):
for k in range(1, n + 1): # k must NOT be innermost
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])Write this instead
for k in range(1, n + 1): # intermediate node outermost
for i in range(1, n + 1):
for j in range(1, n + 1):
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])2Infinity overflow
If unreachable is Integer.MAX_VALUE, then dist[i][k] + dist[k][j] can overflow to a negative number that looks 'shorter', corrupting the matrix.
Explore the code comparisonHide the code comparison
Infinity overflow
If unreachable is Integer.MAX_VALUE, then dist[i][k] + dist[k][j] can overflow to a negative number that looks 'shorter', corrupting the matrix.
Don't write this
final long INF = Long.MAX_VALUE;
// dist[i][k] + dist[k][j] overflows when both are INFWrite this instead
final long INF = Long.MAX_VALUE / 4; // headroom
if (dist[i][k] == INF) continue; // and/or skip infinite rows3Directed graph read as undirected
Each road is one-way. Mirroring edges invents reverse paths, so a query like 3→1 (truly unreachable) would wrongly return a finite distance.
Explore the code comparisonHide the code comparison
Directed graph read as undirected
Each road is one-way. Mirroring edges invents reverse paths, so a query like 3→1 (truly unreachable) would wrongly return a finite distance.
Don't write this
dist[u][v] = min(dist[u][v], w)
dist[v][u] = min(dist[v][u], w) # invents a reverse roadWrite this instead
dist[u][v] = min(dist[u][v], w) # directed: only u -> vRevise
Carry the pattern into the interview
Pattern to remember
All-pairs DP: relax through each intermediate node k
Code pattern to memorize
dist[i][j] = INF for all i≠j; dist[i][i] = 0
for each edge (u, v, w): dist[u][v] = min(dist[u][v], w)
for k in 1..n: # intermediate node — MUST be outermost
for i in 1..n:
for j in 1..n:
if dist[i][k] + dist[k][j] < dist[i][j]:
dist[i][j] = dist[i][k] + dist[k][j]
query(a, b): dist[a][b], or -1 if still INFRules to remember
- 1The k loop is outermost — k is the set of allowed intermediates. Swapping the loop order gives wrong answers.
- 2Guard against INF overflow: only relax when both
dist[i][k]anddist[k][j]are finite (or use a sentinel safely below MAX). - 3The graph here is directed — set
dist[u][v]only (not the reverse) when reading an edge. - 4Keep the minimum among parallel edges when initializing:
dist[u][v] = min(dist[u][v], w). - 5After the precompute, each query is O(1); an entry left at INF means unreachable → -1.
Use this pattern when
- **Many** shortest-path queries between arbitrary pairs on a **small** graph (V ≤ ~400–500)
- All-pairs distances are needed, not just from one source
- Dense graph where a per-query Dijkstra would repeat work
- Negative edges allowed (no negative cycle) — Floyd-Warshall still works
Choose another pattern when
- Single source, one query → Dijkstra is O((V+E) log V), far cheaper than O(V³)
- Large V (thousands+) → V³ is too big; run Dijkstra per source/query instead
- Unweighted graph → BFS per source beats the cubic precompute
- Need the actual path, not just the distance → store a 'next' matrix for reconstruction
Interview takeaway
Floyd-Warshall is dynamic programming over 'which intermediate nodes are allowed': after considering nodes 1..k as possible waypoints, dist[i][j] is the best path using only those. Adding node k either helps (route i→k→j) or doesn't. The cubic precompute pays for O(1) queries — the right trade when queries are many and the graph is small.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical All-Pairs Shortest Path via Floyd-Warshall. Recognize it when many shortest-path queries hit a small (V ≤ ~400) graph, or when you need every pair's distance. The triple loop is DP over allowed intermediate nodes with k outermost; the same skeleton computes transitive closure and detects negative cycles. For large V or single-source queries, prefer Dijkstra/Bellman-Ford.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Bellman-Ford Shortest PathSingle source with negative edges; also detects negative cycles (Floyd flags them via dist[i][i] < 0).
- Dijkstra: Shortest Reach 2Single-source non-negative shortest paths — the right tool when V is large or queries share a source.
- Find the City With the Smallest Number of NeighborsComing soonDirect Floyd-Warshall application: all-pairs distances, then count reachable nodes within a threshold.
- Transitive Closure / ReachabilityComing soonSame triple loop with OR/AND instead of min/+ to compute which pairs are connected.