Interactive Lab · Algorithms & Data Structures
Given a weighted map, how do you find the cheapest route from one place to every other? The trick that makes Dijkstra's algorithm work is deceptively simple: repeatedly pick the nearest node you haven't settled yet, lock in its distance forever, and then relax its edges, try to improve every neighbour's tentative distance through it. A priority queue (a min-heap) hands you the nearest unsettled node in O(log n), and once a node comes off the queue its shortest distance is final. Below is a real weighted graph. Step the algorithm one settle at a time and watch a surprising truth appear, the shortest route to the far node isn't the direct-looking edge; it's the five-hop way round.
🎬 Watch the 90-second explainer, then find the shortest paths yourself below ↓
▶ The playground, step Dijkstra one "settle" at a time from A
Filled = settled (distance final). Outlined = in the priority queue with a tentative distance. Faint = not reached yet (∞). Bold gold edges are the growing shortest-path tree; the number on each node is its best-known distance from A. Drag the slider to settle the next-nearest node.
Dijkstra's algorithm is the ancestor of every routing system: Google Maps ETAs (with A* and heuristics on top), network packet routing (OSPF), ride-share dispatch, and game pathfinding. The non-negative-weights guarantee you just probed is exactly why tolls and travel times work but “discount” edges need Bellman-Ford instead.
The code that's actually running, pop the nearest, relax its edges
Look at node D. The tempting route is A → C → D = 2 + 8 = 10. Predict: that is not its shortest distance. Step the algorithm and watch D settle at 8because relaxing through B (A → C → B → D = 2 + 1 + 5) beats the direct edge. Now the deeper one: the shortest path all the way to F is the five-hop A → C → B → D → E → F = 13, longer in hops than any alternative yet cheaper in total weight. So here's the question Dijkstra's whole correctness rests on: why is a node's distance guaranteed final the instant it comes off the priority queueand what one property of the edge weights would break that guarantee?
The takeaway
u → v, if dist[u] + w < dist[v], you found a cheaper way to v: update it and remember u as its predecessor. The predecessors form the shortest-path tree.O(log n); the whole run is O((V + E) log V). That heap is exactly the binary heap you can build in the sister lab.