Pathfinding Algorithms

How A* Search Works

A* finds the shortest route by expanding whichever intersection has the lowest distance travelled plus an estimate of the distance left. Watch it cut across a city while Dijkstra floods every street around the start.

Complexity

BestAverageWorstExtra memory
O(d)O((V + E) log V)O((V + E) log V)O(V)

d is the number of intersections on the route. The best case needs a perfect heuristic; with h = 0 A* is exactly Dijkstra, which is its worst case.

How a* search works

A* is Dijkstra's algorithm with one change to the priority: instead of ordering the frontier by the distance travelled so far, g(v), it orders it by g(v) + h(v), where h(v) estimates the distance still to go. On a road map the natural estimate is the straight-line distance to the goal. As long as that estimate never overestimates the real remaining distance, A* still returns the shortest route; it just stops wasting effort on streets that lead away from the goal.

  1. Set g(start) = 0 and push the start with priority h(start).
  2. Pop the intersection with the lowest g + h. If it is the goal, walk the parent pointers back: that is the shortest route.
  3. For each street out of it, compute g through this intersection. If that beats the neighbour's current g, record it and its parent, and push the neighbour with priority g + h.
  4. Skip intersections already closed. With a consistent heuristic such as straight-line distance, a closed intersection never needs reopening.

Implementation

import heapq
from math import dist


def a_star(graph, pos, start, goal):
    """graph: {node: [(neighbour, length)]}, pos: {node: (x, y)}."""
    g = {start: 0}
    parent = {start: None}
    frontier = [(dist(pos[start], pos[goal]), start)]
    closed = set()

    while frontier:
        _, node = heapq.heappop(frontier)
        if node in closed:
            continue
        if node == goal:
            route = []
            while node is not None:
                route.append(node)
                node = parent[node]
            return route[::-1]
        closed.add(node)
        for neighbour, length in graph[node]:
            candidate = g[node] + length
            if candidate < g.get(neighbour, float("inf")):
                g[neighbour] = candidate
                parent[neighbour] = node
                estimate = candidate + dist(pos[neighbour], pos[goal])
                heapq.heappush(frontier, (estimate, neighbour))
    return None

When to use it

  • Use it for one start and one goal when you can estimate the remaining distance: maps, game grids, puzzle states.
  • Keep the heuristic admissible (never above the true distance) if you need the shortest route. Straight-line distance is admissible on roads; Manhattan distance is on a 4-way grid.
  • Inflate the heuristic (weighted A*, g + w·h with w > 1) when a slightly longer route found much faster is a good trade.
  • Skip it when you need distances to every node. There is no single goal to aim at, so plain Dijkstra does the same work with less bookkeeping.

Watch the counter in the race under the map: A* and Dijkstra return the same kilometres, but A* usually settles a fraction of the intersections. The saving grows the further apart the two dots are, because Dijkstra's circle grows with the square of the distance while A*'s corridor grows roughly linearly.

Check yourself

What happens if the heuristic overestimates the remaining distance?

A* can close the goal through a longer route before the better one ever reaches the front of the queue, so the route it returns may not be the shortest. It usually gets faster, which is why weighted A* overestimates on purpose.

What does A* do with h(v) = 0 for every v?

It orders the frontier by g alone, which is exactly Dijkstra's algorithm, and explores in every direction at once.

More pathfinding algorithms