Dijkstra (weighted shortest path)

52 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Four towns, with road times: 2 → 1 takes 1 hour, 2 → 3 takes 1, 3 → 4 takes 1, 1 → 3 takes 4, 1 → 4 takes 6. A message starts at town 2. How long until every town has it? By hand you list routes: to 4 you can go 2 → 1 → 4 (7 hours) or 2 → 3 → 4 (2 hours). The best is 2.

Listing routes works for four towns. For a city map with 100,000 junctions the number of routes is astronomical. Plain breadth-first search does not help either, because it counts roads, not hours: it would think 2 → 1 → 4 and 2 → 3 → 4 are equally good since both use two roads.

Build the structure, one piece at a time

Piece one: a table dist[] holding the best time found so far to each town. Start with 0 for the source and ∞ (unknown) for the rest: dist = {1: ∞, 2: 0, 3: ∞, 4: ∞}.

Piece two: the greedy rule. Among the towns not yet settled, the one with the smallest dist cannot be improved, because any other route to it would have to pass through a town that is already farther. So settle it and use its roads to improve its neighbours. This improving step is called relaxing an edge: if dist[u] + time(u, v) is smaller than dist[v], write the smaller value.

Piece three: finding "the smallest unsettled dist" by scanning the table costs V per step. So keep the candidates in a min-heap, a bag that always hands you its smallest item in log time. Push (0, 2). Pop (0, 2): settle 2, relax 2 → 1 giving dist[1] = 1, relax 2 → 3 giving dist[3] = 1; push (1, 1), (1, 3). Pop (1, 1): settle 1; 1 → 3 offers 5, worse than 1, skip; 1 → 4 offers 7, push (7, 4). Pop (1, 3): settle 3; 3 → 4 offers 2, better than 7, push (2, 4). Pop (2, 4): settle 4 at 2.

Piece four: the heap still contains the old (7, 4). When it surfaces, 4 is already settled, so it is stale and is simply skipped. Leaving stale entries in the heap is cheaper than deleting them.

Why it is correct

The invariant: when a town is popped and settled, its dist is the true shortest time. Suppose not, and some shorter route exists. That route leaves the settled region at some first unsettled town w. Every edge has a non-negative time, so

dist[w] ≤ length of the shorter route < dist[popped town]

But then w had a smaller dist and the heap would have popped w first. Contradiction. This argument needs non-negative times; with negative edges use Bellman–Ford instead.

Why it is fast

Each edge is relaxed once, when its source town is settled, and each successful relaxation pushes one heap entry. So at most E pushes and pops, each log E ≤ 2 log V:

work ≈ E log V

For 100,000 junctions and 300,000 roads that is about 5 million steps.

How to recognise it in an interview

Cues: "shortest time", "minimum cost path", "weights" or "costs" on edges that are all non-negative, a grid where entering a cell costs something. The first thing to say: "non-negative weights, so Dijkstra with a min-heap." Network Delay Time is the example above; the answer is the largest settled dist. Path With Minimum Effort replaces the sum of weights by the maximum weight along the path, and the same pop-the-smallest rule still works because the maximum never decreases as a path grows.

02The idea in one line

Pop the closest unsettled node; relax its edges; stale entries are skipped.

Reach for it when: Network delay, path with min effort, swim in rising water, max probability path.

Cost: O(E log V) time.

03The walk-through, step by step

The video works one example: Network Delay Time on 4 nodes. These are its captions in order, so you can follow without the video or check a step you missed.

1. Start: dist[2] = 0, everything else ∞; push (0, 2)
2. Pop the closest: (0,2). Node 2 is now settled at 0
3. Relax 2→1: 0 + 1 = 1 < ∞, update and push
4. Relax 2→3: 0 + 1 = 1 < ∞, update and push
5. Pop the closest: (1,1). Node 1 is now settled at 1
6. Relax 1→3: 1 + 4 = 5 is not better than 1, keep
7. Relax 1→4: 1 + 6 = 7 < ∞, update and push
8. Pop the closest: (1,3). Node 3 is now settled at 1
9. Relax 3→4: 1 + 1 = 2 < 7, update and push
10. Pop the closest: (2,4). Node 4 is now settled at 2
11. Pop (7,4): node 4 is already settled, stale, skip
12. All settled: the farthest node is 4 at distance 2, so the delay is 2
13. A popped node is final: O(E log V) with a binary heap

04Asked at Google

11 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Graphs: Grid flood fill (components), Multi-source BFS, BFS shortest path (unweighted), BFS over an augmented state, 0-1 BFS (deque), DFS three-colour cycle detection, Topological sort (Kahn's), Union–Find (disjoint sets), Bellman–Ford with k rounds, Minimum spanning tree, Bipartite colouring, Eulerian path (Hierholzer), Bridges / articulation (low-link), Clone / traverse with a visited map, Implicit graph (states as nodes).