A Search is a shortest-path algorithm that uses a heuristic to guide its exploration toward a specific goal. Where Dijkstra's algorithm expands outward in all directions from the source, A prioritizes nodes that appear closer to the destination, which lets it find the shortest path while exploring far fewer nodes.

A* is widely used in GPS navigation, game pathfinding, and robotics motion planning, anywhere a single shortest path needs to be computed quickly between a known start and a known goal.

What Is A* Search?

A (pronounced "A-star") is a best-first search algorithm* that finds the shortest path between a start node and a goal node. It combines two pieces of information for each node:

g(n): The actual cost from the start node to node n (what we have already paid)
h(n): A heuristic estimate of the cost from node n to the goal (what we expect to pay)

The algorithm uses their sum:

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

At every step, A* picks the node with the lowest f(n) value. This favors nodes that are both cheap to reach (low g) and close to the goal (low h). The result is a search that gravitates toward the destination instead of spreading in all directions.

The diagram below compares the two approaches for a path from node S to node G. Dijkstra explores uniformly, while A* focuses toward the goal.

Dijkstra expands many nodes it does not need. A* uses the heuristic to skip unpromising directions and reach the goal faster, while still guaranteeing the optimal path as long as the heuristic is admissible (never overestimates the true cost to the goal).

The Key Insight: Heuristics

The heuristic h(n) is what differentiates A* from Dijkstra. A poorly chosen heuristic can produce incorrect results or no speedup at all, so two properties matter: admissibility and consistency.

Admissibility

A heuristic is admissible if it never overestimates the true cost to reach the goal.

The heuristic can be optimistic (underestimate) or exactly right, but it must never say "it will cost 10" when the real cost is 5. Overestimating can cause A* to skip the optimal path in favor of a suboptimal one that looked cheaper.

Why does admissibility guarantee optimality? Because if h(n) never overestimates, then f(n) = g(n) + h(n) never overestimates the total cost through n. So the first time A reaches the goal, it is guaranteed to have found the cheapest path. If h overestimated somewhere, A might have avoided a node on the true shortest path, thinking it was too expensive.

Consistency (Monotonicity)

A heuristic is consistent if for every node n and every neighbor n' reached via edge cost c(n, n'):

h(n) <= c(n, n') + h(n')

This is the triangle inequality. It means the estimated cost from n should not exceed the cost of stepping to a neighbor plus the estimate from that neighbor. Consistency is a stronger condition than admissibility. Every consistent heuristic is admissible, but not every admissible heuristic is consistent.

Why does consistency matter? With a consistent heuristic, once A expands (closes) a node, it has already found the shortest path to that node. You never need to re-open a closed node. This simplifies the implementation and makes A more efficient.

Common Heuristics for Grid Problems

For pathfinding on a 2D grid, the most common heuristics are:

Heuristic	Formula	Best For
Manhattan Distance	\|x1 - x2\| + \|y1 - y2\|	4-directional movement (up, down, left, right)
Euclidean Distance	sqrt((x1-x2)^2 + (y1-y2)^2)	Any-angle movement
Chebyshev Distance	max(\|x1-x2\|, \|y1-y2\|)	8-directional movement (including diagonals, uniform cost)

All three are admissible for their respective movement types. Manhattan distance fits most grid problems, which allow only 4-directional movement.

How A* Works

The algorithm maintains two collections:

Open set: Nodes discovered but not yet fully explored. Implemented as a priority queue sorted by f(n), so the most promising node is always pulled next.
Closed set: Nodes that have been fully explored. We have already found the shortest path to these nodes and processed all their neighbors.

Here is the step-by-step process:

Add the start node to the open set with g = 0 and h = heuristic(start, goal).
While the open set is not empty:

Remove the node with the smallest f value from the open set. Call it current.
If current is the goal, reconstruct and return the path.
Add current to the closed set.
For each neighbor of current:

If the neighbor is in the closed set, skip it.
Calculate tentative_g = g(current) + cost(current, neighbor).
If the neighbor is not in the open set, add it with the computed g and f values.
If the neighbor is already in the open set but tentative_g is lower than its current g, update its g and f values (we found a better path to it).

If the open set is empty and we never reached the goal, no path exists.

Path reconstruction works by keeping a parent map. Every time we update a node's best path, we record which node we came from. Once we reach the goal, we follow parent pointers backward from goal to start to get the full path.

Step-by-Step Walkthrough

Let us trace A* on a small grid to see exactly how it works. Consider this 4x4 grid where S is the start (0,0), G is the goal (3,3), and X marks obstacles. Movement is 4-directional with a cost of 1 per step.

We use Manhattan distance as our heuristic. Let us label cells by (row, col).

Initial state:

Open: {(0,0) with g=0, h=6, f=6}
Closed: {}

Step 1: Expand (0,0), f=6

Neighbors: (0,1) and (1,0)
(0,1): g=1, h=|0-3|+|1-3|=5, f=6
(1,0): g=1, h=|1-3|+|0-3|=5, f=6
Open: {(0,1) f=6, (1,0) f=6}
Closed: {(0,0)}

Step 2: Expand (0,1), f=6 (tie-broken arbitrarily)

Neighbors: (0,0) closed, (0,2), (1,1) is obstacle
(0,2): g=2, h=|0-3|+|2-3|=4, f=6
Open: {(1,0) f=6, (0,2) f=6}
Closed: {(0,0), (0,1)}

Step 3: Expand (1,0), f=6

Neighbors: (0,0) closed, (2,0)
(2,0): g=2, h=|2-3|+|0-3|=4, f=6
Open: {(0,2) f=6, (2,0) f=6}
Closed: {(0,0), (0,1), (1,0)}

Step 4: Expand (0,2), f=6

Neighbors: (0,1) closed, (0,3), (1,2)
(0,3): g=3, h=|0-3|+|3-3|=3, f=6
(1,2): g=3, h=|1-3|+|2-3|=3, f=6
Open: {(2,0) f=6, (0,3) f=6, (1,2) f=6}
Closed: {(0,0), (0,1), (1,0), (0,2)}

Step 5: Expand (0,3), f=6

Neighbors: (0,2) closed, (1,3)
(1,3): g=4, h=|1-3|+|3-3|=2, f=6
Open: {(2,0) f=6, (1,2) f=6, (1,3) f=6}

Step 6: Expand (1,2), f=6

Neighbors: (0,2) closed, (2,2)
(2,2): g=4, h=|2-3|+|2-3|=2, f=6

Step 7: Expand (1,3), f=6

Neighbors: (0,3) closed, (2,3)
(2,3): g=5, h=|2-3|+|3-3|=1, f=6

Step 8: Expand (2,2), f=6

Neighbors: (1,2) closed, (2,3) already has g=5 (same), (3,2)
(3,2): g=5, h=|3-3|+|2-3|=1, f=6

Step 9: Expand (2,3), f=6

Neighbor: (3,3) is the goal!
(3,3): g=6, h=0, f=6
Goal reached.

Path: (0,0) -> (0,1) -> (0,2) -> (0,3) -> (1,3) -> (2,3) -> (3,3), cost = 6.

Every expanded node had f=6 because the optimal path length equals the Manhattan distance from start to goal (the obstacles do not lengthen the path here, since a route around them has the same length). When obstacles force a detour, f values increase, and A* focuses on the nodes with lower f.

Implementation

Here is a complete implementation of A* for a weighted graph using an adjacency list. The graph has nodes identified by integers, and edges have associated costs.

We use a lazy deletion approach for the priority queue. Instead of updating priorities (which most standard priority queues do not support efficiently), we add a new entry with the updated f value. When we poll a node that is already closed, we skip it. This is simpler than maintaining a decrease-key operation on the queue.
The closed array (or set) serves as our closed set. Once a node is marked closed, we never process it again (valid because we assume a consistent heuristic).
Path reconstruction walks backward from the goal using the parent array.

A* vs Dijkstra

Dijkstra's algorithm is A* with h(n) = 0 for every node. Without a heuristic, f(n) = g(n), so Dijkstra always expands the node with the lowest actual cost from the source. It explores in concentric "rings" of increasing distance, which is correct but wasteful when you have a specific destination.

Aspect	Dijkstra	A*
Explores	All directions uniformly	Focused toward goal
Heuristic	None (h = 0)	Uses h(n) to estimate remaining cost
Optimal?	Always	Yes, if h is admissible
Best for	Single source, all destinations	Single source, single destination
Nodes explored	More (for single target)	Fewer (guided by heuristic)
Time complexity	O((V + E) log V)	O((V + E) log V) worst case, but typically much better

Complexity Analysis

Time Complexity

The worst case is O((V + E) log V) with a binary-heap priority queue, the same bound as Dijkstra, since A with h(n) = 0 reduces to Dijkstra. A more precise characterization is that the running time depends on the quality of the heuristic. The number of nodes A expands can be exponential in the worst case, but it stays far smaller with an accurate, admissible heuristic, which is why A* usually explores many fewer nodes than Dijkstra on the same graph.

Space Complexity

A needs O(V) space to store the g, f, and parent information for each node, plus the open and closed sets. The main practical limitation of A is memory, because the open set can hold a large fraction of the graph's nodes before the goal is reached.

Key Takeaways

A* is a best-first search that always expands the frontier node with the lowest f(n) = g(n) + h(n), where g(n) is the actual cost from the start and h(n) is a heuristic estimate of the remaining cost to the goal.
A generalizes Dijkstra's algorithm, which is the special case where h(n) = 0; the heuristic is what steers A toward the goal instead of expanding uniformly in all directions.
A* returns the optimal path when the heuristic is admissible, meaning it never overestimates the true cost to the goal.
When the heuristic is consistent, satisfying h(n) <= c(n, n') + h(n') for every edge, A* never needs to reopen a closed node because it has already found the shortest path to each node when it closes it.
On 2D grids, Manhattan distance fits 4-directional movement and Euclidean distance fits any-angle movement, and both stay admissible for their respective movement types.
A* has a worst-case time complexity of O((V + E) log V), the same as Dijkstra, but a good heuristic usually makes it explore far fewer nodes in practice.

Quiz

A* Search Algorithm Quiz

10 quizzes