Dijkstra's algorithm

The problem it solves

The moment edges get weights, BFS’s promise collapses: fewest edges no longer means lowest cost. A two-hop route of 3 + 4 beats a direct road of 10, and route planners, network packet routing, and every “cheapest way from A to everything” question live in this weighted world. Dijkstra’s algorithm computes lowest-cost paths from one source to all nodes, with one hard precondition that everything else depends on: no negative edge weights.

It earns its place in interviews twice over: directly, as the canonical weighted-shortest-path question, and indirectly, because A* — the game-industry and robotics standard — is exactly Dijkstra with a hint added, and Bellman-Ford is exactly Dijkstra with the greed removed. Understand this one and its neighbours come almost free.

The intuition — and where it breaks down

Water spreading through pipes from one source, at constant speed. The wet frontier reaches junctions in order of their true distance — a junction 7 metres of pipe away gets wet at time 7, full stop, no matter how many pipes lead there. When the water first arrives somewhere, no later arrival can beat it, because any other route flows through junctions that got wet earlier and still had farther to travel.

Dijkstra discretizes the water. Each node holds a tentative distance — the cheapest route found so far — and the algorithm repeatedly makes the boldest legal claim: the unsettled node with the smallest tentative distance is done; its number is final. That claim is safe for exactly the water reason: any hypothetical better route would have to exit through some other unsettled node, whose tentative distance is already ≥ this one, plus more pipe on top. Non-negative pipe. That’s the proof, whole.

And that’s precisely where the analogy breaks: a negative edge is pipe that flows backwards in time. Water cannot arrive before it left, but a cost can shrink en route — and then the “first arrival is final” claim is simply false. Settled nodes would need revisiting; Dijkstra never revisits; wrong answers come out with full confidence. Negative edges don’t slow Dijkstra down, they break its theorem — that’s Bellman-Ford’s territory.

Loading…

A walkthrough you can check

Graph: A→B (1), A→C (4), B→C (2), C→D (1), B→D (6). Source A.

1. A settles at 0. Relax its edges: B gets tentative 1, C gets 4.
2. Smallest unsettled: B (1). Settle it. Relax B→C: 1 + 2 = 3 beats 4 — C’s label drops to 3. Relax B→D: tentative 7.
3. Smallest unsettled: C (3). Settle. Relax C→D: 3 + 1 = 4 beats 7 — D drops to 4.
4. Settle D (4). Done: distances 0, 1, 3, 4.

Two things in that run deserve the stare. First, C’s label changed — tentative numbers are working hypotheses, and the direct road A→C lost to a detour. Second, D’s first offer (7, via B) was beaten before D settled — improvements are only impossible after settling, which is the entire content of the algorithm’s guarantee. The prediction prompts in the visualization target both moments: “which node settles next?” and “does this relaxation improve the label?”.

The invariant

Settled distances are exact, and they leave the priority queue in non-decreasing order. The second half is the checkable version of the first: if a settled value ever came out smaller than a previously settled one, the proof has been violated (or an edge was negative). The trace asserts this ordering as a unit test — the invariant is machine-checked, not just recited.

For the interview, be able to derive rather than recite: suppose node u settles at distance d, but a cheaper path exists. That path leaves the settled region through some unsettled node v with tentative t ≥ d (else v would have settled first), then travels edges summing to ≥ 0. Total ≥ d. Contradiction — and the ≥ 0 step is the exact point a negative edge punctures.

Complexity, derived

Every node settles once: V pops. Every edge relaxes once, when its source settles: E relaxations, each possibly pushing a heap entry. With a binary heap, pushes and pops cost O(log (heap size)), heap size at most E — total O((V + E) log V) for the connected case. The implementation here uses lazy deletion: rather than decrease-key surgery, an improved node is simply pushed again, and stale entries are skipped at pop time — the trace narrates the skip when it happens, because seeing one stale entry surface teaches the technique better than a paragraph. Cost of laziness: a fatter heap, same asymptotics, dramatically simpler code — which is why real implementations overwhelmingly choose it.

The degenerate cases anchor the picture: all weights equal → Dijkstra visits in BFS order and the heap was overhead (use BFS); weights in {0, 1} → a deque suffices (0-1 BFS); dense graph with V² edges → the ancient no-heap O(V²) scan is actually optimal. Knowing when not to pay for the heap is part of knowing the algorithm.

What people get wrong

Running it with negative weights anyway. The failure is silent — plausible-looking wrong distances, no error. If negatives are possible: Bellman-Ford (O(VE), also detects negative cycles), or for the all-pairs version, Johnson’s reweighting trick. Saying those names at the right moment is the follow-up answer.

Settling on push instead of pop. Marking a node “done” when it first enters the queue uses its tentative (possibly improvable) value as final — the walkthrough’s step 3 is a direct counterexample, since D entered at 7 and settled at 4. Done means popped with the smallest label, never merely seen.

Skipping the stale-entry check with lazy deletion. Without if settled(node): continue at pop, a node processes twice with different distances, corrupting downstream relaxations. The check is two lines and non-optional.

Reconstructing paths by re-searching. Store a predecessor pointer at each successful relaxation; the path is a backwards walk. Recomputing routes afterwards is quadratic silliness under pressure.

Implementation notes across languages

Python: heapq + tuples (distance, node) — distance first, so tuple ordering does the comparator’s job; push duplicates, skip stale. Java: PriorityQueue has no decrease-key, which makes lazy deletion not just easier but essentially mandatory; entries as int[]{dist, node} with a comparator, or small records. C++: std::priority_queue is a max-heap — the classic trap; use greater<> or negate distances. All three: the visited/settled structure is a boolean array, and the distance array initializes to infinity except source zero. And in all three, A* is a ten-line diff from what you just wrote — priority becomes dist + heuristic(node) — which is the cheapest “senior” flourish available in this corner of the interview map.