liveBook · Manning

A* algorithm

As explained in Algorithms Every Programmer Should Know

A* is a best-first search algorithm that prioritizes paths using their cost so far and a heuristic estimate of the remaining cost.

Suppose you need the cheapest route across a city, but you only care about one destination. Dijkstra’s algorithm may explore streets in every direction. A* adds an estimate of the distance still to go, helping the search lean toward the goal without giving up the shortest-path guarantee when the heuristic meets the required conditions. section 12.0 section 12.1

For each node n, A* keeps three values:

  • g(n): the actual cost from the start to n. section 12.4
  • h(n): a cheap estimate of the remaining cost to the goal. section 12.4
  • f(n) = g(n) + h(n): the estimated total cost. A* expands the queued node with the smallest f value. section 12.4

The estimate must be admissible: it must never exceed the true remaining cost. Straight-line distance is an example for road routes; Manhattan distance works for movement restricted to four grid directions. A stronger property, consistency, means an expanded node need not be reopened. section 12.1 section 12.4

Do not stop when you first see the goal

On a six-intersection map, A* first finds a route to the goal costing 11. Another node still has a lower f value, so the search continues. Expanding it reveals a route costing 10. A* updates the goal’s cost and parent pointer, then finishes when the goal comes off the priority queue. Following parent pointers recovers the cheaper path. section 12.1

Listing 12.1 Pseudocode of A* Algorithm
function A_STAR(start, goal):
    open_set = priority queue ordered by f, containing {start}
    g[start] = 0
    f[start] = h(start)
    came_from = empty map
 
    while open_set is not empty:
        current = node in open_set with smallest f
        if current == goal:
            return reconstruct_path(came_from, current)
 
        remove current from open_set
        for each neighbor of current:
            tentative_g = g[current] + cost(current, neighbor)
            if tentative_g < g[neighbor] (or neighbor has no g yet):
                came_from[neighbor] = current
                g[neighbor] = tentative_g
                f[neighbor] = tentative_g + h(neighbor)
                add neighbor to open_set if not already present
 
    return "no path exists"
 

The pseudocode shows the working loop: take the lowest-f node, test for the goal, improve neighbors’ g values when possible, and record their parents for path reconstruction. section 12.1

A weak heuristic can leave A* exploring as much as Dijkstra. With a binary priority queue, worst-case time is O((V + E) log V). Memory is often the tougher limit because discovered nodes retain scores and parent pointers. Iterative Deepening A* (IDA*) trades repeated search work for a smaller memory footprint. section 12.3

How Algorithms Every Programmer Should Know covers it

How deep it goes
Works through a six-node priority-queue trace and pseudocode, then examines guarantees, worst-case time, and memory costs.
Examples
Traces a six-intersection route where a cost-11 goal path is replaced by a cost-10 path.
What it assumes
Builds on weighted-graph shortest paths and Dijkstra’s algorithm while defining the heuristic and A* scores.
What you can do after
Build it from scratch using a priority queue, heuristic scores, neighbor-cost updates, and parent pointers.
How it connects
Connects heuristic search to Dijkstra’s algorithm, admissibility, consistency, priority queues, and Iterative Deepening A*.

Also explained in

Compare how 6 books explain A* algorithm →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Algorithms Every Programmer Should Know. The section links point to the parts of the book it draws on.