Skip to content

level 7 · Graphs

Dijkstra's Shortest Path

The cheapest route through a weighted map — always finish the nearest place first.

14 min 110 XP

what is it

Start here

Breadth-first search finds the shortest path when every step costs the same. But real maps aren't like that: one road is 4 km, another is 12. Now 'fewest roads' and 'shortest distance' are completely different questions.

Dijkstra's algorithm answers the second one. It keeps a running best-known cost to every place, starting at ∞ for everywhere except home, which costs 0. Then it does one thing, over and over: take the **closest place it hasn't finished yet**, and declare its cost final.

Why is it safe to declare it final? Because if that's the nearest unfinished place, any other route to it would have to travel through somewhere even further away first — and then it would already cost more. So no shortcut can exist. That single argument is the whole proof.

Then it 'relaxes' each neighbour: is going through this place cheaper than what we already knew? If so, write down the better number. This is the algorithm behind every route your maps app has ever given you.

One warning the proof makes obvious: it collapses if a road can have a **negative** cost. Then a longer detour really could turn out cheaper, and 'nearest so far' means nothing. That's why Bellman–Ford exists.

real-life analogy

Picture it

Ink spreading through a network of pipes

Pour ink in at home. It spreads through the pipes at a steady speed, so it reaches each junction exactly at that junction's shortest distance. The moment ink first arrives somewhere, that arrival time *is* the shortest path — it couldn't have gotten there any faster by any other route.

interactive visualization

Watch it run

Pick a start node: 1 = A, up to 7 = G. Numbers on the roads are their cost.

425108122634
A 0
B ∞
C ∞
D ∞
E ∞
F ∞
G ∞

Find the cheapest route from A to everywhere. Every node starts at ∞ — unreachable as far as we know — except A, which costs 0 to reach from itself.

step 01/28

  • just discovered
  • visited
  • found it
  • visiting now
1function dijkstra(graph, start) {
2 const dist = {};
3 for (const v of graph.nodes) dist[v] = Infinity;
4 dist[start] = 0;
5 const done = new Set();
6
7 while (done.size < graph.nodes.length) {
8 // the unfinished node with the smallest known distance
9 const u = closest(dist, done);
10 if (u === null) break;
11 done.add(u);
12
13 for (const [v, w] of graph.edges[u]) {
14 if (dist[u] + w < dist[v]) {
15 dist[v] = dist[u] + w;
16 }
17 }
18 }
19 return dist;
20}

variables right now

start
A
A
0
comparisons 0moves 0

the dry run · every step, in words

28 steps

complexity

What it costs

best case
O(E log V)
average
O(E log V)
worst case
O(E log V)
extra memory
O(V)

With a priority queue (a heap!) to grab the nearest unfinished node, it's O(E log V). Without one you scan every node each round, giving O(V²) — still fine for small dense graphs. This is a real payoff from the Heap lesson.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n) · this one
  • O(n²)
input size →work →

common mistakes

Common traps

  • Using Dijkstra on a graph with negative edge weights.

    It will confidently return the wrong answer. 'Nearest unfinished node is final' is only true when travelling further can't make things cheaper. Use Bellman–Ford for negative edges.

  • Re-finalising a node that's already done.

    Once a node is finalised, skip it forever. Popping stale entries out of the priority queue without checking is a classic source of wrong answers and infinite work.

  • Confusing Dijkstra with BFS.

    BFS finds the fewest *edges*; Dijkstra finds the lowest *total weight*. On an unweighted graph they agree — and Dijkstra reduces to BFS exactly.

  • Scanning every node to find the closest, on a big graph.

    That's O(V²). Use a priority queue so 'get me the closest' costs O(log V) instead of O(V).

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+110 XP

01Why can Dijkstra declare the nearest unfinished node's distance final?

02What breaks Dijkstra?

03What data structure makes Dijkstra fast?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.