Dijkstra's Algorithm · Compound Engineer

Concept · Shortest path

Intermediate · O((V + E) log V) time · O(V + E) space

Why it exists

A map has towns joined by roads, and each road has a length. You want the shortest route from one town to every other. Breadth-first search counts roads, not kilometres, so it picks the route with the fewest roads, which can be far longer.

Trying every route works but explodes: the number of routes grows exponentially with the number of roads. Repeating a search from each town with a "best so far" check is better but still wastes work, because the same town is reached again and again by routes we already know are worse.

We only need one number per town: the length of its shortest route. Which town's number can we be sure of right now?

The core idea

Keep a tentative distance for every town: the shortest route found so far. It starts at ∞ for every town except the start, which is 0. Then repeat one move:

Take the unfinished town with the smallest tentative distance. Declare it final. Then look at its roads. For each neighbour, check whether going through this town is shorter than what the neighbour has. If it is, update the neighbour. This check is called a relaxation.

The unfinished town with the smallest distance is already final, because every other route to it must pass through a town that is at least as far away.

A min-heap makes "take the smallest" cheap. We push every improved distance into it as a (distance, town) pair.

A worked example

Five towns, six roads, and the start is town 0. The number beside a town is its tentative distance. The number on a road is its length.

Start. Town 0 is final at 0. Its roads give town 1 a distance of 4 and town 2 a distance of 1.

An improvement. The smallest unfinished town is 2, at distance 1. Through it, town 1 costs 1 + 2 = 3, which beats the 4 it had. The distance of town 1 drops to 3, and a new entry goes into the heap.

A stale entry. The old entry (4, town 1) is still in the heap. When it comes out, town 1 already has 3, so the entry is stale and we throw it away. The same happens to (9, town 3) later, after town 3 improves to 8.

Done. Every town is popped once with its final distance: 0, 3, 1, 8 and 11. The roads that gave each town its distance form the shortest-path tree.

How it works

Set every distance to ∞ except the start, which is 0. Push (0, start).
Pop the smallest (d, u). d is larger than dist[u]⟶stale, skip it
For each road (u, v, w): d + w < dist[v]⟶set dist[v] = d + w and push (d + w, v)
Repeat until the heap is empty. Every reachable town now has its shortest distance.

Why it is correct

Say we pop town u at distance d. Suppose a shorter route to u existed. It starts in the finished area and has to leave it through some road to an unfinished town x. That town is still waiting in the heap, so its distance is at least d, because we popped the smallest. The rest of the route from x to u can only add length, so the whole route is at least d. No shorter route exists, and d is final.

Why edges cannot be negative

The step "the rest of the route can only add length" is where the proof needs non-negative roads. With a negative road, a long first leg followed by a big negative one could beat a town we already finalised. Dijkstra would then return a wrong answer without any error.

Watch it run

Pick an input, then press Play or use the arrow keys. The highlighted line is the one running, and the number beside each line counts how often it ran. The graph shows the tentative distance by each town and draws the current shortest-path tree. The heap on the right holds the pending entries, smallest on top.

Complexity

O((V + E) log V)

Time. Here's why: each road can improve a distance at most once per direction, so at most 2E entries are ever pushed, and each push or pop on a heap costs O(log V). A pop that finds a stale entry costs O(log V) and nothing more. Each town is expanded once, which scans its roads for O(V + E) in total.

O(V + E)

Space. The adjacency lists hold V lists and 2E entries. dist holds V numbers. The heap holds at most 2E entries, because stale entries stay until they are popped.

Mistakes and variants

Forgetting the stale check. Without if d > dist[u]: continue, a town is expanded once for every entry it has. The answer is still correct, but the running time can grow badly.
Negative edges. Dijkstra can silently return wrong distances. Use Bellman-Ford instead, which allows negative edges and costs O(V × E).
Stopping early. If you only need the distance to one target, return as soon as that target is popped. Its distance is final at that moment.
A different cost. Only the "add" step changes the meaning. Swapping d + w for max(d, w) finds the route whose worst road is smallest, which is how grid problems like Swim in Rising Water use it.
A plain array instead of a heap. Scanning an array for the smallest unfinished town costs O(V) per pick, or O(V²) overall. That beats a heap only on very dense graphs.

Where it shows up

Reach for it when:

roads, edges or steps have different non-negative costs, and you want the cheapest route;
"fewest steps" would be BFS, but each step costs something different;
the cost of a path is not a sum but a worst step (a maximum), and the same greedy idea still applies.

Problems that use it:

Swim in Rising Water

Interviewer follow-ups

These are the questions that usually come next. Open one to see an answer you could say out loud.

"What if one road has a negative length?"

What they are checkingWhether you know why the algorithm works, not only the steps. They want to see you point at the exact line of the proof that breaks.

A strong answerThe proof says a route through an unfinished town can only be longer. A negative road breaks that, so a town we finalised could later get a shorter route and Dijkstra would not notice. I would use Bellman-Ford, which is O(V × E), and it can also report a negative cycle. If the graph has no cycles, a topological order is faster.

"The graph is almost fully connected. Is a heap still the right choice?"

What they are checkingWhether you tie the data structure to the shape of the input instead of using the same answer every time.

A strong answerWith E close to V², the heap costs about V² log V. Scanning an array for the smallest unfinished town costs O(V) per pick and O(V²) overall, with no heap overhead. So on a dense graph the plain array is better. On a sparse graph, where E is near V, the heap is better.

"I only need the route to one town, in a graph with millions of towns. What do you change?"

What they are checkingWhether you can stop work you do not need, and whether you can return the route itself instead of only its length.

A strong answerStop as soon as the target is popped, since its distance is final then. To return the route, record parent[v] = u each time a distance improves, and walk back from the target. It still explores everything closer than the target, so if the data allows a good estimate of the remaining distance, A* uses that to explore far fewer towns.