A* search

Dijkstra’s method spreads out evenly in every direction, even when the target is clearly to the east. A* (say “A star”) adds a guess of the distance still to go, and searches towards the target first, without giving up the guarantee of a shortest route.

Searching towards a goal

Dijkstra takes the vertex with the smallest g(v), the time from the start so far. A* takes the vertex with the smallest

where h(v) is a heuristic: a guess, worked out from v alone, of the distance from v to the goal. On a map, h(v) can be the straight-line distance from v to the goal. f(v) is then a guess of the length of the best route that passes through v. With h = 0 for every vertex, A* is Dijkstra.

Step through the figure: a grid where each move costs 1, with a wall between the start and the goal. Dijkstra takes 33 squares before it reaches the goal; A* takes 18, nearly all of them on the way.

The code is Dijkstra’s, with f in the heap and a stop at the goal:

import heapq
import math

def a_star(adj, s, goal, h):     # adj[u]: list of (v, w), w >= 0
    g = {s: 0}
    heap = [(h(s), s)]
    while heap:
        f, u = heapq.heappop(heap)
        if u == goal:
            return g[u]
        if f > g[u] + h(u):
            continue                # an old entry
        for v, w in adj[u]:
            if g[u] + w < g.get(v, math.inf):
                g[v] = g[u] + w
                heapq.heappush(heap, (g[v] + h(v), v))
    return math.inf

A guess that is never too high

Two properties of h decide whether A* is right and how fast it is.

• Admissible: h(v) is never more than the true distance from v to the goal. The guess may be too low, never too high. The straight-line distance is admissible, because no route is shorter than a straight line.
• Consistent: for every edge u → v, h(u) ≤ w(u, v) + h(v). The guess never drops by more than the edge just used. The straight-line distance is consistent too (it is the triangle rule of geometry). A consistent h with h(goal) = 0 is always admissible.

A larger h, as long as it stays admissible, means fewer vertices looked at: h equal to the true distance would walk straight along a shortest route. h = 0 is admissible and gives back Dijkstra. A guess that is sometimes too high can make A* return a route that is not the shortest.

Why A* is right

With a consistent h there is a short proof: A* is Dijkstra on a changed graph. Give every edge the new weight

Consistency says exactly that every w′ is 0 or more, so Dijkstra is correct on the new weights. Along any route from s to v the new weights add up to the old length − h(s) + h(v), because the h terms in the middle cancel in pairs. So every route from s to the goal changes by the same amount, −h(s) + h(goal), and shortest routes stay shortest. And Dijkstra’s order on the new weights is the order of g(v) + h(v) − h(s): the order of f, since h(s) is the same for every vertex. This is the reweighting of Johnson’s method (lesson 5).

So with a consistent h, every vertex is settled once, with its true g, and the goal’s g is final when it comes out of the heap. With an h that is admissible but not consistent, A* still returns a shortest route if it allows a settled vertex to be lowered and handled again. Every vertex taken out has f(v) ≤ δ(s, goal), so A* only looks at vertices that the guess cannot rule out.

Guesses for grids, and ties

• Four directions, each move costs 1: the Manhattan distance |x − x_goal| + |y − y_goal|. Each move changes x or y by 1, so it is consistent.
• Eight directions, with diagonal moves costing √2 (the square root of 2, about 1.414): the octile distance max(dx, dy) + (√2 − 1) · min(dx, dy), where dx and dy are how far apart the columns and rows are. With all eight moves costing 1, use max(dx, dy).
• Any direction on a map: the straight-line distance, math.dist(p, goal).

Ties. On an open grid, every square in the rectangle between the start and the goal has the same f: g + h equals the Manhattan distance of the whole trip. If ties go to the square with the smaller g, or to the square added first, A* fills that whole rectangle, d² squares (d times d) for a goal d moves away diagonally. If ties go to the larger g, the square nearest the goal, A* walks straight there. With heapq, push (f, -g, square): the minus sign makes the larger g come first. PATH-P7 has a test built for this.

Where A* is used

• Games and robots find routes on grids and meshes with A*, often with a guess made a little too high on purpose (weighted A*, f = g + 1.5 h): routes may be a little longer, but far fewer squares are looked at.
• Puzzles. For the 15-puzzle, the sum over the tiles of each tile’s Manhattan distance to its place is admissible. The state graph is too big to store; A* builds it as it goes.
• Road maps. Route planners use guesses worked out in advance: landmarks (distances to a few chosen places give lower bounds by the triangle rule, the ALT method), and contraction hierarchies, which add shortcut edges so a search touches only a few hundred vertices of a continent-sized map.
• Memory. A* keeps every reached vertex. When that is too much, IDA* repeats depth-first searches with a growing limit on f, using memory only for the current path.

Without a single goal, or without a good guess, A* has nothing to add to Dijkstra. Its worst case is the same, O((V + E) log V). Now try PATH-P7, Across an endless grid.