Understand
30-second explanation
Build the interview-ready mental model before comparing implementations.
Compute single-source shortest paths on a graph with non-negative edge weights. Maintain a dist array, pull the closest unfinalized vertex from a min-heap, and relax its outgoing edges. The greedy pull is correct only because weights are non-negative — that is the whole trick. O((V + E) log V) with a binary heap.
Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview contextHide interview context
What's being tested
Whether you reach for a min-heap on a weighted shortest-path problem, can state why the greedy 'settle nearest first' is correct, and know the non-negative-weight precondition cold.
Where candidates slip
Using Dijkstra on a graph with negative edges (silently wrong), or forgetting to skip stale heap entries and re-relaxing finalized vertices.
How to stand out
Name the algorithm, state the non-negative precondition unprompted, contrast it with Bellman-Ford for negatives, and explain the lazy-deletion stale-entry trick rather than implementing a 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:Five vertices, non-negative weights. Dijkstra finalizes vertices in increasing distance order: 0, 2, 1, 3.
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
Bellman-Ford — Repeated Relaxation (Baseline)
1Hint 1Explore hintHide hint
Forget the heap for a moment. If you relaxed every edge once, some shortest paths would be found but not all. What if you just repeated that pass?
2Hint 2Explore hintHide hint
A shortest path has at most V − 1 edges. So V − 1 full passes over every edge guarantee all shortest distances settle.
3Hint 3Explore hintHide hint
Each pass: for every edge (u, v, w), if dist[u] + w < dist[v], update dist[v]. No ordering, no priority queue.
A · Core idea
Bellman-Ford ignores the cleverness of which vertex to process next and instead brute-forces the relaxation. It relaxes every edge in the graph, then does it again, and again — V − 1 times in total.
Why V − 1 passes are enough. Any shortest path in a graph with no negative cycle visits at most V vertices, so it uses at most V − 1 edges. Claim: after pass k, every shortest path that uses at most k edges has been correctly computed. Pass 1 settles all 1-edge shortest paths, pass 2 extends those by one more edge to settle 2-edge paths, and so on. After V − 1 passes, every shortest path — which can be no longer than V − 1 edges — is final.
Why it tolerates negative edges. Nothing in the argument above assumed non-negative weights. It only assumed there is no negative cycle (a cycle whose total weight is negative, which would let you loop forever to reduce cost without bound). That is exactly why Bellman-Ford is the fallback when Dijkstra's precondition fails.
Why we don't always use it. It does O(V·E) work regardless of structure — no early stopping, no priority ordering. On the non-negative graphs Dijkstra targets, that is wasteful. Mention Bellman-Ford to show you know the general tool, then explain that non-negative weights unlock a far faster greedy approach.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 3, edges = [[0,1,1],[1,2,1],[0,2,5]], src = 0Array state
init
dist[src] = 0, rest = ∞
[0, 1, 2]C · Code with teaching comments
Reference implementation previewpublic int[] bellmanFord(int n, int[][] edges, int src) { long[] dist = new long[n]; Arrays.fill(dist, Long.MAX_VALUE); dist[src] = 0; for (int pass = 0; pass < n - 1; pass++) {Explore the full codeHide the full code
D · Why it works and complexityO(V·E) timeO(V) spaceOpen the invariant and proofExplore the proofHide the proof
Bellman-Ford trades speed for generality: it makes no assumption about edge signs, paying O(V·E) for that freedom. Recognizing the precondition split — negative edges → Bellman-Ford, non-negative → Dijkstra — is the single most important shortest-path decision in an interview.
ComplexityO(V·E) time, O(V) space — V − 1 passes, each touching all E edges → O(V·E). On a dense graph that is O(V³), much slower than Dijkstra's O((V+E) log V).
E · Edge cases and pitfalls3Forgetting the reachability guard (dist[u] != INF) — adding INF + w overflows.Explore edge casesHide edge cases
Pitfalls
- Forgetting the reachability guard (dist[u] != INF) — adding INF + w overflows.
- Running only one pass instead of V − 1 — misses multi-edge shortest paths.
- Not adding a negative-cycle check pass when negative edges are present.
Approach 2 of 2 · Optimal
Dijkstra — Min-Heap Greedy (Optimal)
1Hint 1Explore hintHide hint
Bellman-Ford redoes work because it relaxes edges in arbitrary order. What if you always processed the vertex you are *most certain* about next?
2Hint 2Explore hintHide hint
The closest unfinalized vertex can never be improved later — because all remaining edges are non-negative, any detour only adds cost. So finalize it greedily.
3Hint 3Explore hintHide hint
A min-heap keyed by current distance gives you that closest vertex in O(log V). Pop it, relax its edges, push updated neighbors. Skip entries whose distance is stale.
A · Core idea
Dijkstra is best understood as breadth-first search where the frontier is ordered by accumulated cost instead of hop count. You keep a dist[] array (all infinity except the source) and a min-heap of (distance, vertex) pairs. Repeatedly pop the smallest-distance entry, and if it is not stale, relax every outgoing edge.
The greedy invariant and why non-negativity is essential. When you pop vertex u with distance d, you claim d is the final shortest distance to u. Why is that safe? Any other path to u must go through some vertex x still on the heap, and x's current distance is ≥ d (because the heap gave you the minimum). Since every remaining edge weight is ≥ 0, continuing from x to u can only add cost — it can never produce a path shorter than d. Remove the non-negativity assumption and this collapses: a negative edge later in the graph could make a path through x cheaper, so the vertex you 'finalized' was wrong. That is precisely why Dijkstra cannot handle negative edges.
Why we skip stale entries. When we relax an edge into v and find a better distance, we push a new (dist[v], v) onto the heap rather than updating the old entry in place — most standard libraries have no efficient decrease-key. So the heap can hold several entries for the same vertex. The first one popped is the smallest and correct; the later ones are outdated. The line if d > dist[u]: continue discards them in O(1), which is simpler and, in practice, faster than maintaining an indexed heap.
Why an adjacency list and iterative loop. We store neighbors as an adjacency list so each relaxation only scans real edges, giving the O(E) push bound; a matrix would force O(V) work per vertex and O(V²) total. The main loop is iterative (a while over the heap), so there is no recursion and therefore no risk of blowing the call stack on a graph with 10⁵ vertices.
Why dist[] is both the state and the answer. Unlike unweighted BFS where a boolean visited set suffices, here the values in dist[] are what we return. A vertex left at infinity at the end was never reached, which we map to -1.
B · Visual dry run
Interactive dry run
Select a frame to connect the decision with its visual state.
n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5]], src = 0Array state
pop 0
relax neighbors of 0
[0, 3, 1, 4, -1]C · 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 'greedy is provably correct' algorithm: the min-heap guarantees you always commit to the choice you can never regret — but only because no edge can later subtract cost. Whenever you see weighted single-source shortest paths with non-negative weights, this is the reflex. The lazy stale-skip trick (push duplicates, ignore outdated pops) is the practical implementation detail interviewers love to hear you mention.
ComplexityO((V + E) log V) time, O(V + E) space — Each edge triggers at most one push → O(E) pushes, each O(log V). Each vertex 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 = 2, edges = [], src = 0 — Heap pops only the source; vertex 1 stays infinity → returns [0, -1].Explore edge casesHide edge cases
Edge cases handled
n = 2, edges = [], src = 0Heap pops only the source; vertex 1 stays infinity → returns [0, -1].self-loop edge [u, u, 5]Relaxation dist[u] + 5 < dist[u] is always false → harmless, no effect.parallel edges [0,1,9] and [0,1,2]Both relax into vertex 1; the smaller (2) wins, the larger push becomes stale.
Pitfalls
- Running Dijkstra on a graph with a negative edge — silently returns wrong distances.
- Omitting the stale-entry skip — you re-relax finalized vertices and may TLE on big graphs.
- Using int for accumulated distance when weights × path length can overflow — use long.
- Using a visited boolean instead of comparing d to dist[u] — both work, but mixing them causes subtle bugs.
Practice
Try the solution yourself
Edit the optimal implementation, test another input, and observe the result.
Editable code previewpublic int[] dijkstra(int n, int[][] edges, int src) { 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]}); Explore the playgroundClose the playground
Avoid mistakes
Recognize the interview traps
Understand why common attempts fail before reviewing the corrected implementation.
1Using Dijkstra with negative edges
The greedy 'finalize the closest vertex' invariant assumes no edge can later reduce a path's cost. A negative edge violates that, so a finalized vertex may actually have a cheaper path discovered later.
Explore the code comparisonHide the code comparison
Using Dijkstra with negative edges
The greedy 'finalize the closest vertex' invariant assumes no edge can later reduce a path's cost. A negative edge violates that, so a finalized vertex may actually have a cheaper path discovered later.
Don't write this
# edges include [1, 2, -4] — Dijkstra finalizes vertex 2 too early
d, u = heapq.heappop(heap)
for v, w in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wWrite this instead
# negative edges present → switch algorithm
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w # Bellman-Ford2Forgetting the stale-entry skip
Because we push duplicates instead of decrease-key, the heap holds outdated (distance, vertex) pairs. Processing them re-relaxes finalized vertices and degrades performance, potentially to 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, vertex) pairs. Processing them re-relaxes finalized vertices and degrades performance, potentially to a TLE.
Don't write this
long[] top = heap.poll();
int u = (int) top[1];
for (int[] edge : adj[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[u]) { /* relax */ }3Integer overflow on accumulated distance
With up to 10⁵ vertices and weights up to 10⁶, a long path can exceed int range. Use long for dist and the initial 'infinity'.
Explore the code comparisonHide the code comparison
Integer overflow on accumulated distance
With up to 10⁵ vertices and weights up to 10⁶, a long path can exceed int range. Use long for dist and the initial 'infinity'.
Don't write this
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE); // overflows when you add wWrite this instead
long[] dist = new long[n];
Arrays.fill(dist, Long.MAX_VALUE);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, skip
for (v, w) in adj[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
push (dist[v], v)Rules to remember
- 1Works only with non-negative edge weights. A single negative edge breaks the greedy invariant — use Bellman-Ford instead.
- 2Skip stale heap entries with
if d > dist[u]: continue— you push duplicates and must ignore the outdated ones. - 3A vertex is finalized the first time it is popped. Don't relax into already-finalized vertices needlessly.
- 4Use a
dist[]array seeded with infinity, not avisitedset alone — the distances are the answer. - 5Build an adjacency list, not a matrix, unless the graph is dense — the matrix wastes O(V²) on sparse graphs.
Use this pattern when
- Single source, shortest path to all (or one) targets, **non-negative** weights
- Weighted graph where BFS would be wrong because edges differ in cost
- Road networks, latency graphs, flight costs — anything with positive distances
- You need the actual distance values, not just reachability
Choose another pattern when
- Any negative edge weight → Bellman-Ford (O(VE)) or Johnson's
- All edges have equal weight → plain BFS is O(V + E), simpler and faster
- Need 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: instead of expanding by hop count, you expand by accumulated cost. Internalize why non-negativity matters and you'll know instantly when to reach for Bellman-Ford instead.
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 same heap-relaxation skeleton powers Network Delay Time, Path With Minimum Effort, Swim in Rising Water, and Prim's MST — only the relaxation rule changes.
Practice queueDirect variations and pattern siblings
Direct follow-ups
- Bellman-Ford Shortest PathSame single-source problem but with negative edges allowed; O(VE) and detects negative cycles.
- Network Delay TimeComing soonDirect Dijkstra application — return the max finalized distance, or -1 if any node is unreachable.
- Cheapest Flights Within K StopsComing soonShortest path with a hop limit — Bellman-Ford bounded to K+1 passes, or modified Dijkstra carrying stop count.
- Path With Minimum EffortComing soonDijkstra where path cost is the max edge along the path rather than the sum.