Coding · Algorithms
A* search algorithm explained: how it works, code and complexity
Short answer
A* search finds a shortest path from a start node to one goal node by combining the cost so far, g(n), with an estimate of the remaining cost, h(n). It always expands the node with the smallest f(n) = g(n) + h(n). If the heuristic never overestimates the true remaining cost, A* is guaranteed to return an optimal path, and a good heuristic makes it explore far fewer nodes than Dijkstra's algorithm.
What problem A* solves
Dijkstra's algorithm expands nodes in rings of growing distance in every direction, even directions that lead away from the goal. When you know where the goal is, that is wasted work. A* adds a heuristic, an estimate of the distance still to go, so the search is pulled toward the goal. It is the standard algorithm for pathfinding in games, robotics and maps.
A* was described by Peter Hart, Nils Nilsson and Bertram Raphael in 1968 in "A Formal Basis for the Heuristic Determination of Minimum Cost Paths".
The idea in plain words
| Symbol | Meaning |
|---|---|
| g(n) | Cost of the best known path from the start to n. |
| h(n) | Heuristic estimate of the cost from n to the goal. |
| f(n) = g(n) + h(n) | Estimated cost of the cheapest full path through n. The open set is ordered by f. |
- Put the start in a priority queue (the open set) with g = 0 and f = h(start).
- Pop the node with the smallest f. If it is the goal, rebuild the path and stop.
- For each neighbor, compute a tentative g = g(current) + edge cost. If it is better than the neighbor's known g, record it, set the parent, and push the neighbor with f = g + h.
- If the open set becomes empty, there is no path.
With h(n) = 0 for every node, A* becomes exactly Dijkstra's algorithm. With a perfect heuristic, it walks straight along an optimal path.
Choosing a heuristic
A heuristic is admissible if it never overestimates the true remaining cost. It is consistent (or monotone) if h(n) <= cost(n, m) + h(m) for every edge n → m. Consistent heuristics are also admissible, and with them each node needs to be expanded only once.
| Movement | Heuristic | Formula |
|---|---|---|
| 4 directions on a grid, cost 1 | Manhattan distance | abs(dx) + abs(dy) |
| 8 directions, diagonal cost 1 | Chebyshev distance | max(abs(dx), abs(dy)) |
| 8 directions, diagonal cost √2 | Octile distance | max(dx, dy) + (sqrt(2) - 1) * min(dx, dy) with absolute dx, dy |
| Any direction, straight lines | Euclidean distance | sqrt(dx * dx + dy * dy) |
Python implementation on a grid
The grid below has 5 rows and 7 columns; # marks a wall in column 5. Cells are (row, column). Moves go up, down, left and right with cost 1, so Manhattan distance is admissible and consistent.
import heapq
def a_star(grid, start, goal):
rows, cols = len(grid), len(grid[0])
h = lambda p: abs(p[0] - goal[0]) + abs(p[1] - goal[1])
g = {start: 0}
parent = {start: None}
open_heap = [(h(start), start)]
while open_heap:
f, cur = heapq.heappop(open_heap)
if cur == goal:
path = []
while cur is not None:
path.append(cur)
cur = parent[cur]
return path[::-1]
if f > g[cur] + h(cur):
continue # outdated entry
r, c = cur
for nb in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nb[0] < rows and 0 <= nb[1] < cols and grid[nb[0]][nb[1]] != "#":
ng = g[cur] + 1
if ng < g.get(nb, float("inf")):
g[nb] = ng
parent[nb] = cur
heapq.heappush(open_heap, (ng + h(nb), nb))
return None
grid = [".......",
".....#.",
".....#.",
".....#.",
"......."]
path = a_star(grid, (2, 3), (2, 6))
print(len(path) - 1, path)
# 7 [(2, 3), (2, 4), (1, 4), (0, 4), (0, 5), (0, 6), (1, 6), (2, 6)]Worked example, step by step
In the grid above, the start (2, 3) is 3 steps from the goal (2, 6) in a straight line, so the first f is 0 + 3 = 3. The wall blocks that line, and the real shortest path has 7 steps. A* discovers this in stages: it expands all cells with the smallest f, and when those run out, the next smallest f.
| f value | Cells expanded (in order) | What happened |
|---|---|---|
| 3 | (2, 3), (2, 4) | Straight toward the goal until the wall. |
| 5 | (1, 3), (1, 4), (2, 2), (3, 3), (3, 4) | One step sideways or back costs 2 extra; still blocked. |
| 7 | (0, 3), (0, 4), (0, 5), (0, 6), (1, 2), (1, 6), (2, 1), (2, 6) | Around the top of the wall; the goal is popped with f = 7. |
A* expanded 15 of the 32 open cells. Dijkstra's algorithm (A* with h = 0) expands all 32, because every open cell is at most 7 steps from the start. On large open maps the saving is much bigger.
Time and space complexity
| Measure | Cost | Reason |
|---|---|---|
| Worst-case time | O((V + E) log V) | Same as Dijkstra: a useless heuristic such as h = 0 gives no guidance. |
| Typical time | much less than Dijkstra | Depends entirely on heuristic quality; a perfect h expands only nodes on the path. |
| Space | O(V) | The open heap, g values and parents. Memory is often the real limit on huge maps. |
Memory-saving variants include IDA* (iterative deepening A*), which keeps only the current path, at the cost of revisiting nodes.
When to use A* and real-world uses
- Use A* when there is one goal and a cheap, admissible estimate of the remaining cost, such as geometric distance on a map.
- Use Dijkstra when you need distances to many or all nodes, or when no useful heuristic exists. Use BFS for unweighted graphs where a heuristic gives little benefit.
- Video games: unit movement on tile maps and navigation meshes.
- Robotics and route planning, often combined with precomputed landmarks or hierarchies.
- Puzzle solving: the 8-puzzle and 15-puzzle with the Manhattan distance of tiles as the heuristic.
FAQ
Is A* always optimal?
A* returns an optimal path when its heuristic is admissible, meaning it never overestimates the remaining cost. With an overestimating heuristic it can return a longer path.
What is the difference between A* and Dijkstra's algorithm?
Dijkstra orders nodes by the cost so far, g(n). A* orders them by g(n) + h(n), where h estimates the remaining cost to the goal. A* with h = 0 is Dijkstra.
Which heuristic should I use on a grid?
Use Manhattan distance for 4-direction movement, Chebyshev or octile distance for 8-direction movement depending on the diagonal cost, and Euclidean distance for free movement.
What is greedy best-first search?
It orders nodes by h(n) alone and ignores the cost so far. It is often fast but gives no guarantee of a shortest path.