Pathfinding

Every algorithm in this chapter answers one question: what is the best route from a start to a goal through a graph? On the grid, a node is a cell and its neighbours are the cells above/below/left/right (optionally diagonals). On real streets, a node is an intersection and its neighbours are the roads leading out of it. The algorithms don’t care which — they only ever ask four things:

• successors(node) — the neighbouring nodes and the cost to step to each,
• heuristic(node) — an estimate of the remaining distance to the goal,
• start and goal.

Because that interface is all they use, the same nine algorithms run unchanged on a hand-drawn maze and on a city’s road network. What differs is only how much of the graph each one explores before it finds the goal — and that gap is the whole lesson.

The shared skeleton

Every search keeps a frontier (nodes discovered but not yet expanded) and a set of visited nodes. It repeatedly pulls a node off the frontier, checks if it’s the goal, and otherwise pushes its successors. The only thing that separates the algorithms is the order in which the frontier hands nodes back:

frontier ← { start }
while frontier not empty:
    node ← frontier.pop()          # ← the choice of which node defines the algorithm
    if node is goal: return reconstruct_path(node)
    for (nbr, step_cost) in successors(node):
        if nbr not seen (or found cheaper):
            record came_from[nbr] = node
            frontier.push(nbr)

BFS makes frontier a FIFO queue; DFS a stack; Dijkstra and A* a priority queue ordered by a cost. Swap the container, get a different algorithm.

Uninformed search — no idea where the goal is

Breadth-First Search (BFS) expands the frontier in rings of equal step count. Because it reaches every node at distance $k$ before any node at distance $k+1$, the first time it touches the goal it has found the path with the fewest steps. That makes BFS optimal when every move costs the same — but it fans out in all directions, so on a big open grid it visits a huge number of cells.

Depth-First Search (DFS) swaps the queue for a stack: it plunges down one path as far as it can before backtracking. It often reaches a goal quickly and uses very little memory, but the path it returns can be wildly long — DFS optimises for nothing but “keep going.” It’s the cautionary tale of the group.

Uniform-cost search — when steps cost differently

Add Mud to the maze and a step is no longer free — crossing a mud cell costs 5. BFS breaks here, because “fewest steps” ≠ “cheapest”. Dijkstra’s algorithm fixes it by ordering the frontier by $g(n)$, the cheapest known cost to reach $n$ from the start, and always expanding the cheapest node next. It’s guaranteed to find the minimum-cost path, and BFS is just the special case where every step costs 1.

g[start] = 0
frontier = priority queue ordered by g
while frontier:
    node = frontier.pop_min()      # cheapest-so-far
    if node == goal: return path
    for (nbr, cost) in successors(node):
        if g[node] + cost < g[nbr]:
            g[nbr] = g[node] + cost
            frontier.push(nbr, priority = g[nbr])

Informed search — using a heuristic

Dijkstra is optimal but blind: it explores outward evenly, spending effort on directions that lead away from the goal. A heuristic $h(n)$ — a cheap guess of the remaining distance — lets us aim. On a grid, straight-line (or Manhattan) distance to the goal; on streets, the great-circle haversine distance.

Greedy best-first orders the frontier by $h(n)$ alone — always step toward whatever looks closest. It’s fast and often finds a path with few expansions, but it’s fooled by dead ends and walls, so the path can be far from optimal.

A* is the classic. It orders the frontier by

— cost already paid plus estimated cost remaining. It only commits to a node once its total estimated route is the best on the table, so it drives toward the goal without giving up the optimality guarantee. The catch is a condition on the heuristic:

• Admissible — $h$ never overestimates the true remaining cost. Straight-line distance is admissible because the real road can only be longer. An admissible $h$ makes A* return an optimal path.
• Consistent — $h$ never drops by more than the step cost between neighbours. Consistency is slightly stronger and lets A* skip re-expanding nodes.

Set $h = 0$ and A* is Dijkstra. Make $h$ a perfect oracle and A* walks straight to the goal. Real heuristics sit between, and the better the estimate, the fewer cells A* touches — which is exactly what you watch race on the grid.

Weighted A* inflates the heuristic: $f = g + w \cdot h$ with $w > 1$ (the playground uses 1.5). It reaches the goal faster with far fewer expansions, but the path can be up to $w\times$ longer than optimal — a deliberate trade of quality for speed.

Meet in the middle — bidirectional search

A search that fans out from the start touches roughly $b^d$ nodes (branching factor $b$, depth $d$). Run two searches — one forward from the start, one backward from the goal — and each only has to reach the halfway point, so together they touch about $2\,b^{d/2}$ nodes: dramatically fewer. When the two frontiers collide, you stitch the halves. The playground includes bidirectional BFS, Dijkstra and A*; the first two stay optimal, and Bi-A* is near-optimal with careful stopping.

Side by side

The same algorithms on real streets

Lesson 2 of the playground swaps the grid for a live road graph pulled from OpenStreetMap. Intersections become nodes; road segments become weighted edges whose cost is their length in metres. The heuristic becomes the haversine (great-circle) distance to the destination — admissible, because no road is shorter than the straight line over the Earth’s surface. Nothing else changes: the identical A* that solved your maze now plans a route across a city, and the A*-vs-Dijkstra expansion gap you saw on the grid reappears on real roads. That’s the point of the shared interface — the lesson transfers.

Why A* is optimal — the proof worth carrying

The optimality claim deserves more than assertion, because its two-line proof is a template you will reuse across this track. Suppose A* (with admissible $h$) pops the goal off the frontier via a suboptimal path of cost $C > C^\*$. Then some node $n$ on an optimal path is still sitting in the frontier, with $f(n) = g(n) + h(n) \le g(n) + h^\*(n) = C^\*$ — admissibility never lets $f$ exceed the true optimal cost through $n$. But the goal was popped first, so $C \le f(n) \le C^\*$: contradiction. Admissibility makes the frontier’s $f$-values a certificate: nothing provably-cheaper is ever abandoned. The same never-overestimate logic returns as optimistic initialization in the exploration lessons ahead — and its failure mode returns too: an inadmissible heuristic is exactly a value estimate that overpromises, and both break their guarantees the same way.

The cost accounting completes the picture. With a consistent $h$, A* expands every node with $f(n) < C^\*$ — no algorithm using the same heuristic information can provably do less. So “A* is efficient” really means: its waste is exactly the heuristic’s ignorance, $h^\* - h$. Better heuristics are the only lever, which is why the weighted variant (deliberately inflating $h$ past admissibility) is an informed choice to accept bounded suboptimality, not a hack.

import heapq

def astar(successors, h, start, goal):
    """The 20 lines every mapping app is built on."""
    g = {start: 0.0}
    came = {}
    frontier = [(h(start), start)]           # (f, node)
    while frontier:
        f, node = heapq.heappop(frontier)
        if node == goal:
            path = [node]
            while node in came:
                node = came[node]
                path.append(node)
            return path[::-1], g[goal]
        for nbr, cost in successors(node):
            ng = g[node] + cost
            if ng < g.get(nbr, float("inf")):
                g[nbr], came[nbr] = ng, node
                heapq.heappush(frontier, (ng + h(nbr), nbr))
    return None, float("inf")

# grid world: successors = 4-neighbours, h = Manhattan distance
# streets:     successors = road segments, h = haversine — same function, unchanged

Exercises