What Are We Solving?
You are standing at node A. You want to reach node H. There are many roads between them — each with a different cost. Which route is cheapest?
That is the entire problem. It sounds simple, even trivial. But ask yourself: how would you solve it systematically on a graph with a thousand nodes and ten thousand edges? Brute force — checking every possible path — is catastrophically slow. The number of possible paths grows faster than any reasonable computer can enumerate.
This is the shortest path problem, and it sits at the foundation of nearly every routing system ever built: road networks, packet-switched internet, airline connections, game AI, protein folding, circuit layout. The problem is everywhere because connectivity is everywhere.
The Core Question
Given a weighted graph where each edge has a non-negative cost, find the path from a source node to every other node such that the total cost is minimised. Dijkstra's Algorithm solves this in O((V + E) log V) — fast enough to run in real time on millions of nodes.
Before Dijkstra, there was no efficient general solution. Researchers knew it was solvable — but not how to solve it quickly. The breakthrough came in 1956, in Amsterdam, in roughly twenty minutes.
02 — The Vocabulary
Nodes, Edges, and Weights
Dijkstra's operates on a weighted graph — a mathematical structure of three primitives that can model almost any network you can imagine.
Nodes (Vertices)
The places in your network. Cities on a map, servers in a data centre, rooms in a building, waypoints in a game world. Each node gets assigned a running "distance from source" value that Dijkstra's algorithm updates as it explores.
Edges (Connections)
The roads between nodes. An edge says: "you can travel between A and B." Edges can be directed (one-way) or undirected (two-way). Dijkstra's handles both — most practical implementations use undirected edges for road networks.
Weights (Costs)
The price of using an edge. Kilometres, minutes, dollars, bandwidth — any non-negative numeric value. Weights are what separate Dijkstra's from simple breadth-first search: we're minimising total cost, not total hops.
The Distance Array
Dijkstra's notebook. At initialisation, every node's distance is set to infinity — we haven't found a path yet. As the algorithm explores, it overwrites these values whenever it finds a cheaper route to a node.
The Priority Queue — The Key Data Structure
The most critical ingredient is the priority queue (min-heap): a data structure that always returns the element with the smallest key in O(log n) time. In Dijkstra's, the key is the current known distance. The priority queue ensures we always process the cheapest known node next — the greedy choice that makes the algorithm correct.
Without a priority queue, you would scan all nodes to find the minimum each time, yielding O(V²) — workable for small graphs but unusable at scale.
03 — The Algorithm
How Dijkstra's Works
The core insight is deceptively simple: if you always process the node with the smallest known distance first, you are guaranteed never to find a better path to it later. This is the greedy property, and it is what makes the algorithm both fast and provably correct.
01
Initialise distances
Set the source node's distance to
0. Set every other node's distance to ∞. Insert all nodes into the priority queue keyed by their distance.02
Extract minimum
Pull the node
u with the smallest distance from the priority queue. On the first iteration this is always the source (distance = 0).03
Relax neighbours
For each unvisited neighbour
v of u, compute alt = dist[u] + weight(u, v). If alt is less than the current dist[v], update it and record that we reached v via u. This is relaxation — finding a cheaper route.04
Mark as settled
Node
u is now finalised — its shortest distance is known and will never improve. This is the invariant that makes Dijkstra's correct: greedy extraction + non-negative weights guarantee it.05
Repeat until empty
Return to step 2. Continue until the priority queue is empty (all reachable nodes settled) or until the target node is extracted. Then trace back through the
prev array to reconstruct the path.The Relaxation Condition
The single most important line in the algorithm. Every neighbour check reduces to this:
if dist[u] + weight(u, v) < dist[v]:
dist[v] = dist[u] + weight(u, v)
prev[v] = u
Read it as: "If I can reach
v cheaper by going through u, update the record." The prev array threads a chain of pointers back to the source — reconstruct the path by following prev[target] → prev[prev[target]] → … → source.Pseudocode
DIJKSTRA(Graph G, source s):for each node v in G:
dist[v] = ∞
prev[v] = undefineddist[s] = 0
PQ = PriorityQueue(all nodes, keyed by dist)while PQ is not empty:
u = PQ.extractMin() // node with smallest distfor each neighbour v of u:
alt = dist[u] + weight(u, v)if alt < dist[v]:
dist[v] = alt
prev[v] = u // record shortest path predecessor
PQ.decreaseKey(v, alt)return dist[], prev[]Time Complexity
The dominant operations are the priority queue insertions and extractions. With a binary heap:
- ExtractMin: O(log V) per call, called V times → O(V log V)
- DecreaseKey: O(log V) per call, called at most E times → O(E log V)
- Total: O((V + E) log V)
With a Fibonacci heap,
04 — Live Demo
decreaseKey drops to amortised O(1), giving O(E + V log V) — the theoretical optimum. In practice, binary heaps are faster in cache due to simpler memory layout.Watch It Think
Click Run to watch Dijkstra's settle nodes one by one. Gold is the current node being processed, pink nodes are settled, and the blue path is the final shortest route discovered.
Click any node to set it as the new source. Shift-click any node to set it as the new target. Then run again to see a different shortest path computed.
Watch how the algorithm expands outward like a wavefront from the source. It doesn't march directly toward the target — it settles every reachable node in order of increasing cost. That is why node A→C (cost 2) is settled before A→B (cost 4), even though B might look "closer" visually. Distance in Dijkstra's is always accumulated edge weight, never Euclidean distance.
05 — Why It Exists
The 20-Minute Invention
Edsger Dijkstra designed this algorithm in 1956 while sitting in a café in Amsterdam. He had no pencil, no paper. He was 26 years old.
Dijkstra was working at the Mathematical Centre in Amsterdam and needed a demonstration problem for the ARMAC computer — one of the first stored-program computers in the Netherlands — at a public unveiling. The audience would be non-technical. He needed something visually intuitive but computationally non-trivial.
He chose the problem of finding the shortest route between two Dutch cities on a road network. The algorithm appeared to him almost complete within twenty minutes of thinking. He published it three years later, in 1959, in a two-page paper in Numerische Mathematik.
Dijkstra's Own Words
"One of the reasons that it is so nice is that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually, that algorithm became, to my great amazement, one of the cornerstones of my fame."
The deeper historical motivation was the absence of any efficient algorithm for shortest paths in arbitrary weighted graphs. Before Dijkstra, the only known approaches were exponential-time exhaustive search. His greedy solution provided the first polynomial-time guarantee — and it worked on any graph, not just road maps.
06 — Where It Lives Today
Everywhere You Look
Dijkstra's algorithm — or one of its direct descendants — runs inside almost every routing system built in the last sixty years.
GPS and mapping. Google Maps, Apple Maps, and Waze all use bidirectional Dijkstra or A* variants to compute routes. The graph has hundreds of millions of nodes (road intersections) and edges (road segments with travel-time weights that update in real time with traffic data).
Internet routing. The OSPF protocol (Open Shortest Path First) — one of the backbone routing protocols of the internet — is a direct implementation of Dijkstra's on a network of routers. Every router runs it independently, converging on a consistent view of least-cost paths through the network.
Video game AI. Pathfinding for NPCs in strategy games, role-playing games, and simulations uses Dijkstra's or A*. The game world is a grid or navigation mesh; edge weights encode terrain traversal cost. The algorithm runs hundreds of times per second for large groups of units.
Airline networks. Finding the cheapest or fastest connection between two airports across a graph of routes and layovers. Airlines also use Dijkstra variants for fleet scheduling and crew assignment optimisation.
Chip design. In VLSI circuit layout, routing wires between components on a chip is a shortest-path problem. The grid is nanometre-scale; the weights encode congestion and wire resistance.
07 — The Limits
What It Cannot Do
Dijkstra's correctness proof rests on a single assumption: all edge weights must be non-negative. Violate it and the algorithm produces wrong answers, silently.
No Negative Weights
The greedy invariant — "once settled, always optimal" — only holds when weights are non-negative. With a negative edge, a path through an unsettled node might turn out cheaper than a path through a settled one, breaking the invariant.
Use Bellman-Ford Instead
For graphs with negative edges, Bellman-Ford relaxes every edge V−1 times, guaranteeing correct answers in O(VE) time. It is slower, but it handles the general case and can even detect negative cycles — where the shortest path is negative infinity.
Blind Exploration
Dijkstra's has no knowledge of where the target is. It expands in all directions simultaneously, settling nodes in a circle radiating from the source. On a large graph where source and target are far apart, this means visiting many irrelevant nodes — a significant inefficiency that A* addresses.
Memory at Scale
For very large graphs — the entire road network of a country, or the global internet — storing the priority queue and distance array in a single machine's memory becomes impractical. Real-world systems use preprocessing (contraction hierarchies, hub labelling) that can answer shortest-path queries in microseconds by precomputing shortcuts.
08 — A* and Beyond
The Heuristic Improvement
A* (A-Star), developed in 1968 by Hart, Nilsson, and Raphael, makes one change to Dijkstra's that can reduce explored nodes by an order of magnitude: it adds a heuristic estimate of the remaining distance to the goal.
Where Dijkstra's priority function is:
f(n) = g(n) // actual cost from source to n
A* uses:
f(n) = g(n) + h(n) // actual cost + estimated remaining cost
The heuristic
h(n) must be admissible — it must never overestimate the true remaining cost. Euclidean distance (straight-line to goal) is admissible for road networks. Manhattan distance (grid steps) is admissible for grid maps. A perfect heuristic would lead the algorithm straight to the goal without exploring anything off-path.When
h(n) = 0 everywhere, A* reduces exactly to Dijkstra's — the heuristic is the only thing separating them.The priority queue at the top illustrates the min-heap property: the node with the lowest accumulated cost (node A, distance 3) is always at the front. Below, the grid comparison shows Dijkstra's expanding in all directions (pink) while A* uses the Manhattan heuristic to bias exploration toward the target (blue) — often exploring dramatically fewer cells.
Dijkstra'sBellman-FordA*Floyd-Warshall
| Algorithm | Negative Weights | Heuristic | Time Complexity | Best For |
|---|---|---|---|---|
| Dijkstra's | No | None | O((V+E) log V) | Single-source, non-negative graphs |
| A* | No | Yes | O(E log V)* | Point-to-point on maps and grids |
| Bellman-Ford | Yes | None | O(VE) | Negative weights, cycle detection |
| Floyd-Warshall | Limited | None | O(V³) | All-pairs, small dense graphs |
| BFS | Unweighted | None | O(V+E) | Unweighted graphs (equal edge costs) |
A complexity depends on heuristic quality; a poor heuristic degrades to Dijkstra's.*
09 — Significance
A Way of Thinking
Dijkstra's Algorithm is more than a piece of code. It is a demonstration that greedy local choices can produce globally optimal results — a non-obvious truth that underlies a large fraction of modern algorithm design.
The proof of correctness is instructive. It does not rely on exhaustive search or dynamic programming over all subproblems. It relies on a single invariant: at the moment a node is extracted from the priority queue, its distance is final. Proving this invariant is maintained is a two-line argument by contradiction — assume a cheaper path exists, observe it must pass through an unsettled node with a larger distance, reach a contradiction.
That economy of proof reflects something deeper. Dijkstra was deeply sceptical of unnecessary complexity in both algorithms and software. He famously wrote programs by hand, believed proofs should accompany every piece of code, and spent decades arguing that correctness should be constructed — not tested for after the fact.
Turing Award, 1972
Dijkstra received the ACM Turing Award — computing's Nobel Prize — for "fundamental contributions to programming as a high, intellectual challenge." The award citation mentions both his shortest-path algorithm and his work on structured programming, the seminal paper "Go To Statement Considered Harmful," and the development of the first ALGOL compiler.
The next time your GPS reroutes around a traffic jam in half a second, or a data packet finds its way from London to Singapore through seventeen routers without losing a byte — somewhere in that chain, the ghost of Dijkstra's café-table invention is doing its quiet, exact work.
He designed it without pen or paper. It has been running without pause ever since.