subroute.
Intermediate12 min readlive prototype

Dijkstra's Shortest Path

Single-source shortest paths in a non-negative weighted graph — grow a frontier by always settling the closest unsettled node.

Overview

What this concept solves

Dijkstra's algorithm is BFS for weighted graphs. Instead of a queue that always pops the oldest node, it uses a priority queue that always pops the node with the smallest known distance. Everything else is the same shape: a frontier of seen-but-not-yet-settled nodes, and a settled set of nodes whose shortest-path distance is finalised.

The trick is the greedy choice: at every step, the unsettled node with the smallest distance estimate has its true shortest distance. That's safe to commit to — any path that tried to reach it via some other route would have to go through another unsettled node with an even bigger estimate, which can't improve on what we already have. Once committed, we relax its outgoing edges: for each neighbour, check whether routing through this newly-settled node gives a shorter distance than the neighbour currently has, and update if so.

The only requirement is non-negative edge weights. Negative edges break the greedy choice — a node you committed to could turn out to be reachable more cheaply via a longer-but-cheaper path you hadn't explored yet. For graphs with negatives, you need Bellman-Ford. For everything else — road networks, latency-weighted topologies, fee-weighted routes — Dijkstra is the default.

Mechanics

How it works

The algorithm in five lines

  1. Give every node a distance estimate. The start gets 0, everyone else gets ∞.
  2. Put (start, 0) into a min-priority-queue keyed by distance.
  3. Loop: pop the node u with the smallest distance. If it's already settled, skip it. Otherwise, mark u settled — its distance is now final.
  4. For each edge u → v with weight w: if dist[u] + w < dist[v], update dist[v] = dist[u] + w and push (v, dist[v]) into the priority queue. This is called relaxing the edge.
  5. Repeat until the queue is empty (or you popped the target you cared about).

Why the greedy choice is safe (the cut property)

  • When you pop the unsettled node u with the smallest estimate dist[u], every other unsettled node has a distance estimate ≥ dist[u].
  • Any alternative path to u must pass through some unsettled node w first — and then dist[u] ≤ dist[w] + (cost from w to u) ≤ dist[w] only if every edge weight ≥ 0.
  • So dist[u] can't be beaten — it's the true shortest distance. Settling is safe.
  • This argument breaks the moment a negative edge appears: dist[w] + (negative cost) can be smaller than dist[u], so u could later be reached more cheaply. That's why Dijkstra refuses to run on negative-weight graphs.

Two common implementations

With a binary heap the runtime is O((V + E) log V) — what every library ships. With a Fibonacci heap the analysis drops to O(E + V log V), better in theory but rarely worth the constants in practice. On dense graphs (E ≈ V²), an array-based version is O(V²) and often beats the heap version because of cache effects.

Lazy deletion is the standard trick

When a better path is found, the old (v, oldDist) is still in the heap — heaps don't support remove-by-key. The fix: leave it there and skip stale entries on pop (if (oldDist > dist[v]) continue). The heap can hold up to O(E) entries, so the time bound is O((V + E) log E), which simplifies to O((V + E) log V).

Interactive prototype

Run it. Break it. Tune it.

Sandboxed simulation embedded right in the page. No setup, no install.

About this simulation

A six-node weighted graph and a priority queue. Press Play to watch Dijkstra settle the closest unsettled node and relax its outgoing edges, ring by ring. Step / Back walk one settle at a time. Use the Start dropdown to recompute from a different source.

Hands-on

Try these on your own

Open the prototype above, run each experiment, predict the answer, then verify.

try 01

Play through one full computation

Press Play from the default start. Watch the priority queue (right panel) re-order as edges are relaxed: every time a shorter path is found, the affected node moves up in the queue. The settled set grows ring by ring — but the rings are weighted now, not edge-counted.

try 02

Step through one settle at a time

Hit Step to pop the next node from the priority queue. If its distance is stale (it's already settled with a smaller distance), the prototype shows the skip badge — that's lazy deletion in action. Back rewinds the relaxation: distances roll back to their previous values.

try 03

Try a different start node

Switch Start from A to E. Watch how the shortest-path tree (the highlighted edges) restructures itself: a leaf-start gives a long thin tree, an interior-start gives a balanced one. Note that every node's distance changes — Dijkstra is single-source by design.

try 04

Find the heaviest edge that's *not* in the tree

Look for an edge with a big weight where neither endpoint's shortest path uses it. That edge would only ever be useful if a future change made some other path more expensive. In production routing, those are the edges that absorb failures — they're called backup paths.

In practice

When to use it — and what you give up

When it's the right tool

  • Road maps and GPS routing — every navigation app runs Dijkstra (or a derivative) over a road graph with travel-time weights.
  • Network routing protocols — OSPF and IS-IS run Dijkstra over the network topology to compute shortest paths from a router to every other.
  • Latency-aware load balancing — when picking which backend to call, route through the lowest-latency path. Same algorithm, different weights.
  • Toll / fee minimisation — anywhere a path has a per-edge cost and you want the cheapest one, Dijkstra is the answer.
  • Game maps with movement costs — different terrain has different costs to cross; Dijkstra finds the cheapest path. If you have a known goal and a heuristic, upgrade to A*.

When to reach for something else

  • Negative edge weights — use Bellman-Ford. Dijkstra silently returns wrong answers; Bellman-Ford handles negatives and detects negative cycles.
  • All pairs at once on a small dense graph — use Floyd-Warshall. V calls to Dijkstra is O(V·(V+E)·log V); Floyd-Warshall is O(V³) and often wins for V < a few hundred.
  • Unweighted graph — use BFS. It's the same algorithm minus the heap; O(V + E) vs O((V + E) log V).
  • Single goal with a useful heuristic — use A*. It's Dijkstra with a 'go this way' hint; usually expands far fewer nodes.

Pros

  • Fast — O((V + E) log V) with a binary heap, near-linear in sparse graphs.
  • Correct on non-negative weights — no other classical SSSP algorithm beats it in this regime.
  • Settles one node at a time — easy to stop early once you've settled your target, which is what GPS apps do.
  • The shape under A*, Prim's MST, Yen's k-shortest-paths — once you know Dijkstra, half a dozen other algorithms become obvious variants.
  • Ships in every standard library — Python's heapq, Java's PriorityQueue, C++ std::priority_queue, all you need to write it from scratch.

Cons

  • Wrong on negative edges — the greedy invariant breaks. Use Bellman-Ford.
  • Heap overhead — for very dense graphs the O(V²) array form beats the O((V+E) log V) heap form because of constants.
  • No directional bias — explores symmetrically away from the source. Pathfinding to a single goal can be much faster with A*.
  • Lazy-deletion entries clutter the heap — implementation gotcha; missing the stale-skip check turns the algorithm into a slow correctness landmine.

Reference

Code & further reading

A minimal reference implementation and pointers worth bookmarking.

dijkstra.ts
// Dijkstra's algorithm with a binary heap.
// Returns shortest distances from `start` to every reachable node.
type Edge = { to: string; w: number };
type Heap = Array<[number, string]>;          // [distance, node]

function dijkstra(
  graph: Map<string, Edge[]>,
  start: string,
): Map<string, number> {
  const dist = new Map<string, number>();
  for (const u of graph.keys()) dist.set(u, Infinity);
  dist.set(start, 0);

  const heap: Heap = [[0, start]];
  while (heap.length > 0) {
    const [d, u] = heap.shift()!;             // real code: sift-down
    if (d > (dist.get(u) ?? Infinity)) continue;   // stale entry — skip

    for (const { to: v, w } of graph.get(u) ?? []) {
      const nd = d + w;
      if (nd < (dist.get(v) ?? Infinity)) {
        dist.set(v, nd);
        heap.push([nd, v]);                   // real code: sift-up
      }
    }
  }
  return dist;
}

// Real implementations: replace shift/push with a proper binary heap
// (Python: heapq, Java: PriorityQueue, C++: priority_queue with reverse comparator).
// For a target-only query, return early as soon as you pop the target.

References & further reading

6 sources

Knowledge check

Did the prototype land?

Quick questions, answers revealed on submit. No scoring saved.

question 01 / 03

Why is Dijkstra's algorithm incorrect on graphs with negative-weight edges?

question 02 / 03

What does 'relaxing an edge' mean in Dijkstra's algorithm?

question 03 / 03

Using a binary heap, what is Dijkstra's time complexity?

0/3 answered

Was this concept helpful?

Tell us what worked, or what to improve. We read every note.

Back to Graph Algorithms