Heuristics & Pathfinding: From Dijkstra to A*
How A* works — and why Dijkstra gets boring without a heuristic.
Your GPS finds the fastest route through millions of intersections in milliseconds. It doesn't check every possible route — even a delivery run with just 21 stops would have more possible orderings than seconds since the Big Bang. Instead, it uses a mathematical shortcut: a heuristic — an informed estimate that steers the search toward the goal without exploring every dead end.
This article traces the idea from Dijkstra's blind-but-optimal algorithm (1959) to A*'s informed search (1968) to AlphaGo's neural network heuristics (2016) — a single concept that connects classical computer science to modern AI.
The Cost Problem: Why BFS Fails on Weighted Graphs
In the previous article, you learned about BFS and DFS — algorithms that systematically explore graphs. BFS finds the shortest path measured by edge count. But real roads have different lengths, different speed limits, and different traffic volumes. BFS counts edges, not costs.
Definition
Cost Function
Analogy
Definition
Consider a city graph with 6 intersections (A through F), where each connection has a travel time in minutes. The connections: A→B 5, B→C 8, C→F 7, B→E 12, E→F 10, A→D 25 and D→F 20 minutes.
BFS picks A→D→F (2 edges, 45 minutes) because it has the fewest edges.
Dijkstra picks A→B→C→F (3 edges, 20 minutes) because it tracks cumulative cost. More edges, but significantly less total time.
Same graph, drastically different result. Edge counting fails as soon as edges have different weights.
10 Cities (TSP)
181,440 routes
Still feasible for a computer
20 Cities (TSP)
6 ×10¹⁶ routes
Centuries of computation time if you try them all
25 Cities (TSP)
3.1 ×10²³ routes
Hundreds of millions of years of computation if you try them all
Dijkstra's algorithm solves this problem. It was designed in 1956 by Edsger W. Dijkstra at a café in Amsterdam — in just 20 minutes, in his mid-twenties — and published in 1959.
Dijkstra always expands the cheapest unvisited node so far. It tracks cumulative costs (g-values) from the start node and, with non-negative edge weights, guarantees the optimal path once the goal node is selected as the cheapest node.
But Dijkstra has a crucial limitation: it searches blindly in all directions. Like a water wave spreading from a dropped stone, it floods the graph uniformly — without knowing where the goal is.
Caution
Misconception: BFS Finds the Shortest Path
BFS finds the shortest path only in unweighted graphs, where every edge counts equally. In weighted graphs, fewer edges does not mean lower cost. Dijkstra corrects this by tracking cumulative cost instead of edge count.
Heuristics & A*: Searching with Direction
Dijkstra finds the optimal path, but it wastes enormous effort searching in all directions. What if the algorithm knew where the goal was — and preferentially searched toward it?
Definition
Heuristic
Analogy
Definition
Definition
Admissibility
Analogy
Definition
A* evaluates each node with f(n) = g(n) + h(n): g(n) is the actual cost from start to n, h(n) is the estimated remaining cost from n to the goal. A* always expands the node with the lowest f(n) value.
Where the compass analogy breaks: a real compass always points in a fixed direction. A*'s heuristic value changes at every node. Also, the compass only represents h(n) — the analogy must be considered alongside the formula f(n) = g(n) + h(n) to close this gap.
Note
A* Step by Step
- 1. We start at intersection A and look at the neighbors. Intersection B is 5 minutes away (g=5). The straight-line distance estimates 14 minutes remaining to the goal (h=14), so f=19. Intersection D costs 25 minutes (g=25), straight-line 15 (h=15), so f=40.
- 2. B has the lowest f-value (19), so we go there. From B we can reach C: 5+8=13 minutes so far (g=13), straight-line to the goal only 6 (h=6), so f=19. We also reach E: 5+12=17 minutes (g=17), straight-line 8 (h=8), so f=25.
- 3. C now has the best f-value (19), so we continue. From C we reach F — the goal! Cost: 13+7=20 minutes. Since we are at the goal, h=0.
- 4. Done: Path A→B→C→F, 20 minutes. A* checked only 3 intersections — Dijkstra would have checked 4 because it would also have checked intersection E (17 minutes) before the goal (20 minutes).
Expands 4 nodes, searches in all directions. Finds the optimal path A→B→C→F (20 min) — but with unnecessary effort.
Expands 3 nodes, guided toward the goal by the heuristic. Finds the identical optimal path A→B→C→F (20 min) — with less work.
Note
Historical Context: A*
A* was developed in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute, as part of the Shakey robot project — one of the first autonomous mobile robots. Published in IEEE Transactions on Systems Science and Cybernetics, A* proved for the first time that heuristic search can guarantee optimal results.
Shakey: The First Intelligent Mobile Robot
The birth of autonomous robotics through the integration of reasoning, planning, and physical action. From 1966 to 1972, Charles Rosen's team at SRI International developed Shakey — the first mobile robot capable of reflecting on its own actions. The 2-meter-tall robot combined a TV camera, sonar rangefinder, processors, and 'cat whiskers' as bump detectors into an autonomous system. Shakey's remarkable capabilities included environmental perception, drawing inferences from implicit facts, plan creation, and error compensation — all controllable via natural English. The ARPA (now DARPA)-funded project was the first to unite logical reasoning with physical action, laying the groundwork for autonomous systems. Shakey's innovations led to the A* search algorithm, visibility graph methods, and the influential computational variant of the Hough transform (Duda & Hart, SRI 1972). In 1970, Life Magazine called Shakey 'the first electronic person.'
Caution
Misconception: A* Finds an Approximate Path
A* doesn't just find an approximation — with an admissible heuristic, A* finds the exact same optimal path as Dijkstra. The difference lies solely in efficiency: A* visits fewer nodes to reach the same result.
Caution
Misconception: Any Heuristic Speeds Up A*
A bad heuristic can even make A* slower than Dijkstra — for example if it is expensive to compute or not consistent (see the Deep Dive below). Heuristic quality is crucial. Setting h(n) = 0 for all nodes reduces A* exactly to Dijkstra — the heuristic provides no directional information at all.
Admissibility (h(n) ≤ h*(n)) is sufficient for tree-search A* to guarantee the optimal path. Graph-search A* — where visited nodes are not re-expanded — requires a stronger condition: consistency (also called monotonicity).
A heuristic is consistent if: h(n) ≤ c(n, n') + h(n') for every node n and successor n', where c(n, n') is the edge cost from n to n'. Intuitively: the estimated cost decrease between two nodes must not be greater than the actual cost of the connecting edge.
Consistency implies admissibility, but not vice versa. In practice, most natural heuristics (like straight-line distance) are consistent. This distinction becomes relevant when implementing A* with a closed list.
Interactive: A* on the Grid
You have learned how A* finds the optimal path using f(n) = g(n) + h(n). Now you can trace the algorithm step by step on a 5×5 grid: observe how A* uses Manhattan distance to steer toward the goal and navigate around obstacles.
The Heuristic Idea in Modern AI
A* works brilliantly on road maps with thousands of nodes. But what about Go, which has approximately 2.08 × 10¹⁷⁰ legal positions — more than atoms in the observable universe (approx. 10⁸⁰)?
Note
The Heuristic Spectrum
From handcrafted to learned: A* with straight-line distance (exact guarantee, thousands of nodes) → Google Maps (handcrafted plus real-time data, billions of edges, near-optimal) → AlphaGo (learned neural network, 10¹⁷⁰ positions, superhuman but no guarantee) → LLMs (probability distributions, no guarantee, hallucinations possible). As search spaces grow, heuristics shift from handcrafted to learned.
AlphaGo defeated Lee Sedol, winner of 18 world titles, 4-1 in 2016. It uses two neural networks as heuristics: a policy network (which move next?) and a value network (how good is this position?). These are learned heuristics — trained on millions of games rather than designed by humans.
A* is a navigator with a perfect map — guaranteed shortest route, precise distances. AlphaGo is an experienced taxi driver who has known the city for 30 years — no map, but an uncanny sense for the right streets.
The taxi driver analogy understates the failure modes of learned heuristics: a taxi driver who takes a wrong turn notices immediately and corrects. A neural network playing Go can completely misjudge a position and drift into nonsensical move sequences — without noticing. Learned heuristics can fail in ways that handcrafted ones cannot.
The heuristic idea appears everywhere in AI: heuristic evaluation functions in game trees (article on MinMax & Pruning), loss functions as heuristics for model quality, gradient descent as heuristic-guided search through parameter space. Every AI system that searches a space too large for brute force uses some form of heuristic.
P is the class of problems that can be solved efficiently (in polynomial time). NP is the class of problems whose solutions can be verified efficiently. The unproven conjecture P ≠ NP — one of the Clay Millennium Problems (prize: $1 million, announced May 24, 2000) — states that some problems are efficiently verifiable but not efficiently solvable.
TSP is NP-hard: no known algorithm efficiently finds the optimal solution for all instances. If P ≠ NP holds, such an algorithm fundamentally cannot exist — heuristics are then not merely practically useful but fundamentally necessary.
This motivates the entire heuristic paradigm: when exact solutions are practically unreachable, good approximations become the best achievable outcome.
NP-hard does NOT mean unsolvable. It means: no known efficient exact algorithm. Small instances are often exactly solvable, and good heuristics find excellent approximations for large instances.
Note
Takeaways
- Blind search (BFS/DFS) ignores costs and explodes combinatorially. Cost functions make graphs realistic; Dijkstra finds the cheapest path — but searches in all directions.
- A heuristic is an informed estimate, not a guess. A* combines exact past cost g(n) with estimated remaining cost h(n). If the estimate never overestimates (admissible), A* is guaranteed to find the optimal path — and with a good heuristic it needs far less work than Dijkstra.
- The heuristic idea scales from exact guarantees (A* on road maps) to learned approximations (AlphaGo, neural networks). As search spaces grow, handcrafted heuristics give way to learned ones — trading guarantees for practical effectiveness.
Check
Quiz: Heuristics & Pathfinding
What does the heuristic h(n) in A* represent?
Select one answer
1. What does the heuristic h(n) in A* represent?
2. After starting at A, A* considers the possible next steps: B (g=5, f=19) and D (g=25, f=40). Which node does A* choose next and why?
3. Two paths from S to G: S→A→G (cost 10) and S→B→G (cost 8). The heuristic gives h(A)=3 and h(B)=12. Is this heuristic admissible?
4. A developer uses A* with a heuristic that always overestimates remaining costs by 50%. What happens compared to Dijkstra?
Check
Comprehension Check
Can you explain this in your own words? Tick what you've got.
0 of 3 done