cf.completefrontend
GRAPHS · CORE

Dijkstra's algorithm

Find the cheapest path from one start to every node when edges have non-negative costs, always growing from the closest unfinished node.

Time O((n + e) log n)Space O(n + e)5 practice problemsStep-through picture

The idea

When edges have different costs, such as travel times or prices, the path with the fewest edges is not always the cheapest. Dijkstra's algorithm finds the cheapest total cost from a start node to every other node, as long as no edge has a negative cost.

It keeps a best-known distance dist for every node. At each step it picks the unfinished node with the smallest dist. That distance can't get any better, because every other route would have to go through a node that is already at least as far away and then add a cost that is 0 or more. So that node is finished, and it tries to improve its neighbors' distances.

Picking the smallest quickly needs a priority queue, a structure that always hands back its smallest item. JavaScript doesn't have one built in, so the template includes a small binary heap with push and pop.

An everyday example

Water flowing through pipes

Pour water into one end of a network of pipes, where longer pipes take longer to fill. The water reaches each junction at the earliest possible time, and at that moment it starts flowing into every pipe leaving that junction. Junctions fill up in order of how quickly water can get to them. Dijkstra's algorithm visits nodes in that same order.

How the example maps to the code
In the exampleIn the code
The pipe junctionsNodes
How long a pipe takes to fillAn edge's weight
The earliest time water reaches a junctiondist[node]
The junction that fills nextpop(heap), the smallest d
Water entering the next pipesTrying d + weight for each neighbor

From the slow way to dijkstra's algorithm

  1. Start with the obvious way: list every path from the start to each node, add up each path's cost, and keep the smallest. The number of paths grows exponentially with the size of the graph. BFS is fast, but it finds the path with the fewest edges, and with costs a three-edge path costing 3 beats a one-edge path costing 10.
  2. Cheapest paths are made of cheapest paths. If the cheapest route to C goes through B, then the part that ends at B is also the cheapest route to B. So once we know B's final cost, we can offer each neighbor the price dist[B] + weight and never need to look at other routes into B again.
  3. Which node's cost is final first? The start, at 0. After that, look at every node reached so far and take the one with the smallest known cost. Any other route to it must leave the finished nodes through a node that costs at least as much, then add edges that cost 0 or more, so it can't be cheaper. Finish that node, offer prices to its neighbors, and repeat.
  4. Scanning all nodes for the smallest cost takes n steps each time. A min-heap hands back the smallest entry in O(log n) instead. Rather than finding and changing an entry inside the heap when a price drops, push a new entry and skip the old one when it comes out later. A heap of [d, node] pairs, popped until empty, with outdated entries skipped: that loop is Dijkstra's algorithm.

How it works

  1. Build graph with [to, weight] pairs. Set every dist to Infinity, except dist[start] = 0.
  2. Put [0, start] in the min-heap heap.
  3. Pop the entry [d, node] with the smallest d.
  4. If d is bigger than dist[node], it is an old entry from before a cheaper route was found: skip it.
  5. For each edge [next, weight], if d + weight is smaller than dist[next], store it and push [dist[next], next].
  6. When the heap is empty, dist holds the cheapest cost from start to every node, or Infinity if unreachable.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function dijkstra(n, edges, start) {
  2. const graph = Array.from({ length: n }, () => []);
  3. for (const [from, to, weight] of edges) graph[from].push([to, weight]);
  4. const dist = new Array(n).fill(Infinity);
  5. dist[start] = 0;
  6. const heap = [[0, start]];
  7. while (heap.length > 0) {
  8. const [d, node] = pop(heap);
  9. if (d > dist[node]) continue;
  10. for (const [next, weight] of graph[node]) {
  11. if (d + weight < dist[next]) {
  12. dist[next] = d + weight;
  13. push(heap, [dist[next], next]);
  14. }
  15. }
  16. }
  17. return dist;
  18. }
  20. function push(heap, item) {
  21. heap.push(item);
  22. let i = heap.length - 1;
  23. while (i > 0 && heap[(i - 1) >> 1][0] > heap[i][0]) {
  24. const parent = (i - 1) >> 1;
  25. [heap[parent], heap[i]] = [heap[i], heap[parent]];
  26. i = parent;
  27. }
  28. }
  30. function pop(heap) {
  31. const top = heap[0];
  32. const last = heap.pop();
  33. if (heap.length === 0) return top;
  34. heap[0] = last;
  35. let i = 0;
  36. while (true) {
  37. let small = i;
  38. for (const child of [2 * i + 1, 2 * i + 2]) {
  39. if (child < heap.length && heap[child][0] < heap[small][0]) small = child;
  40. }
  41. if (small === i) return top;
  42. [heap[small], heap[i]] = [heap[i], heap[small]];
  43. i = small;
  44. }
  45. }

How fast it is

TimeO((n + e) log n)
Extra memoryO(n + e)

Each edge can push one heap entry, and each push or pop costs O(log n) because the heap is a balanced tree. The graph, dist, and the heap hold O(n + e) entries.

  • Best caseO(n + e)

    A simple chain like 0 → 1 → 2 → 3: the heap never holds more than one entry, so each push and pop is constant, and building graph dominates.

  • Average caseO((n + e) log n)

    A typical graph, where the heap holds many entries and each push or pop costs about log n swaps.

  • Worst caseO((n + e) log n)

    A dense graph where most edges lower a price, so nearly every edge pushes an entry. The heap can hold up to e entries, and log e is at most 2 log n.

Common mistakes

  • Using it with negative edge costs. A node can be finished too early; use Bellman-Ford instead.
  • Forgetting the if (d > dist[node]) continue check. Old entries then relax edges again, which wastes time.
  • Sorting an array on every step instead of using a heap. That turns each step into O(n log n).
  • Marking a node as finished when it is pushed instead of when it is popped. A cheaper route can still be found after the push.
  • Returning Infinity in a problem that wants -1 for unreachable nodes. Convert at the end.

When to use it

Look for these clues in a problem:

  • Edges have costs, times, or distances, and the question asks for the cheapest, fastest, or shortest total.
  • All costs are 0 or positive.
  • You need the cheapest path from one start to one or all nodes.
  • The "cost" of a path is built step by step, such as the largest step so far or a product of probabilities, and never gets better as the path grows.

Check yourself

Answer each one in your head first, then open it.

Why must a node be marked finished when it's popped, not when it's pushed?

A cheaper route can still be found after the push, like node 1 in the trace: pushed at 6, finished at 5. Only the pop of the smallest entry proves the cost is final.

How many entries can the heap hold at once?

Up to one per edge that lowered a price, plus the start, so O(e). That's why the time has log e, which is at most 2 log n.

What goes wrong if the if (d > dist[node]) continue line is removed?

Old entries would relax their node's edges again with a worse d. The final answer stays correct because those offers lose, but the work can grow a lot.

Why is the < in d + weight < dist[next] strict?

With <=, a tie would push a duplicate entry that improves nothing, as with node 4 at 14 in the trace. Strict < keeps the heap smaller.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 5 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

easy

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

Two rules hold the whole time. First, every dist value is the cost of some real path, so it is never lower than the true cheapest cost. Second, when an entry [d, node] comes out of the heap and isn't skipped, d is the true cheapest cost of node.

Here's why the second rule holds. Suppose some path P to node costs less than d. P starts at a finished node and ends at node, so it has a first node Y that isn't finished. The node just before Y was finished, and at that moment it offered Y a price no bigger than the cost of P up to Y. Since every edge costs 0 or more, that part of P costs no more than all of P, which is less than d. So the heap holds an entry for Y smaller than d, and it would have come out before [d, node]. That contradicts how a min-heap works.

The loop ends because each push comes from a strict drop of some dist[next], and each node relaxes its edges only once, when it's finished. That's at most one push per edge, plus the start. When the heap is empty, every node that can be reached has been finished at its true cost, and every other node still has Infinity.

Going deeper

3 more ideas

Why the smallest popped distance is final

When [d, node] is the smallest entry in the heap, every other route to node must leave the finished area through some node whose distance is at least d, and then add edges that cost 0 or more. So no other route can cost less than d. This is why negative edges break the algorithm: a negative edge later on could make a "finished" node cheaper.

How the heap keeps it fast

A binary heap stores items in an array so that each item is no bigger than its two children, at indexes 2i + 1 and 2i + 2. The smallest item is always at index 0. push adds at the end and swaps it up while it is smaller than its parent; pop moves the last item to the top and swaps it down. Both take O(log n), so the whole algorithm is O((n + e) log n).

Stopping early and rebuilding the path

If you only need the cost to one target, return as soon as the target is popped: its distance is final. To rebuild the route itself, keep a prev array and set prev[next] = node whenever dist[next] improves. Then walk prev back from the target.

Work it by hand

Every step in a table, with why

Six nodes from start 0. Node 1 gets cheaper twice, three outdated heap entries get skipped, and node 5 is never reached.

n = 6, edges = [[0,1,6], [0,2,2], [2,1,3], [2,3,7], [1,3,2], [1,4,9], [3,4,1], [2,4,12]], start = 0

StepPop [d, node]Prices that improvedist afterWhat happensWhy
1[0, 0]1: 6, 2: 2[0, 6, 2, ∞, ∞, ∞]Push [6, 1] and [2, 2]The start is the only entry. Both of its neighbors had Infinity, so both improve.
2[2, 2]1: 5, 3: 9, 4: 14[0, 5, 2, 9, 14, ∞]2 + 3 = 5 beats 6Node 2 is the closest unfinished node. Going through it is cheaper for node 1, so a new entry [5, 1] is pushed. The old [6, 1] stays in the heap.
3[5, 1]3: 7[0, 5, 2, 7, 14, ∞]5 + 9 = 14 doesn't beat 14Node 1 lowers node 3 from 9 to 7. For node 4 the new price ties the old one, and < is strict, so nothing is pushed.
4[6, 1]noneunchanged6 > dist[1]: skipThis is the old entry for node 1. Its distance 6 is bigger than the stored 5, so the continue throws it away.
5[7, 3]4: 8[0, 5, 2, 7, 8, ∞]7 + 1 = 8 beats 14Node 3 is finished at 7, through 0 → 2 → 1 → 3. Its edge to node 4 gives a much cheaper price.
6[8, 4]noneunchangedFinished, no edges outNode 4 is finished at 8. It has no outgoing edges, so there is nothing to offer.
7[9, 3]noneunchanged9 > dist[3]: skipAn outdated entry for node 3 from when its price was still 9.
8[14, 4]noneunchanged14 > dist[4]: skipThe last outdated entry. After this pop the heap is empty and the loop ends.

It returns [0, 5, 2, 7, 8, Infinity] after 8 pops: 5 finished nodes and 3 skipped entries. Node 5 has no edges coming into it, so it keeps Infinity.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
Dijkstra's algorithmO(e log n)O(n + e)Costs are 0 or more and you need the cheapest cost from one start.
BFSO(V + E)O(V)Every edge costs the same, so the fewest edges is also the cheapest.
0-1 BFSO(V + E)O(V)Every edge costs either 0 or 1. A double-ended queue replaces the heap.
Bellman-FordO(n · e)O(n)Some edges are negative, or you must detect a loop that keeps getting cheaper.

Extra memory: O(n + e): the adjacency lists hold every edge, dist holds n numbers, and with lazy skipping the heap can hold one entry per improving edge.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for Dijkstra's algorithm and the other approaches, on a scale where each line up is 10 times more steps.
  • Dijkstra's algorithm O(e log n)
  • BFS, 0-1 BFS O(V + E)
  • Bellman-Ford O(n · e)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
Dijkstra's algorithm339,96620 million
BFS202,0002 million
0-1 BFS202,0002 million
Bellman-Ford1001 million1 trillion

Inputs that need care

5 tricky inputs
A node no edge leads to, like node 5 in the trace
It never gets an entry, so dist stays Infinity. Convert to -1 at the end if the problem asks for that.
A start with no outgoing edges
The first pop finishes the start and offers nothing. It returns 0 for the start and Infinity for everything else.
Edges that cost 0
They work. d + 0 < dist[next] is strict, so a tie never pushes a duplicate entry.
A negative edge: [[0,1,2], [0,2,5], [2,1,-4], [1,3,1]]
This lazy version pushes node 1 again when its price drops, so here it still ends with [0, 1, 5, 2]. But it loses its speed guarantee, an early stop at target 1 would return 2 instead of 1, and a negative loop makes it run forever. Use Bellman-Ford.
Two edges between the same pair, with costs 4 and 9
Both are relaxed. The cheaper one sets the price; the other fails the < test or leaves an outdated entry that gets skipped.

Variations and follow-ups

Twists interviewers add

Stop at the target

If you only need one target's cost, return d as soon as [d, target] is popped and not skipped. The proof above says that value is final. Stopping when the target is pushed is wrong, because a cheaper route can still turn up.

Several starts at once

To find the distance from the nearest of several sources, such as the closest open store, set each source's dist to 0 and put all of them in the heap at the start. It's one run, not one per source.

Other ways to combine costs

The proof only needs path costs that never go down as a path gets longer. So you can replace d + weight with Math.max(d, weight) to minimize the steepest single step on a route, or work with probabilities by maximizing a product of values between 0 and 1.

Without a heap, for dense graphs

Keep a done array and scan all n nodes for the smallest unfinished dist each round. That's O(n²) total, which beats O(e log n) when nearly every pair of nodes has an edge.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from "cheapest", "fastest", "minimum total cost", or "network delay" with costs on the edges, and no costs below zero. If every cost is the same, say so and use BFS instead.
  • Explain the key step out loud: "the smallest entry in the heap is final, because every other route would leave through something at least as expensive and only add more". That one sentence covers both why it works and why negative edges break it.
  • Test by hand a graph where the direct edge is more expensive than a two-edge detour, like 0 → 1 costing 6 against 0 → 2 → 1 costing 5. Check that the old entry is skipped and doesn't relax edges again.
  • Expect "how do you get the path, not just the cost?". Answer: keep prev[next] = node whenever dist[next] improves, then walk prev back from the target and reverse the list.

Where frontend code uses it

The same idea in real UI code
  • Map and directions features in web apps compute fastest routes with Dijkstra's algorithm or its faster cousin A*.
  • Network and dependency dashboards that show the fastest path for a request through a service graph, using measured latencies as edge weights.
  • Diagram editors that route connector lines around boxes find the cheapest path on a grid, where turns or crossing cost extra.

Related algorithms