A step-by-step explainer
From scanning a flooded map outward to A*'s clever guess, and finally to the trick that lets a phone route across a continent in milliseconds.
The whole idea, in one sentence
Finding the shortest route is just spreading water out from where you are — A* makes the water spread toward the destination instead of in every direction at once, and graph partitioning pre-computes the highways so the water can jump across regions in a single step.
Step 1 · the setup
Strip away the prettier rendering and a map is a graph: dots (intersections, called nodes) connected by lines (roads, called edges). Each edge carries a number — the time or distance to travel it.
The question your phone has to answer is simple to state: among all paths from A to B in this graph, which one has the smallest total cost? The widget below is a tiny city. Click any cell to drop a wall (a closed road, a river, a building), or shift-click to move the start or goal. There are usually many viable routes; only one is shortest.
Step 2 · brute force, but smart
Imagine pouring water at the start. It rushes into every neighboring cell at unit cost, then into each of their neighbors at cost 2, then 3, and so on. As long as the water always reaches a cell by its cheapest possible route first, the moment it splashes onto the goal you've found the shortest path.
This is Dijkstra's algorithm. The crucial trick is the order: always expand from the cheapest-so-far cell on the boundary of the flood. Press play and watch the flood swell outward in equal-cost rings.
Zoomed out, the flood is intuitive. Zoomed in, it's just a tiny bookkeeping loop on a graph. The widget below lays the pseudocode beside a six-city map and walks through them in lockstep — each click executes one operation, highlights the line that ran, and updates the running state on the right.
Let \(G=(V,E)\) be a graph with non-negative edge weights \(w:E\to\mathbb{R}_{\ge 0}\). Write \(d(s,v)\) for the true shortest-path cost from the source \(s\) to a node \(v\). Dijkstra maintains an upper bound \(g(v) \ge d(s,v)\) for every \(v\), initialized as
\( g(s)=0, \quad g(v)=\infty \text{ for } v\ne s. \)
A min-priority queue holds every unsettled node keyed by its current \(g\). Repeat: pop the node \(u\) with smallest \(g(u)\), mark it settled, and relax each outgoing edge \((u,v)\):
\[ g(v) \;\leftarrow\; \min\!\big(g(v),\; g(u) + w(u,v)\big). \]
Why first-pop equals shortest. Claim: when \(u\) is popped, \(g(u) = d(s,u)\). Suppose not, and let \(P\) be a strictly cheaper true path \(s = v_0 \to v_1 \to \cdots \to v_k = u\). Walk along \(P\) until you find the first node \(v_i\) that is still unsettled. Its predecessor \(v_{i-1}\) is settled (or is \(s\) itself), so when \(v_{i-1}\) was settled its edges were relaxed, and therefore
\( g(v_i) \;\le\; d(s, v_i) \;\le\; d(s,u) \;<\; g(u). \)
But then the priority queue would have popped \(v_i\) before \(u\) — contradiction. So \(g(u)=d(s,u)\). This is why edge weights must be non-negative: the proof needs \(d(s,v_i) \le d(s,u)\), which requires that extending the path can only increase cost.
Cost. With a binary-heap priority queue, each of \(|V|\) extractions is \(O(\log V)\) and each of \(|E|\) relaxations may decrease a key in \(O(\log V)\), so total runtime is \(O((V+E)\log V)\). A Fibonacci heap brings this to \(O(E + V\log V)\).
Step 3 · the A* trick
Dijkstra is unbiased — it has no idea where the goal is, so it explores everywhere equally. But we know roughly where the goal is: even with walls in the way, the straight-line distance to the goal is a reasonable hint.
Where does the formula come from? Dijkstra sorts the frontier by \(g(n)\), the cheapest known cost to reach \(n\). What we'd really like to sort by is the cheapest cost of any full path through \(n\) to the goal — call that quantity \(f^*(n)\):
\[ f^*(n) \;=\; g^*(n) \;+\; h^*(n), \]
where \(g^*(n)\) is the true cheapest cost from the start to \(n\) and \(h^*(n)\) is the true cheapest cost from \(n\) onward to the goal. We can't compute \(f^*\) without already knowing the answer, so we approximate: use the best \(g\) we've found so far in place of \(g^*\), and a cheap estimate \(h(n)\) in place of \(h^*(n)\). That gives the A* priority
\[ f(n) \;=\; \underbrace{g(n)}_{\text{cost so far (known)}} \;+\; \underbrace{h(n)}_{\text{guess to goal}}. \]
For a grid that allows 8-directional moves, a natural \(h\) is the octile distance — the length of the unobstructed shortest path if every wall were removed:
\[ h(n) \;=\; \max(\Delta x, \Delta y) \;+\; (\sqrt{2}-1)\,\min(\Delta x, \Delta y), \]
with \(\Delta x = |n_x - g_x|\) and \(\Delta y = |n_y - g_y|\). It's the cheapest geometric way to combine \(\min(\Delta x,\Delta y)\) diagonal steps of cost \(\sqrt 2\) with the remaining axis-aligned steps of cost \(1\). When \(h \equiv 0\), the formula collapses to \(f = g\) and A* becomes Dijkstra exactly. So A* is Dijkstra with an extra term — nothing more.
Side by side, on the same map: Dijkstra explores nearly everything; A* explores a narrow corridor.
The cleanest way to see why A* still works is to reinterpret it. Treat \(h\) as a potential on the graph (think of it as a height assigned to each node) and define a new edge weight
\[ \tilde w(u,v) \;=\; w(u,v) \;-\; h(u) \;+\; h(v). \]
Then for any path \(s \to v\), the reweighted total telescopes:
\[ \sum \tilde w \;=\; \Big(\sum w\Big) \;-\; h(s) \;+\; h(v), \]
which differs from the original cost by a constant for fixed endpoints. So shortest paths in the reweighted graph are identical to shortest paths in the original. And:
\[ f(v) \;=\; g(v) + h(v) \;=\; \tilde g(v) + h(s), \]
where \(\tilde g\) is the reweighted-graph cost-so-far. Sorting the frontier by \(f\) is the same as sorting by \(\tilde g\) (up to the constant \(h(s)\)). So A* is literally Dijkstra running on a reweighted graph. The catch: Dijkstra's correctness proof needs \(\tilde w \ge 0\), i.e.
\[ h(u) \;\le\; w(u,v) + h(v) \quad \text{for every edge.} \]
That is exactly the consistency condition on \(h\). Consistency is just the triangle inequality on the estimate, and it is what makes the reduction to Dijkstra valid.
Step 4 · why the guess must be honest
A* only finds the truly shortest path if its hint \(h(n)\) never overestimates the real remaining distance. Such a hint is called admissible. Straight-line distance is admissible: no path can be shorter than a straight line.
Why does it matter? When A* pops a cell off its frontier, it's committing — saying "no other path I haven't yet explored could possibly be cheaper." That commitment is only safe if every un-explored cell's optimistic estimate \(g + h\) is still at least as large as the path I'm committing to. Inflate the estimates and you commit too early to a path that turns out worse.
Try it. The slider scales the heuristic by a weight \(w\). At \(w = 1\) the search is correct. As \(w\) grows, the search gets faster (fewer cells explored) but the path it finds gets longer — you've traded optimality for speed.
Admissibility. \( h(n) \le h^*(n) \) for every node \(n\), where \(h^*(n)\) is the true cheapest remaining cost from \(n\) to the goal. (Equivalent: \(h\) never overestimates.)
Claim. When A* pops the goal, the value \(g(\text{goal})\) it commits to equals the true optimum \(C^* = d(s, \text{goal})\).
Proof. Suppose A* is about to pop the goal with \(g(\text{goal}) > C^*\). Let \(P^*\) be a true optimal path \(s = v_0 \to \cdots \to v_k = \text{goal}\), and let \(v_i\) be the first node on \(P^*\) still on the open list. Since the prefix \(s\to v_i\) was relaxed via \(v_{i-1}\) (or \(v_i = s\)),
\( g(v_i) \;=\; g^*(v_i). \)
By admissibility \(h(v_i) \le h^*(v_i)\), so
\[ f(v_i) \;=\; g(v_i) + h(v_i) \;\le\; g^*(v_i) + h^*(v_i) \;=\; C^* \;<\; g(\text{goal}) \;=\; f(\text{goal}). \]
But the priority queue pops the smallest \(f\) first, so it would pop \(v_i\) (or another open node) before the goal — contradicting our assumption. Therefore \(g(\text{goal}) = C^*\). \(\square\)
Where the proof breaks with \(w>1\) (weighted A*). Inflating \(h\) by a factor \(w>1\) means \(f(v_i) \le g^*(v_i) + w\cdot h^*(v_i)\), which can now exceed \(C^*\). The inequality \(f(v_i) < f(\text{goal})\) no longer holds, so A* may commit to a suboptimal goal — though one can show the returned cost is at most \(w \cdot C^*\), bounding how bad the detour can be.
Consistency (a stronger property), \(h(u) \le w(u,v) + h(v)\), additionally guarantees no node is ever re-expanded — see the reweighting view in the previous step.
Step 5 · the production trick
A* is great on a city, but a real road graph has tens of millions of nodes — the entire street network of Europe is around 18 million intersections. Even a focused A* search would touch enormous numbers of them. Phones can't afford that.
The fix is to do most of the work before any query arrives. Cut the graph into regions (say, 256 of them — one per neighborhood, county, or land tile). Within each region, identify the few cells on its boundary — the only points where a path can cross into a neighboring region. Then pre-compute and store the shortest distance between every pair of boundary nodes, across the whole world.
Now a query from A to B in different regions becomes three small searches: from A to its region's boundary, a single lookup hop across regions through the precomputed shortcuts, and from B's region boundary back to B. The middle step — potentially crossing a continent — is just a table lookup.
Below, a small map split into four colored regions. Watch the unpartitioned A* search sprawl across all four. Then switch on partitioning: the search stays inside its own region, jumps to the target region through the precomputed shortcut edges (drawn as dashed lines), and finishes locally.
Dijkstra is a flood. It eventually finds the shortest path but doesn't know which direction to favor, so it inflates outward in every direction.
A* is the same flood, but each frontier cell gets pushed by a hint — the straight-line distance left. As long as the hint never lies in the optimistic direction (never overestimates), the flood still finds the optimal path, just by spreading toward the goal instead of away from it.
Graph partitioning moves the work off the critical path: rather than searching the whole continent at query time, you pre-compute the inter-region distances once and reduce a transcontinental search to "local search · table lookup · local search." That's the reason your phone routes you across Europe in 50 milliseconds — not because it searched the whole network, but because someone already did, years ago.
So when you tap "Directions," what runs underneath is exactly the kernel: water spreading from your location, pulled toward the destination, leaping across pre-built highways in the graph.