A* Search Algorithm

A* (pronounced "A-star") is an informed search algorithm: it finds the shortest path between a start and a goal vertex, but unlike Dijkstra's algorithm it uses extra knowledge about where the goal is to steer the search towards it rather than groping outwards in every direction. That extra knowledge is supplied by a heuristic function $h(n)$h(n), an estimate of how far each vertex is from the goal. By combining the known cost of getting to a vertex with the estimated cost of getting from it to the goal, A* concentrates its effort along promising routes and so typically examines far fewer vertices than Dijkstra's while still — given a sensible heuristic — returning the genuinely shortest path. It is the workhorse of game-AI pathfinding, robotics and route planning. At A-Level you must understand the formula $f(n)=g(n)+h(n)$f(n)=g(n)+h(n), the meaning and importance of an admissible heuristic, why A* expands fewer nodes than Dijkstra's, and how to trace a small example.

---

Spec Mapping

This lesson addresses AQA A-Level Computer Science (7517), Section 4.3 Fundamentals of algorithms, specifically 4.3.6 Optimisation algorithms (A* search). The specification requires you to understand how A* finds the shortest path, the role of the cost function $f(n)=g(n)+h(n)$f(n)=g(n)+h(n), and the contrast with Dijkstra's algorithm. It builds directly on Dijkstra's algorithm (4.3.6) — A* is Dijkstra's with a heuristic added — on priority queues (4.2.4) for the open set, on graphs (4.2.6) for the search space, and on the idea of a heuristic from the optimisation/intractability strand (4.4.4 / 4.3.6). The admissibility analysis uses the complexity and optimality reasoning of 4.4.4.

---

The Key Idea

Dijkstra's algorithm finalises vertices strictly in order of their distance from the source. With no notion of which direction the goal lies in, it expands outwards uniformly — like a circular ripple — and so finalises many vertices that lie away from the goal before it ever reaches it. On a large map that is a great deal of wasted exploration.

A* fixes this by ranking each candidate vertex $n$n not by how far it is from the start, but by an estimate of the total cost of the whole journey that passes through it:

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

Component	Meaning	Known or estimated?
$g(n)$g(n)	The actual cost of the best path found so far from the start to $n$n	Known (computed by relaxation, exactly as in Dijkstra's)
$h(n)$h(n)	The heuristic estimate of the cost from $n$n onward to the goal	Estimated (a problem-specific guess)
$f(n)$f(n)	The estimated total cost of the cheapest path from start to goal through $n$n	Derived: $g(n)+h(n)$g(n)+h(n)

At each step A* expands the open-set vertex with the lowest $f(n)$f(n). The $g$g term keeps it honest about cost already incurred; the $h$h term pulls it towards the goal. The interplay of the two is the whole algorithm.

---

The Heuristic Function $h(n)$h(n)

The heuristic is an estimate of the remaining distance from a vertex to the goal — cheap to compute, never actually traversing the graph. Its quality determines how well A* performs, and one property of it determines whether A* is even correct: admissibility.

A heuristic is admissible if it never overestimates the true remaining cost: for every vertex $n$n, $h(n) \le h^*(n)$h(n)≤h∗(n), where $h^*(n)$h∗(n) is the real shortest distance from $n$n to the goal. If the heuristic is admissible, A* is guaranteed to return the optimal (shortest) path. Intuitively, an admissible heuristic is optimistic — it may say "the goal looks close" when it is actually far, but it never wrongly says "the goal is far" about a vertex that is in fact close, and it is that one-sided honesty that stops A* from discarding the true best route.

Common heuristics for grid pathfinding

Heuristic	Formula	When to use
Manhattan distance	$h = \lvert x_1 - x_2 \rvert + \lvert y_1 - y_2 \rvert$h=∣x1​−x2​∣+∣y1​−y2​∣	Movement restricted to 4 directions (up, down, left, right)
Euclidean distance	$h = \sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$h=(x1​−x2​)2+(y1​−y2​)2​	Movement allowed in any direction (including diagonals)
Zero heuristic	$h(n) = 0$h(n)=0	Makes A* behave identically to Dijkstra's algorithm

The Manhattan distance is admissible for 4-directional movement because, when you can only step along grid lines, the true shortest distance can never be less than the sum of the horizontal and vertical gaps — so the estimate never exceeds the truth. The zero heuristic is trivially admissible (it never overestimates anything), which is exactly why setting $h(n)=0$h(n)=0 recovers Dijkstra's algorithm: with no goal-direction information, A* ranks purely by $g(n)$g(n), the distance from the source.

Key Insight: $h(n)=0$h(n)=0 for all $n$n turns A* into Dijkstra's algorithm. The heuristic is the only thing that makes A* "smarter": it is what focuses the search towards the goal. The closer $h$h is to the true remaining cost (without ever exceeding it), the more sharply focused — and faster — A* becomes.

---

Pseudocode

PROCEDURE AStar(graph, start, goal, h)
    openSet  = priority queue ordered by f value     // frontier to explore
    closedSet = empty set                             // already finalised

    g[start] = 0
    f[start] = h(start, goal)
    ADD start TO openSet

    WHILE openSet IS NOT EMPTY
        current = vertex in openSet with the LOWEST f value   // extract-min

        IF current = goal THEN
            RECONSTRUCT path via previous[] from start to goal
            RETURN path
        END IF

        REMOVE current FROM openSet
        ADD current TO closedSet

        FOR EACH neighbour OF current
            IF neighbour IN closedSet THEN
                CONTINUE
            END IF

            tentativeG = g[current] + weight(current, neighbour)

            IF neighbour NOT IN openSet THEN
                ADD neighbour TO openSet
            ELSE IF tentativeG >= g[neighbour] THEN
                CONTINUE                              // existing route is no worse
            END IF

            previous[neighbour] = current
            g[neighbour] = tentativeG
            f[neighbour] = g[neighbour] + h(neighbour, goal)
        END FOR
    END WHILE
    RETURN "No path found"
END PROCEDURE

Compare this with the Dijkstra pseudocode of the previous lesson: the structure is identical (an open priority queue, relaxation of neighbours, a closed set of finalised vertices). The only difference is the key used to order the open set — $f = g + h$f=g+h here versus $g$g alone in Dijkstra's. That one change is the entire content of "A* = Dijkstra + heuristic".

---

Full Worked Trace

Consider a 3×4 grid. S is the start, G the goal, and # a wall that cannot be entered. Movement is 4-directional and each step costs 1. We use the Manhattan distance to the goal as the heuristic.

row \ col	0	1	2	3
0	S	.	.	.
1	.	#	#	.
2	.	.	.	G

Coordinates are $(\text{row}, \text{col})$(row,col), so $S=(0,0)$S=(0,0) and $G=(2,3)$G=(2,3). The Manhattan heuristic from a cell $(r,c)$(r,c) is $h = \lvert r-2\rvert + \lvert c-3\rvert$h=∣r−2∣+∣c−3∣.

We show the open set (as cell: g, h, f) and the closed set at each step. The cell extracted each round is the open-set cell with the smallest $f$f (ties broken by larger $g$g, then arbitrarily — a common tie-break that favours cells nearer the goal).

Step 1 — start

$S=(0,0)$S=(0,0): $g=0$g=0, $h=\lvert 0-2\rvert+\lvert 0-3\rvert = 2+3 = 5$h=∣0−2∣+∣0−3∣=2+3=5, so $f=5$f=5.

Open set	Closed set
(0,0): g0 h5 f5	{ }

Step 2 — expand (0,0)

Neighbours of $(0,0)$(0,0) that are not walls: $(0,1)$(0,1) and $(1,0)$(1,0).

• $(0,1)$(0,1): $g=1$g=1, $h=\lvert 0-2\rvert+\lvert 1-3\rvert=2+2=4$h=∣0−2∣+∣1−3∣=2+2=4, $f=5$f=5.
• $(1,0)$(1,0): $g=1$g=1, $h=\lvert 1-2\rvert+\lvert 0-3\rvert=1+3=4$h=∣1−2∣+∣0−3∣=1+3=4, $f=5$f=5.

Open set	Closed set
(0,1): g1 h4 f5, (1,0): g1 h4 f5	{(0,0)}

Step 3 — expand (0,1)

Both open cells have $f=5$f=5; the tie-break (prefer larger $g$g, then towards the goal) selects $(0,1)$(0,1). Its non-wall, non-closed neighbours: $(0,2)$(0,2). ($(1,1)$(1,1) is a wall.)

• $(0,2)$(0,2): $g=2$g=2, $h=\lvert 0-2\rvert+\lvert 2-3\rvert=2+1=3$h=∣0−2∣+∣2−3∣=2+1=3, $f=5$f=5.

Open set	Closed set
(1,0): g1 h4 f5, (0,2): g2 h3 f5	{(0,0), (0,1)}

Step 4 — expand (0,2)

Neighbours: $(0,3)$(0,3). ($(1,2)$(1,2) is a wall.)

• $(0,3)$(0,3): $g=3$g=3, $h=\lvert 0-2\rvert+\lvert 3-3\rvert=2+0=2$h=∣0−2∣+∣3−3∣=2+0=2, $f=5$f=5.

Open set	Closed set
(1,0): g1 h4 f5, (0,3): g3 h2 f5	{(0,0), (0,1), (0,2)}

Step 5 — expand (0,3)

Neighbours: $(1,3)$(1,3).

• $(1,3)$(1,3): $g=4$g=4, $h=\lvert 1-2\rvert+\lvert 3-3\rvert=1+0=1$h=∣1−2∣+∣3−3∣=1+0=1, $f=5$f=5.

Open set	Closed set
(1,0): g1 h4 f5, (1,3): g4 h1 f5	{(0,0), (0,1), (0,2), (0,3)}

Step 6 — expand (1,3)

Neighbours: $(2,3)=G$(2,3)=G.

• $(2,3)$(2,3): $g=5$g=5, $h=0$h=0, $f=5$f=5.

Open set	Closed set
(1,0): g1 h4 f5, (2,3): g5 h0 f5	{(0,0), (0,1), (0,2), (0,3), (1,3)}

Step 7 — extract (2,3) = G

The goal is extracted. A* terminates and reconstructs the path through the previous pointers:

$S(0,0) \to (0,1) \to (0,2) \to (0,3) \to (1,3) \to G(2,3), \qquad \text{total cost } = 5.$S(0,0)→(0,1)→(0,2)→(0,3)→(1,3)→G(2,3),total cost =5.

What just happened — and why it matters

Look at the closed set: A* finalised only the cells along the top edge and down the right side — the cells the heuristic identified as lying on the way to the goal. Crucially, cell $(1,0)$(1,0) entered the open set in step 2 but was never expanded: its $f=5$f=5 tied, but the tie-break consistently preferred cells with larger $g$g (further along a committed route towards the goal), so the bottom-left region was left unexplored. Dijkstra's algorithm, ranking purely by $g$g, would have had no reason to prefer the goal-ward cells and would have expanded $(1,0)$(1,0) and the whole left/bottom region too. That difference — leaving provably-irrelevant regions unexplored — is the precise sense in which A* expands fewer nodes than Dijkstra's.

Note also that every cell on the discovered path had $f=5$f=5, equal to the true optimal cost. This is no accident: along an optimal path computed with an admissible (here, consistent) heuristic, $f$f stays constant and equal to the optimum, because each unit of $g$g gained is matched by a unit of $h$h lost as you step closer to the goal.

---

Comparison: Dijkstra vs A*

Feature	Dijkstra's	A*
Uses a heuristic?	No	Yes — $h(n)$h(n)
Ranks open vertices by	$g(n)$g(n) (distance from source)	$f(n)=g(n)+h(n)$f(n)=g(n)+h(n) (estimated total)
Direction of exploration	Outwards in all directions equally	Preferentially towards the goal
Optimal path?	Yes (non-negative weights)	Yes (iff $h$h is admissible)
Vertices expanded	More (no goal awareness)	Fewer (guided by $h$h)
When $h(n)=0$h(n)=0	—	Degenerates exactly to Dijkstra's
Worst-case time	$O(V^2)$O(V2) or $O((V+E)\log V)$O((V+E)logV)	Same worst case; far fewer expansions in practice

The key examiner point is that A*'s advantage is practical, not asymptotic: in the worst case (e.g. a useless heuristic, or a maze that thwarts every guess) A* explores as much as Dijkstra's, so the Big-O is the same. The win is that a good heuristic prunes huge swathes of the graph that Dijkstra's would needlessly examine.

---

Admissible vs Consistent Heuristics

Two related-but-distinct properties govern A*'s behaviour, and confusing them is a common slip.

Property	Definition	Effect on A*
Admissible	$h(n)$h(n) never overestimates the true remaining cost: $h(n) \le h^*(n)$h(n)≤h∗(n)	Guarantees A* returns the optimal path
Consistent (monotone)	For every edge $(n, m)$(n,m): $h(n) \le \text{cost}(n, m) + h(m)$h(n)≤cost(n,m)+h(m)	A* never needs to re-open a closed vertex, so it is more efficient

Every consistent heuristic is automatically admissible, but not every admissible heuristic is consistent. Consistency is a "triangle-inequality" condition: the estimate from $n$n must not exceed the cost of stepping to a neighbour $m$m plus the estimate from $m$m. When it holds, the $f$f values encountered along any path never decrease, which is what lets A* finalise a vertex on first extraction and never revisit it (just like Dijkstra's). The Manhattan distance is both admissible and consistent for uniform-cost 4-directional grids, which is why the trace above never had to re-open a closed cell.

---

Applications

Application	Detail
Video-game pathfinding	NPCs navigate around obstacles on a game map; A* is the de-facto standard because it is fast and gives natural-looking routes
Robotics	Mobile robots plan collision-free paths through a mapped physical environment
Route planning	Sat-navs use A* variants (with straight-line distance as the heuristic) for journey planning
Puzzle solving	Sliding puzzles such as the 8-/15-puzzle, using "number of misplaced tiles" or "sum of tile distances" as an admissible heuristic

Exam Tip: A frequent question asks you to explain the difference between Dijkstra and A*, or why A* is more efficient. The full-mark answer is: A* adds a heuristic $h(n)$h(n) that estimates the remaining cost to the goal, so it ranks vertices by $f(n)=g(n)+h(n)$f(n)=g(n)+h(n) and explores towards the goal, expanding fewer vertices; and provided $h$h is admissible (never overestimates) the path it returns is still optimal. State both halves — the efficiency gain and the admissibility condition for optimality — to secure all the marks.

---

Synoptic Links

• Dijkstra's algorithm (4.3.6): A* is Dijkstra's with the open-set key changed from $g$g to $g+h$g+h; setting $h=0$h=0 recovers Dijkstra's exactly. The relaxation, open set and closed set are all inherited.
• Priority queues (4.2.4): the open set is a priority queue keyed on $f$f; efficient extract-min is what keeps A* fast.
• Graphs (4.2.6): A* searches a (often implicit, grid-shaped) weighted graph; the heuristic exploits the geometry of that graph.
• Heuristics & intractability (4.4.4 / 4.3.6): the heuristic here is the same kind of "good-enough estimate" used to attack intractable problems; A* shows a heuristic accelerating an exact search rather than approximating one.
• Complexity (4.4.4): the "same worst-case Big-O, fewer expansions in practice" argument is a direct application of asymptotic-vs-constant-factor reasoning.

---

Common Misconceptions