Cheapest, not shortest
BFS found Arad → Sibiu → Fagaras → Bucharest: three roads, 450 km. But Arad → Sibiu → Rimnicu Vilcea → Pitesti → Bucharest is 418 km. To find the cheapest route, search must track cost so far. To find it quickly, search should also guess how far is left — and head in the right direction instead of fanning out everywhere.
That's A* search, published by Hart, Nilsson and Raphael in 1968 for the Shakey robot at SRI. More than fifty years later it's still the workhorse of game path-finding and route planning.
g, h and f
For each node on the frontier, A* knows g — the cost of the path so far — and asks a heuristic function for h — an estimate of the cost from here to the goal. It always expands the node with the smallest f = g + h: the best guess at the total cost of a solution through that node. With h = 0 everywhere, A* becomes uniform-cost search (Dijkstra's algorithm), which is optimal but explores in every direction.
const SLD = {
Arad: 366, Sibiu: 253, Fagaras: 176,
RimnicuVilcea: 193, Pitesti: 100, Bucharest: 0,
// …
};
aStar(routeProblem("Arad", "Bucharest"), (c) => SLD[c]);On this map A* with straight-line distance expands 5 cities before reaching Bucharest; uniform-cost search expands 12. Same answer, less than half the work.