Heuristics & Pathfinding: From Dijkstra to A*

Your GPS finds the fastest route through millions of intersections in milliseconds. It doesn't check every possible route — for just 20 stops, there are 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 dead ends.

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.

Consider a city graph with 6 intersections (A through F), where each connection has a travel time in 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.

Dijkstra's algorithm solves this problem. It was designed in 1956 by Edsger W. Dijkstra at a café in Amsterdam — in just 20 minutes, at the age of 26 — and published in 1959.

Dijkstra always expands the cheapest unvisited node so far. It tracks cumulative costs (g-values) from the start node and guarantees the optimal path once the goal node is reached.

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.

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?

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.

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⁸⁰)?

AlphaGo defeated world champion Lee Sedol 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: Alpha-Beta Pruning in game trees (next article), 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.