function route(map: RoadMap, start: Node, goal: Node) {const open = new MinHeap([start]), distance = new Map([[start, 0]]), parent = new Map();
while (open.size > 0) {// lowest distance so far + straight line to the goal
const current = open.pop();
if (current === goal) return rebuild(parent, goal);
for (const street of map.streetsFrom(current)) {const next = street.otherEnd(current);
const candidate = distance.get(current)! + street.metres;
if (candidate >= (distance.get(next) ?? Infinity)) continue;
distance.set(next, candidate); parent.set(next, current);
open.push(next, candidate + straightLine(next, goal));
}
}
}
Loading the street map…
Understanding A* on the real map
The idea
A* ranks every open intersection by the distance driven to reach it plus the straight-line distance still to go. Because no street can be shorter than the straight line, that estimate never overshoots, and the first time the goal comes out of the open set its route is the shortest there is.
On a real street map the effect is visible at once: the search grows as a lobe pointed at the goal instead of a disc, and it closes a few hundred intersections where Dijkstra closes thousands. The route it returns is the same one Dijkstra finds.
The four stages
Complexity
Versus its siblings
Pseudocode
ROUTE(map, start, goal)
open ← {start}; distance[start] ← 0while open not empty
current ← the open intersection with the lowest distance + straightLine(current, goal)
if current = goal: return the route via parent
for each street leaving current, to neighbour
if distance[current] + street.metres < distance[neighbour]: update it, parent[neighbour] ← current, add neighbour to open
When to use
Pitfalls
History
The map is the centre of Cascavel, Paraná: 4 180 intersections and 5 438 street segments from OpenStreetMap, one-way streets respected, about 10 by 7 km. Every real routing engine runs this same loop on a graph a million times larger, with contraction hierarchies or landmarks precomputed so that a query touches only a sliver of it.