A* search

What this chapter covers

Dijkstra finds the shortest path, but it does so blind: with no idea where the goal is, it explores outward in every direction equally, settling nodes in a growing circle until the target happens to fall inside. When you actually know where you're going — a destination on a map, a goal tile in a game — that's wasteful. A* is Dijkstra given a sense of direction. It keeps an estimate of how far each node still is from the goal and uses that estimate to steer the search, so it heads toward the target instead of flooding away from it. With a well-chosen estimate it finds exactly the same shortest path Dijkstra would, while expanding a small fraction of the nodes — in this chapter's open-grid test, about a tenth. This chapter builds it, watches its frontier get pulled toward the goal on a maze, and pins down the one property the estimate must have for the shortest-path guarantee to survive.

A bit of history

A* was published in 1968 by Peter Hart, Nils Nilsson, and Bertram Raphael at the Stanford Research Institute, where it was invented to guide Shakey the robot — one of the first mobile robots that could reason about its own actions — as it planned routes through a cluttered room. Their paper did something important beyond giving an algorithm: it proved that A* is optimally efficient. Among all algorithms that use the same heuristic information and are guaranteed to find a shortest path, none can expand fewer nodes than A* does. That's a strong statement — it says the "distance-so-far plus estimate-to-go" idea isn't just a good heuristic, it's the best possible use of that heuristic. The name is literally "A star": their earlier algorithms were called A1, A2, and so on, and they proved this one optimal, so it earned the star. It has been the backbone of game AI and robot navigation ever since, and it sits directly atop Dijkstra — which the same community had had since 1959 — as "Dijkstra plus a heuristic."

The intuition

Dijkstra picks the next node to expand by $g(n)$ alone — the cheapest distance from the start so far. That's why it grows a uniform circle: it always expands the closest-to-start unsettled node, regardless of direction. A* adds a second term. For each node it also computes $h(n)$, a heuristic estimate of the remaining distance from $n$ to the goal, and orders its priority queue by the sum $f(n) = g(n) + h(n)$ — the estimated total length of a path through $n$. Now the node it expands next isn't the one closest to the start, but the one on the most promising path to the goal. On a grid, if the goal is to the east, a node that's made real progress east looks better than one the same distance from the start but to the north, because its $h$ is smaller. The search elongates toward the target.

The heuristic is problem-specific and it's where the intelligence lives. On a grid where you can only move in the four compass directions, the natural estimate is the Manhattan distance — the number of rows plus columns separating a node from the goal — because you can't possibly reach the goal in fewer than that many unit steps. That last clause is the crucial property: the estimate must never claim the goal is farther than it truly is. Under-estimating (or being exactly right) is fine; over-estimating is not, and the deep dive explains why. Set $h(n) = 0$ everywhere — the trivial "I have no idea how far the goal is" estimate — and $f(n) = g(n)$, and A* becomes Dijkstra exactly. The heuristic is the entire difference between the two algorithms, and a better heuristic means a narrower, faster search.

Complexity: how it scales

A*'s worst case is the same as Dijkstra's — with a useless heuristic it can expand every node, giving $O(E \log V)$ — so its Big-O doesn't capture what makes it fast. What matters is how many nodes it actually expands, which depends entirely on the heuristic's quality, and that's the face-off: A* and Dijkstra finding the identical shortest path across grids of growing size, counted by nodes expanded:

Both algorithms return the exact same optimal path — the correctness check confirms A*'s cost always equals Dijkstra's — but they do wildly different amounts of work to get it. On a 3600-cell grid, Dijkstra expanded about 3200 nodes (nearly the whole grid, its circle swelling until it engulfed the goal), while A* expanded around 290 — roughly eleven times fewer, because the Manhattan heuristic kept it marching toward the target instead of exploring behind and beside the start. The gap widens with grid size, which is exactly why A* dominates real pathfinding: the bigger the world, the more Dijkstra wastes on directions that lead away from where you're going, and the more a heuristic saves.

What it's good at, what it isn't

A* is the right tool for shortest paths to a known goal when you have a decent heuristic — which is most real pathfinding. Game characters navigating a map, robots planning motion, GPS routing (with heuristics like straight-line distance), puzzle solvers (the 15-puzzle and Rubik's cube, with heuristics counting misplaced tiles), and any "get from here to there efficiently" problem in a large state space. When the heuristic is good, A* explores a tiny fraction of what Dijkstra would, and it never sacrifices optimality to do so, as long as the heuristic is admissible.

Where A* offers nothing is when there's no single goal or no useful heuristic. If you need distances to all nodes, or you're exploring without a target, the heuristic is $0$ and A* is just Dijkstra with extra bookkeeping — use Dijkstra. If you can't estimate remaining distance (an abstract graph with no geometry), likewise. A* also assumes non-negative edge weights, inheriting that from Dijkstra. And a poor heuristic can make it barely faster than Dijkstra while costing more per node; a dishonest (overestimating) heuristic makes it faster still but silently returns non-optimal paths — sometimes an acceptable trade (weighted A* does exactly this on purpose), but a trap if you didn't mean to.

The data, or the inputs

The face-off runs on random grids of growing size with about 10% of cells blocked, and counts how many nodes A* (with the Manhattan heuristic) and Dijkstra (no heuristic) each expand to find the identical shortest path from corner to corner. The correctness check confirms on hundreds of random grids that A*'s path cost always equals Dijkstra's optimum and that the returned path is a real connected sequence of the right length. The animation runs A* on a fixed maze with two staggered walls, so you can watch the frontier bend around obstacles while still straining toward the goal in the far corner.

Build it, one function at a time

The search itself — a priority queue ordered by f = g + h, with the goal-hugging tie-break:

def astar(adj, start, goal, h):
    """Cheapest path from start to goal over non-negative weighted edges, guided by heuristic
    h[n] (an estimate of the remaining distance from n to goal). The priority queue is ordered
    by f = g + h, so nodes that look closer to the goal are explored first. With an admissible
    h (never an overestimate) the first time we pop `goal` we have its true shortest distance.
    Returns (path, cost, expanded) where `expanded` counts nodes settled — the work done."""
    g = {start: 0}
    parent = {start: None}
    # Priority is (f, -g): order by f = g + h, and among equal f prefer the LARGER g — i.e.
    # the node already closer to the goal. This admissible tie-break makes A* hug a straight
    # line to the target instead of fanning across a plateau of equal-f nodes on open grids.
    pq = [(h[start], 0, start)]              # (f, -g, node)
    settled = set()
    expanded = 0
    while pq:
        f, neg_g, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        expanded += 1
        gu = -neg_g
        if u == goal:                        # popped the goal → its distance is final
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1], gu, expanded
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):  # a cheaper way to v → relax and re-prioritize
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h[v], -ng, v))
    return None, float("inf"), expanded

Turning a grid with walls into a graph, and the admissible Manhattan heuristic for it:

def grid_graph(rows, cols, walls):
    """Turn a grid with blocked cells into a weighted adjacency list (4-connected, unit
    edges). Cells are numbered r*cols + c; `walls` is a set of (r, c) that can't be entered."""
    def nid(r, c):
        return r * cols + c

    adj = {}
    for r in range(rows):
        for c in range(cols):
            if (r, c) in walls:
                continue
            nbrs = []
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in walls:
                    nbrs.append((nid(nr, nc), 1))
            adj[nid(r, c)] = nbrs
    return adj


def manhattan(rows, cols, goal):
    """The admissible, consistent heuristic for a 4-connected unit grid: the straight-line
    grid distance (|Δrow| + |Δcol|) to the goal. It never overestimates, because you can't
    reach the goal in fewer than that many unit steps."""
    gr, gc = divmod(goal, cols)
    return {r * cols + c: abs(r - gr) + abs(c - gc) for r in range(rows) for c in range(cols)}

Watch it work

Here's A* solving a maze from the top-left (purple) to the bottom-right (red), with two staggered walls it has to route around. Blue cells are the open set — discovered, waiting in the priority queue; grey cells are closed — already expanded; orange is the node being expanded this step. Watch the shape of the exploration: it doesn't spread evenly like Dijkstra's circle would — it reaches toward the goal in the far corner, bulging outward only where a wall forces it to detour, then snapping back onto a beeline. When it finally pops the goal, the green cells trace the shortest path. Dijkstra would have filled far more of this grid grey before finding the same route; A*'s heuristic is what keeps the grey confined to a corridor:

The complete code

The from-scratch tab is A* with the grid helpers and the Manhattan heuristic; the library tab is Dijkstra — A* with the heuristic switched off — which is both the contrast that makes A* legible and the reference its optimum is checked against. The networkx call you'd use in production is noted at the top. Flip between them.

"""A* search — Dijkstra with a sense of direction. Dijkstra explores outward in every
direction equally, because it has no idea where the goal is; it will happily expand
thousands of nodes away from the target before stumbling onto it. But when you DO know
where you're going — a point on a map, a goal tile in a game — you can estimate how far
each node still is from the goal and let that estimate pull the search toward it.

A* orders its priority queue not by distance-so-far g(n) alone (that's Dijkstra) but by
f(n) = g(n) + h(n), where h(n) is a heuristic guess of the remaining distance to the goal.
If h never overestimates the true remaining distance — an "admissible" heuristic — A* is
guaranteed to find the shortest path, exactly like Dijkstra, but it expands far fewer nodes
because it stops wandering away from the target. Set h(n) = 0 and A* IS Dijkstra: the
heuristic is the only difference, and it's the difference between a flood and an arrow.
"""
import heapq


# region: astar
def astar(adj, start, goal, h):
    """Cheapest path from start to goal over non-negative weighted edges, guided by heuristic
    h[n] (an estimate of the remaining distance from n to goal). The priority queue is ordered
    by f = g + h, so nodes that look closer to the goal are explored first. With an admissible
    h (never an overestimate) the first time we pop `goal` we have its true shortest distance.
    Returns (path, cost, expanded) where `expanded` counts nodes settled — the work done."""
    g = {start: 0}
    parent = {start: None}
    # Priority is (f, -g): order by f = g + h, and among equal f prefer the LARGER g — i.e.
    # the node already closer to the goal. This admissible tie-break makes A* hug a straight
    # line to the target instead of fanning across a plateau of equal-f nodes on open grids.
    pq = [(h[start], 0, start)]              # (f, -g, node)
    settled = set()
    expanded = 0
    while pq:
        f, neg_g, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        expanded += 1
        gu = -neg_g
        if u == goal:                        # popped the goal → its distance is final
            path = []
            while u is not None:
                path.append(u)
                u = parent[u]
            return path[::-1], gu, expanded
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):  # a cheaper way to v → relax and re-prioritize
                g[v] = ng
                parent[v] = u
                heapq.heappush(pq, (ng + h[v], -ng, v))
    return None, float("inf"), expanded
# endregion


# region: grid
def grid_graph(rows, cols, walls):
    """Turn a grid with blocked cells into a weighted adjacency list (4-connected, unit
    edges). Cells are numbered r*cols + c; `walls` is a set of (r, c) that can't be entered."""
    def nid(r, c):
        return r * cols + c

    adj = {}
    for r in range(rows):
        for c in range(cols):
            if (r, c) in walls:
                continue
            nbrs = []
            for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and (nr, nc) not in walls:
                    nbrs.append((nid(nr, nc), 1))
            adj[nid(r, c)] = nbrs
    return adj


def manhattan(rows, cols, goal):
    """The admissible, consistent heuristic for a 4-connected unit grid: the straight-line
    grid distance (|Δrow| + |Δcol|) to the goal. It never overestimates, because you can't
    reach the goal in fewer than that many unit steps."""
    gr, gc = divmod(goal, cols)
    return {r * cols + c: abs(r - gr) + abs(c - gc) for r in range(rows) for c in range(cols)}
# endregion

"""The library counterpart and the built-in contrast. In production A* comes from networkx
(`nx.astar_path`, which takes a heuristic callback) or from a game/robotics pathfinding
library:

    import networkx as nx
    nx.astar_path(G, source, target, heuristic=lambda a, b: manhattan(a, b), weight="weight")

The contrast that makes A* legible is DIJKSTRA — which is literally A* with the heuristic
switched off (h ≡ 0). `dijkstra` below is exactly the A* in impl.py with a zero heuristic;
the trace generator runs both to the same goal on the same grid and counts how many nodes
each expands, so the only variable is the heuristic. It's also the trusted reference: with
an admissible heuristic A* must return the same optimal cost as Dijkstra.
"""
import heapq


# region: dijkstra
def dijkstra(adj, start, goal):
    """A* with h ≡ 0: no goal direction, so it expands outward uniformly. Same code shape as
    impl.astar, minus the heuristic — which is the whole point. Returns (cost, expanded)."""
    g = {start: 0}
    pq = [(0, start)]
    settled = set()
    expanded = 0
    while pq:
        gu, u = heapq.heappop(pq)
        if u in settled:
            continue
        settled.add(u)
        expanded += 1
        if u == goal:
            return gu, expanded
        for v, w in adj[u]:
            ng = gu + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(pq, (ng, v))
    return float("inf"), expanded
# endregion

Scratch vs library

The comparison that teaches here is A* against Dijkstra, and the punchline is that they're the same algorithm — A* with $h = 0$ is Dijkstra, line for line. Everything separating "explores 3200 nodes" from "explores 290 nodes" lives in a single extra term, the heuristic, which encodes knowledge the plain algorithm doesn't have: where the goal is. That's a broader lesson about algorithm design than pathfinding alone. Often the way to beat a general algorithm isn't a cleverer data structure but injecting domain knowledge the general version can't use — here, geometry. Dijkstra is optimal among algorithms that know nothing about the goal; A* is optimal among algorithms that know the heuristic; and the heuristic is you telling the search something true about your specific problem. In production you'd call networkx.astar_path with a heuristic callback, or use a game engine's pathfinder; building it yourself is what makes "the heuristic is the whole difference" a fact you've watched rather than a slogan.

Where you'll actually meet it

A* is the default pathfinding algorithm of the games industry — nearly every strategy game, RPG, and RTS moves its units with A* over a navigation grid or mesh, which is why it's one of the most-run algorithms on consumer hardware. Robotics uses it for motion planning, often with continuous-space variants (hybrid A*, D*). Mapping and routing engines use it (and its heavily optimized descendants like contraction hierarchies) with straight-line-distance heuristics. Puzzle solvers — the 15-puzzle, Rubik's cube, Sokoban — use A* with pattern-database heuristics. Network and logistics planners use it wherever a goal and a distance estimate exist. Anywhere the task is "find the best route to a specific place, fast," A* is the algorithm, and its heuristic is the knob that makes it fast.

Takeaways

A* finds shortest paths to a known goal by expanding nodes in order of $f = g + h$ — cost-so-far plus a heuristic estimate of cost-to-go — which steers the search toward the target and, with a good heuristic, expands a small fraction of the nodes Dijkstra would (about a tenth on this chapter's open grid) while returning the identical optimal path. The guarantee holds precisely when the heuristic is admissible, never overestimating the true remaining distance; set the heuristic to zero and A* is exactly Dijkstra. The algorithm is the same priority-queue search as Dijkstra — all the leverage is in the heuristic, which is domain knowledge the blind version can't use.

That completes the shortest-path family. The last three chapters of the graph tier turn to a different question — not paths but structure: connecting all the nodes as cheaply as possible (minimum spanning trees, next, via Prim and then Kruskal), and decomposing a directed graph into its strongly connected components. Prim's algorithm, fittingly, is this very same priority-queue traversal with one word changed in what it puts on the heap.