A* Search Algorithm

A* (pronounced “A-star”) finds a lowest-cost path from one start state to one goal state. It is useful when a problem has many possible routes and can provide a reasonable estimate of how far each candidate is from the goal.

The algorithm combines the cost already paid with an estimate of the cost still remaining. This lets it avoid exploring many routes that point away from the goal while preserving the shortest-path guarantee when the estimate follows the required rules.

The Problem It Solves

Suppose a map, game board, or puzzle is represented as a graph:

A vertex is a location or state.
An edge is an allowed move.
An edge weight is the cost of that move.
A path is a sequence of moves from the start to the goal.

The task is to find a path whose total edge weight is as small as possible.

Dijkstra’s algorithm solves this problem by expanding the candidate with the smallest cost from the start. A* adds information about the goal, so it can often search a smaller part of the graph.

The Core Idea

A* gives every candidate vertex a priority:

f (n) = g (n) + h (n)

Value	Meaning
$g (n)$	The cheapest cost currently known from the start to vertex $n$
$h (n)$	An estimate of the cheapest remaining cost from $n$ to the goal
$f (n)$	The estimated total cost of a complete path that goes through $n$

The algorithm uses a priority queue to expand the vertex with the smallest $f$ value.

The two parts have different roles. The $g$ value is based on moves that have actually been taken, while the $h$ value predicts work that has not been done yet. The heuristic does not replace the real path cost. It only helps decide which candidate to examine next.

How the Search Proceeds

A* starts with the start vertex. Its known cost is 0, so its initial priority is just the heuristic estimate.

It then repeats these steps:

Remove the candidate with the smallest $f$ value from the priority queue.
If that candidate is the goal, reconstruct and return the path.
Examine every neighboring vertex.
Calculate the new $g$ value obtained by moving through the current vertex.
If this route is cheaper than the best route previously known for the neighbor, record the new cost and parent.
Push the neighbor with priority $g + h$ .

Updating a neighbor with a cheaper route is called relaxation. A vertex may enter the priority queue more than once because a later route can improve its $g$ value.

A Small Trace

Consider this directed weighted graph:

S -> A costs 2
S -> B costs 1
A -> G costs 5
B -> C costs 1
C -> G costs 2

S is the start and G is the goal. Use these heuristic estimates:

h(S) = 4
h(A) = 5
h(B) = 3
h(C) = 2
h(G) = 0

The search develops as follows:

Step	Vertex removed	New candidates	Reason
1	`S`, with $f = 0 + 4 = 4$	`A`: $g = 2$ , $f = 7$ , and `B`: $g = 1$ , $f = 4$	Both routes begin at `S`
2	`B`, with $f = 1 + 3 = 4$	`C`: $g = 2$ , $f = 4$	`B -> C` adds cost `1`
3	`C`, with $f = 2 + 2 = 4$	`G`: $g = 4$ , $f = 4$	`C -> G` adds cost `2`
4	`G`, with $f = 4 + 0 = 4$	Stop	The goal is the best candidate

The returned path is S -> B -> C -> G, with total cost 4.

Notice that A remains a possible route, but its estimated total cost is 7. A* reaches the goal without expanding it.

How A* Relates to Other Search Algorithms

These algorithms differ mainly in the value used to choose the next candidate:

Algorithm	Priority	Main condition or tradeoff
BFS	Number of edges from the start	Finds a shortest path when every move has equal cost
Dijkstra	$g (n)$	Finds a lowest-cost path with non-negative edge weights
Greedy best-first search	$h (n)$	May reach the goal quickly but ignores cost already paid
A*	$g (n) + h (n)$	Balances real cost with estimated remaining cost

If $h (n) = 0$ for every vertex, A* becomes Dijkstra’s algorithm. As the heuristic becomes more informative, A* can focus its search more strongly toward the goal.

Greedy best-first search uses only the estimated distance to the goal. It can choose a route that looks close but has already become very expensive. A* keeps that mistake in check by including $g (n)$ .

What Makes a Heuristic Safe

A heuristic is a function that estimates the cheapest remaining cost. It does not have to be exact, but an optimal-path guarantee needs it to be admissible.

An admissible heuristic never overestimates the true cheapest remaining cost. If $h^{*} (n)$ means that true cost, then:

h (n) \leq h^{*} (n)

In the usual shortest-path setup, the heuristic is also non-negative and gives the goal an estimate of 0.

Examples include:

On a four-direction grid where each move costs 1, Manhattan distance is admissible: $∣ r - r_{g} ∣ + ∣ c - c_{g} ∣$ .
On a road map whose edge weights are physical distances, straight-line distance to the destination is admissible because a road route cannot be shorter than the straight line between its endpoints.
The constant heuristic 0 is always safe, although it provides no guidance beyond Dijkstra’s algorithm.

The movement rules and cost units matter. Manhattan distance can overestimate the remaining cost if cheap diagonal movement is allowed. A distance measured in grid steps is also invalid when edge weights represent a different quantity such as time or risk.

A stronger property is consistency. For an edge from $n$ to $m$ with cost $c (n, m)$ , a consistent heuristic satisfies:

h (n) \leq c (n, m) + h (m)

In plain language, taking one real step should not make the estimated remaining cost fall by more than the cost of that step. Consistency prevents a vertex’s best cost from needing to be reopened after it has been finalized. The implementation below still accepts improvements instead of relying on a permanent visited decision.

If a heuristic overestimates, A* may explore fewer vertices, but it is no longer guaranteed to return a lowest-cost path.

Function Contract

The implementation below uses these inputs:

graph is an adjacency list for a weighted graph.
graph[node] contains (neighbor, cost) pairs.
start and goal are keys in graph.
Every edge cost is non-negative.
heuristic(node, goal) returns an estimated remaining cost in the same unit as the edge costs.

It returns (path, cost):

path is a list from start to goal.
cost is the total edge weight of that path.
If the goal is unreachable, it returns (None, float("inf")).

For the returned path to be guaranteed optimal, the heuristic must be admissible and must return 0 at the goal.

Python Implementation

import heapq
from itertools import count
 
 
def reconstruct_path(parent, goal):
    path = []
    node = goal
 
    while node is not None:
        path.append(node)
        node = parent[node]
 
    return path[::-1]
 
 
def a_star(graph, start, goal, heuristic):
    g_score = {start: 0}
    parent = {start: None}
 
    order = count()
    frontier = [(heuristic(start, goal), next(order), 0, start)]
 
    while frontier:
        _, _, current_g, node = heapq.heappop(frontier)
 
        if current_g != g_score.get(node):
            continue
 
        if node == goal:
            return reconstruct_path(parent, goal), current_g
 
        for neighbor, edge_cost in graph[node]:
            tentative_g = current_g + edge_cost
 
            if tentative_g < g_score.get(neighbor, float("inf")):
                g_score[neighbor] = tentative_g
                parent[neighbor] = node
                priority = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(
                    frontier,
                    (priority, next(order), tentative_g, neighbor),
                )
 
    return None, float("inf")

Here is the traced graph in executable form:

graph = {
    "S": [("A", 2), ("B", 1)],
    "A": [("G", 5)],
    "B": [("C", 1)],
    "C": [("G", 2)],
    "G": [],
}
 
estimate = {
    "S": 4,
    "A": 5,
    "B": 3,
    "C": 2,
    "G": 0,
}
 
path, cost = a_star(
    graph,
    start="S",
    goal="G",
    heuristic=lambda node, goal: estimate[node],
)
 
print(path)  # ['S', 'B', 'C', 'G']
print(cost)  # 4

What the Implementation Stores

g_score[node] is the cheapest start-to-node cost found so far. It is not just a visited marker. If a cheaper route appears, the value must be updated.

parent[node] records which previous vertex produced the current best cost. Following these parents backward from the goal reconstructs the path.

frontier is the priority queue. Each entry contains the $f$ priority, a tie-breaking counter, the $g$ value used when the entry was created, and the vertex itself.

The stale-entry check handles improvements. Python’s heap does not replace an old entry when a better route is discovered. The better route is pushed as a new entry, and the older one is ignored if it is removed later.

The counter prevents Python from trying to compare vertex values when two priorities tie. This matters when vertices are objects that do not define an ordering.

Why the Optimality Guarantee Works

Assume the heuristic is admissible. Until the optimal goal route has been completed, the frontier contains a candidate on an optimal path whose recorded $g$ value is the true cost of that path prefix. Its $f$ value is no greater than the total cost of the optimal path because its heuristic does not overestimate the cost still remaining.

The goal has $h = 0$ , so its $f$ value equals the complete path cost already paid. A suboptimal goal route therefore cannot be removed before every candidate that could still lead to a cheaper optimal route. When the goal is removed as the smallest-priority current entry, its recorded $g$ value is optimal.

Non-negative edge costs are part of this guarantee. Negative costs require a different shortest-path model and can invalidate the assumptions used by this search.

Complexity

A* has no single useful performance bound that ignores the heuristic. Its practical cost depends heavily on how many vertices the heuristic causes it to expand.

With h = 0, the search behaves like heap-based Dijkstra and may inspect most of the reachable graph. A more informative safe heuristic can inspect far fewer vertices. In very large implicit search spaces, a weak heuristic can still lead to exponential growth in the number of explored states.

The priority queue, best-cost table, and parent table also consume memory for discovered candidates. Memory use is often the practical limitation of A* because it keeps frontier information needed to preserve the best path.

Common Mistakes

Using a heuristic that measures the wrong thing is a correctness problem, not only a quality problem. The heuristic and edge weights must use compatible cost units.

Treating the first discovery of a vertex as final is also unsafe. Weighted searches can find a cheaper route later, so the algorithm must compare tentative $g$ values.

Stopping when the goal is first inserted into the priority queue is too early. A different candidate may still lead to a cheaper goal route. Stop when the goal is removed as the smallest valid priority entry.

Another mistake is assuming that a more aggressive heuristic is always better. A large estimate may make the search look focused while giving up the optimal-path guarantee.

When To Use A*

Use A* when all of these are true:

The problem asks for a path from one known start to one known goal.
Moves have non-negative costs.
The search space is large enough that goal-directed guidance could help.
A cheap heuristic can estimate remaining cost without overestimating it.

Typical applications include grid pathfinding, route planning, game navigation, robot motion planning, and puzzle-state search.

Use Dijkstra when no meaningful heuristic is available or when distances to many different goals are needed. Use BFS when every move has equal cost and the graph is small enough that goal-directed guidance is unnecessary.

The Main Point

A* chooses the next candidate by adding the real cost already paid to a safe estimate of the cost still remaining. The formula $f = g + h$ is simple, but each part has a strict role. The $g$ value preserves shortest-path reasoning, while the $h$ value directs the search toward the goal. When edge costs are non-negative and the heuristic never overestimates and is zero at the goal, A* returns a lowest-cost path while often exploring much less of the graph than an unguided shortest-path search.

Insight Vault

Browse