Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
This is single-source shortest path on an undirected, non-negatively weighted graph. Run Dijkstra with a min-heap: seed dist[src] = 0, repeatedly pop the closest unsettled node, and relax its edges. Report each node's distance, -1 for unreachable, and skip the source in the output. Parallel edges are fine — relaxation keeps the smaller. O((V + E) log V).
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you choose Dijkstra for weighted non-negative shortest paths, can justify the greedy 'settle nearest first', handle undirected edges and parallel edges, and format unreachable nodes as -1.
Where candidates slip
Forgetting to add undirected edges both ways, re-processing stale heap entries, or using int distances that overflow on long weighted paths.
How to stand out
State the non-negative precondition unprompted, contrast a min-heap O((V+E)log V) against the O(V²) array scan, and explain the lazy stale-skip instead of implementing decrease-key.
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 questionNegative edges?YesNoExplore the full treeCollapse the tree
How to read it:Undirected, non-negative weights. The cheapest route to node 4 goes 1→3→4 (15), beating the direct edge (20).
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
Array-Scan Dijkstra (Baseline)
1Hint 1Explore hintHide hint
Forget the heap. Dijkstra needs the closest unfinalized node each step — what is the most direct way to get it?
2Hint 2Explore hintHide hint
Keep a dist[] array and a visited[] flag. Each round, linear-scan all nodes for the smallest dist among unvisited ones, finalize it, relax its edges.
3Hint 3Explore hintHide hint
That scan is O(V) and you do it V times → O(V²), plus O(E) total relaxation. No priority queue needed.
A · Core idea
The greedy idea behind Dijkstra does not require a heap — it only requires repeatedly finding the closest unfinalized node. The simplest way to do that is a linear scan.
The loop. Initialize dist[src] = 0 and everything else to infinity. Repeat V times: scan all nodes for the unvisited one with the smallest dist, mark it finalized, and relax each of its outgoing edges (dist[v] = min(dist[v], dist[u] + w)). After V rounds every reachable node is finalized.
Why it is correct. Same greedy invariant as the heap version: when you pick the closest unfinalized node u, no other path can improve it, because every remaining edge weight is non-negative — any detour only adds cost. The data structure used to find that closest node does not change the correctness, only the speed.
Why mention it. On a dense graph where E ≈ V², the O(V²) scan version is as fast as the heap version and avoids the heap's constant-factor overhead and stale-entry bookkeeping. With n ≤ 3000 here, V² is 9 × 10⁶ — perfectly fine. State it to show you understand that the heap is an optimization for sparse graphs, not a requirement.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2,24],[1,4,20],[3,1,3],[4,3,12]], s = 1Array state
init
dist[1] = 0, rest ∞
24 3 15C · Code with teaching comments
Reference implementation previewpublic int[] shortestReach(int n, int[][] edges, int s) { 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]});Explore the full codeHide the full code
D · Why it works and complexityO(V²) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Dijkstra's correctness comes from the greedy 'settle nearest first', not from any particular data structure. The heap is purely a speed-up for finding that nearest node on sparse graphs; on dense ones the plain O(V²) scan is just as good.
ComplexityO(V²) time, O(V + E) space — V rounds, each doing an O(V) scan to find the nearest unsettled node → O(V²). All edges are relaxed once across the run → O(E). Total O(V² + E) = O(V²). On a dense graph (E ≈ V²) this matches the heap version; on a sparse graph the heap is faster.
E · Edge cases and pitfalls3Adding undirected edges only one way — half the paths vanish.Explore edge casesHide edge cases
Pitfalls
- Adding undirected edges only one way — half the paths vanish.
- Scanning visited nodes when picking the nearest — finalize each node once.
- int distances that overflow on long weighted paths — use long.
Approach 2 of 2 · Optimal
Min-Heap Dijkstra (Optimal)
1Hint 1Explore hintHide hint
The array scan wastes time re-scanning all V nodes each round. What structure hands you the minimum in O(log V) instead of O(V)?
2Hint 2Explore hintHide hint
A min-heap of (distance, node). Pop the closest, relax its edges, and push improved neighbors. Skip a pop whose stored distance is worse than the recorded dist — it is stale.
3Hint 3Explore hintHide hint
Each edge causes at most one push (O(E) pushes, each O(log V)); each node is finalized once. Total O((V + E) log V).
A · Core idea
On a sparse graph, scanning all V nodes every round is wasteful — most are far away and irrelevant. A min-heap delivers the closest unsettled node directly.
The loop. Seed dist[src] = 0 and push (0, src). Repeatedly pop the smallest-distance entry. If its stored distance is worse than dist[u], it is a leftover duplicate — skip it. Otherwise relax every neighbor: if dist[u] + w < dist[v], update dist[v] and push the new (dist[v], v).
Why non-negativity is essential. When you pop node u at distance d, you claim d is final. Any alternative path to u runs through some node still on the heap whose distance is ≥ d (the heap gave you the minimum). Since every remaining edge weight is ≥ 0, extending that path can only add cost — it can never beat d. A negative edge would void this, which is why Dijkstra cannot handle negatives.
Why we skip stale entries. Most standard heaps lack an efficient decrease-key, so instead of updating an entry in place we push a fresh (dist[v], v). The heap then holds several entries per node; the first popped is the smallest and correct, the rest are outdated. if d > dist[u]: continue discards them in O(1) — simpler and, in practice, faster than an indexed heap.
Why an adjacency list and an iterative loop. Storing neighbors as a list makes each relaxation touch only real edges, giving the O(E) push bound; a matrix would force O(V) per node. The main loop is a while over the heap — iterative, no recursion — so a graph with thousands of nodes never risks a stack overflow.
Output. Any node still at infinity was never reached → -1. Skip the source. Parallel edges need no special handling: each is just another relaxation candidate, and the smallest wins.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 4, edges = [[1,2,24],[1,4,20],[3,1,3],[4,3,12]], s = 1Array state
pop 1
relax neighbors of 1
24 3 15C · Code with teaching comments
D · Why it works and complexityO((V + E) log V) timeO(V + E) spaceOpen the invariant and proofExplore the proofHide the proof
Dijkstra is the canonical provably-correct greedy: the min-heap lets you always commit to the choice you can never regret — but only because no edge can later subtract cost. The lazy stale-skip (push duplicates, ignore outdated pops) is the implementation detail interviewers want to hear.
ComplexityO((V + E) log V) time, O(V + E) space — At most one heap push per edge → O(E) pushes, each O(log V). Each of V nodes is popped and finalized once. Total O((V + E) log V). Space is the adjacency list O(V + E) plus the heap O(V).
E · Edge cases and pitfalls7n = 3, edges = [[1,2,4]], s = 1 — Node 3 is unreachable; its dist stays infinity → reported as -1. Output 4 -1.Explore edge casesHide edge cases
Edge cases handled
n = 3, edges = [[1,2,4]], s = 1Node 3 is unreachable; its dist stays infinity → reported as -1. Output 4 -1.parallel edges [1,2,5] and [1,2,2]Both relax into node 2; the smaller (2) wins, the larger push becomes stale.self-loop [u, u, w]Relaxation dist[u] + w < dist[u] is always false → harmless.
Pitfalls
- Adding undirected edges in only one direction.
- Omitting the stale-entry skip — re-relaxes finalized nodes and can TLE.
- Using int for accumulated distance when weight × path length can overflow — use long.
- Including the source in the output or forgetting to map infinity to -1.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] shortestReach(int n, int[][] edges, int s) { 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]});Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1One-directional undirected edge
An undirected edge connects both ways. Adding it to only one adjacency list makes the reverse direction invisible, so some nodes look unreachable and report -1 incorrectly.
Explore the code comparisonHide the code comparison
One-directional undirected edge
An undirected edge connects both ways. Adding it to only one adjacency list makes the reverse direction invisible, so some nodes look unreachable and report -1 incorrectly.
Don't write this
for u, v, w in edges:
adj[u].append((v, w)) # only one directionWrite this instead
for u, v, w in edges:
adj[u].append((v, w))
adj[v].append((u, w)) # undirected → both ways2Forgetting the stale-entry skip
Because we push duplicates instead of decrease-key, the heap holds outdated (distance, node) pairs. Processing them re-relaxes finalized nodes and degrades performance toward a TLE.
Explore the code comparisonHide the code comparison
Forgetting the stale-entry skip
Because we push duplicates instead of decrease-key, the heap holds outdated (distance, node) pairs. Processing them re-relaxes finalized nodes and degrades performance toward a TLE.
Don't write this
long[] top = heap.poll();
int u = (int) top[1];
for (int[] edge : adj.get(u)) { /* relax */ }Write this instead
long[] top = heap.poll();
long d = top[0];
int u = (int) top[1];
if (d > dist[u]) continue; // skip stale duplicate
for (int[] edge : adj.get(u)) { /* relax */ }3BFS on a weighted graph
BFS counts hops, not cost. On weighted edges the fewest-hop path is not necessarily the cheapest, so BFS returns wrong distances. A min-heap ordered by accumulated cost is required.
Explore the code comparisonHide the code comparison
BFS on a weighted graph
BFS counts hops, not cost. On weighted edges the fewest-hop path is not necessarily the cheapest, so BFS returns wrong distances. A min-heap ordered by accumulated cost is required.
Don't write this
from collections import deque
q = deque([s]) # hop-order, ignores weights
while q:
u = q.popleft()Write this instead
import heapq
heap = [(0, s)] # cost-order via min-heap
while heap:
d, u = heapq.heappop(heap)Revise
Carry the pattern into the interview
Pattern to remember
Greedy min-heap relaxation (settle nearest first)
Code pattern to memorize
dist[src] = 0, push (0, src)
while heap:
(d, u) = pop-min
if d > dist[u]: continue # stale entry
for (v, w) in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
push (dist[v], v)
output dist[i] for i != src, -1 if still infinityRules to remember
- 1Works only with non-negative weights — a negative edge breaks the greedy invariant (use Bellman-Ford).
- 2The graph is undirected, so add every edge to both endpoints' adjacency lists.
- 3Parallel edges between the same pair are harmless — relaxation naturally keeps the cheapest; you may also pre-keep the min.
- 4Skip stale heap entries with
if d > dist[u]: continuesince you push duplicates instead of decrease-key. - 5Output excludes the source and maps any node left at infinity to
-1.
Use this pattern when
- Single source, shortest path to all nodes, **non-negative** weights
- Edges differ in cost, so BFS by hop count would be wrong
- You need the actual distance values, not just reachability
- Sparse graph where an adjacency list plus a heap beats an O(V²) scan
Choose another pattern when
- Any negative edge weight → Bellman-Ford (O(VE))
- All edges equal weight → plain BFS is O(V + E) and simpler
- All-pairs shortest paths on a small dense graph → Floyd-Warshall O(V³)
- Need to detect a negative cycle → Bellman-Ford, Dijkstra cannot
Interview takeaway
Dijkstra is BFS upgraded with a priority queue: expand by accumulated cost, not hop count. The min-heap makes 'always settle the closest unfinalized node' cheap, and that greedy choice is correct precisely because no edge can later subtract cost.
Continue
Transfer the pattern to another problem
Use a direct variation or pattern sibling to prove the idea is reusable.
Transferable patternCanonical Greedy Min-Heap Shortest Path. Recognize it on any weighted, non-negative, single-source path question. The heap-relaxation skeleton also powers Network Delay Time, Path With Minimum Effort, and Prim's MST — only the relaxation rule changes. Drop to the O(V²) array scan when the graph is dense.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Dijkstra's Shortest PathThe directed-graph framing of the same min-heap relaxation.
- Bellman-Ford Shortest PathDrop the non-negative requirement: O(VE) relaxation that also detects negative cycles.
- BFS: Shortest Reach in a GraphWhen all weights are equal, swap the heap for a FIFO queue.
- Network Delay TimeComing soonDirect Dijkstra application — return the maximum finalized distance, or -1 if any node is unreachable.