Dijkstra's Algorithm Explained — Shortest Paths, Step by Step

Dijkstra's algorithm answers one of the most useful questions in computer science: given a weighted graph and a starting point, what is the cheapest way to reach every other node? It powers driving directions, network routing, and game AI — and the core idea fits in a sentence: always expand the closest thing you have not finished yet.

In this guide we will walk a complete example update by update, see why the greedy choice is provably safe, understand where the O((V+E) log V) complexity comes from, and look at the one assumption that, if violated, silently breaks everything: non-negative edge weights.

The problem it solves

Dijkstra's algorithm solves the single-source shortest path problem on graphs with non-negative edge weights. You pick one source node, and the algorithm computes the minimum total weight to reach *every* other node — not just one destination. If your graph is unweighted (every edge costs the same), you do not need Dijkstra at all: plain breadth-first search already finds shortest paths by hop count. Dijkstra exists for the moment edges stop being equal — when one road is 3 km and another is 40.

The greedy insight — and why it is actually correct

The algorithm maintains a tentative distance for every node (source = 0, everything else = infinity) and repeatedly does one thing: take the *unvisited node with the smallest tentative distance*, mark it finished, and update its neighbours. Once a node is marked finished, its distance is final — the algorithm never reconsiders it.

That sounds reckless. How can we be sure no better path shows up later? Here is the proof intuition. Suppose node u currently has the smallest tentative distance among all unfinished nodes. Any *alternative* path to u must, at some point, step out of the finished region through some other unfinished node x. But the path's cost up to x is already at least dist(x), and dist(x) ≥ dist(u) — we chose u precisely because it was the minimum. Since every remaining edge has non-negative weight, the rest of that alternative path can only add cost. So no detour can beat dist(u), and it is safe to lock it in. The entire correctness of the algorithm hangs on that phrase "can only add cost" — remember it for the negative-weights section.

Step-by-step trace on a real graph

Take a small directed graph with five nodes, A through E, and these weighted edges:

• A → B, weight 4
• A → C, weight 1
• C → B, weight 2
• B → D, weight 5
• C → D, weight 8
• D → E, weight 3

We start at A. Every step, we pop the closest unfinished node and relax its outgoing edges. "Relaxing" edge u → v just means asking: is dist(u) + weight(u,v) smaller than the best distance to v we currently know? If yes, we found a shortcut — record it.

1. Pop A (dist 0). Relax A→B: 0 + 4 = 4, better than ∞ → dist(B) = 4. Relax A→C: 0 + 1 = 1 → dist(C) = 1.
2. Pop C (dist 1 — smaller than B's 4). Relax C→B: 1 + 2 = 3, which beats the existing 4 → dist(B) = 3. Relax C→D: 1 + 8 = 9 → dist(D) = 9.
3. Pop B (dist 3). Relax B→D: 3 + 5 = 8, which beats 9 → dist(D) = 8.
4. Pop D (dist 8). Relax D→E: 8 + 3 = 11 → dist(E) = 11.
5. Pop E (dist 11). No outgoing edges. Every node is finished.

Final answer: A=0, C=1, B=3, D=8, E=11. Notice that B's first recorded distance was *wrong*: the direct edge A→B costs 4, but the detour through C costs only 3. The algorithm caught the correction because C — the cheapest frontier node — was processed *before* B was finalized. That ordering is the whole trick. Similarly, D was first reached via C (cost 9) and improved via B (cost 8) while it was still sitting on the frontier.

The pseudocode

dist[source] = 0; dist[v] = infinity for all other v
pq = min-priority-queue containing (0, source)

while pq is not empty:
  (d, u) = pq.extractMin()
  if u already finalized: continue   // stale entry
  finalize u
  for each edge (u, v) with weight w:
    if dist[u] + w < dist[v]:        // relaxation
      dist[v] = dist[u] + w
      pq.insert((dist[v], u -> v))

The priority queue and the complexity

The expensive operation is "give me the unfinished node with the smallest distance". Scanning all nodes every time costs O(V) per pop, giving O(V²) overall — fine for dense graphs, painful for sparse ones. The standard fix is a binary min-[heap](/workspace/heap): extractMin and insert each cost O(log n), so the closest node is always one pop away.

Every node is extracted once, and every edge is relaxed once, with each relaxation possibly pushing a new entry into the heap. Add it up and you get O((V + E) log V) with a binary heap. A Fibonacci heap improves the theoretical bound to O(E + V log V), but in practice the binary heap's simplicity and cache behaviour usually win.

Why negative edges break it

Recall the proof: a detour "can only add cost" because edge weights are non-negative. A single negative edge destroys that argument. Here is a three-node counterexample. Nodes A, B, C, with edges A→B weight 1, A→C weight 2, and C→B weight −2.

Dijkstra from A pops A, setting dist(B) = 1 and dist(C) = 2. Then it pops B — the closest frontier node — and finalizes B at distance 1. Only afterwards does it pop C and discover the edge C→B: 2 + (−2) = 0, a genuinely shorter path. But B is already finalized, so the algorithm never applies the update. It confidently reports 1 when the true shortest distance is 0. For graphs with negative edges you need Bellman-Ford, which trades the greedy shortcut for O(V·E) exhaustive relaxation — slower, but immune to this trap.

Where you meet it in the real world

• Road navigation — map routing engines are built on shortest-path search; production systems layer heuristics and precomputation on top, but the foundation is Dijkstra.
• Network routing — OSPF, one of the internet's core link-state routing protocols, literally runs Dijkstra's algorithm on each router to build its forwarding table (the spec calls it the shortest-path-first computation).
• Game pathfinding — units navigating a map with varying terrain costs (swamp = slow, road = fast) are solving weighted shortest path; A* is the usual refinement.
• Anything modelled as weighted steps — cheapest flight itineraries, minimum-cost workflows, currency conversion chains.

Relationship to BFS and A*

Dijkstra sits in the middle of a neat family. Set every edge weight to 1 and the priority queue always pops nodes in the order they were discovered — the algorithm *becomes* BFS, and the min-heap degenerates into a plain queue. Going the other direction, give Dijkstra a hint about where the goal is and it becomes A*: instead of ordering the frontier by dist(u), A* orders it by dist(u) + h(u), where h is an estimate of the remaining distance. With h = 0 everywhere, A* *is* Dijkstra. With a good (admissible) heuristic, it explores far fewer nodes while returning the same answer — which is why games use A* and routers, which have no single goal, use Dijkstra.

Try it yourself

The distance table above is worth ten re-readings of the proof. Run the algorithm on a random weighted graph, watch tentative distances drop as edges relax, and pay attention to the exact moment each node freezes. Once you can predict which node gets popped next, you understand Dijkstra.