Dijkstra’s algorithm finds the shortest path but explores nodes in every direction equally, which is expensive on a road network with millions of nodes. A* uses a heuristic to bias the search toward the destination, dramatically reducing the number of nodes evaluated. For real-time routing on a continental road network, that difference is the gap between a response in milliseconds and one in seconds.
Analysis Briefing
- Topic: A* vs Dijkstra for real-time navigation and graph search
- Analyst: Mike D (@MrComputerScience)
- Context: Sparked by a question from Claude Sonnet 4.6
- Source: Pithy Cyborg | AI News Made Simple
- Key Question: What does A* know that Dijkstra doesn’t, and why does it matter at Google Maps scale?
How Dijkstra Works and Where It Breaks Down at Scale
Dijkstra’s algorithm maintains a priority queue of unvisited nodes sorted by their tentative distance from the source. At each step it extracts the minimum-distance node, relaxes its neighbors, and continues until it reaches the destination. It is guaranteed to find the shortest path in graphs with non-negative edge weights.
The problem is search radius. Dijkstra expands outward in a circle from the source. To route from San Francisco to Los Angeles, it evaluates every node within roughly the same radius as the destination, which includes enormous swaths of the road network that are geometrically irrelevant to the path. On a graph with 50 million nodes, a cross-country query can evaluate millions of nodes before reaching the destination.
This is not a theoretical concern. Early mapping applications using pure Dijkstra on continental road networks took seconds to route. That latency is unacceptable for a product used while driving.
How A* Uses a Heuristic to Focus the Search
A* augments Dijkstra with a heuristic function h(n) that estimates the cost from any node n to the destination. The priority queue sorts nodes by f(n) = g(n) + h(n), where g(n) is the known cost from the source to n and h(n) is the estimated remaining cost.
The heuristic steers the search. Nodes in the direction of the destination get lower f(n) values and are explored first. Nodes in the opposite direction have high h(n) values and are deprioritized or never evaluated.
For road networks, the straight-line (Euclidean) distance is a common admissible heuristic. It never overestimates the true remaining distance because roads cannot be shorter than straight lines. An admissible heuristic guarantees that A* still finds the optimal path.
import heapq
import math
from collections import defaultdict
def heuristic(node: tuple, goal: tuple) -> float:
# Euclidean distance as admissible heuristic
return math.sqrt((node[0] - goal[0])**2 + (node[1] - goal[1])**2)
def astar(graph: dict, start: tuple, goal: tuple) -> list:
"""
graph: {node: [(neighbor, weight), ...]}
nodes are (lat, lon) tuples for the heuristic to work
"""
open_set = [(0, start)]
came_from = {}
g_score = defaultdict(lambda: float('inf'))
g_score[start] = 0
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
path = []
while current in came_from:
path.append(current)
current = came_from[current]
path.append(start)
return list(reversed(path))
for neighbor, weight in graph.get(current, []):
tentative_g = g_score[current] + weight
if tentative_g < g_score[neighbor]:
came_from[neighbor] = current
g_score[neighbor] = tentative_g
f_score = tentative_g + heuristic(neighbor, goal)
heapq.heappush(open_set, (f_score, neighbor))
return [] # No path found
The efficiency gain depends on heuristic quality. A perfect heuristic (knowing the exact remaining distance) would expand only nodes on the optimal path. The Euclidean heuristic is imperfect because roads are not straight lines, but it reduces node expansions by an order of magnitude on typical road network queries.
What Google Maps Actually Uses Beyond Basic A*
Pure A* on a 50-million-node road network is fast enough for city-scale routing but still too slow for cross-country queries at the latency required for a consumer product. Google Maps and similar systems use preprocessing-based algorithms that make A* look slow by comparison.
Contraction Hierarchies (CH) preprocess the graph by adding shortcut edges. Less important nodes are contracted and replaced with shortcuts that preserve shortest path distances. Queries then run a bidirectional Dijkstra on the contracted graph, evaluating only the highway network for long-distance routes and expanding to local roads near the source and destination. CH reduces query time from tens of milliseconds to under a millisecond on continental road networks.
Hub Labeling precomputes, for each node, a set of important intermediate nodes (hubs) that appear on optimal paths. Queries reduce to a table lookup. This achieves sub-microsecond routing but requires gigabytes of preprocessing data.
A* remains the right algorithm to understand because it underlies game AI pathfinding, robotics motion planning, and any graph search where a meaningful distance heuristic exists. The AI agent infinite loop failures that plague modern LLM systems often trace back to the same graph search principles: without a good heuristic or termination condition, search expands indefinitely.
What This Means For You
- Use A over Dijkstra whenever you have a meaningful distance heuristic,* because the heuristic is free information that can reduce evaluated nodes by 10x or more on spatial graphs.
- Ensure your heuristic is admissible (never overestimates the true cost) or A* will not guarantee an optimal path, and the resulting routes or game paths will be subtly wrong in ways that are hard to debug.
- Apply bidirectional search for long-distance queries on large graphs, because searching simultaneously from source and destination and meeting in the middle halves the effective search radius even without a heuristic.
- Use Contraction Hierarchies for production road network routing rather than raw A*, because the preprocessing investment pays back on the first query and CH handles continental-scale graphs with sub-millisecond response times.
Enjoyed this deep dive? Join my inner circle:
- Pithy Cyborg | AI News Made Simple → AI news made simple without hype.