A* Algorithm

Dijkstra's algorithm is thorough but blind: it spreads out from the source in every direction, settling vertices in strict order of distance with no idea where the goal lies. If you only want the route to one destination, that is a lot of wasted exploration. The A* (A-star) algorithm fixes this by giving the search a sense of direction — a heuristic that estimates how far each vertex still is from the goal — so the frontier pushes towards the target instead of bulging out uniformly. A* is the workhorse of game pathfinding, robotics and route planning, and it is examined in OCR H446 section 2.3 right after Dijkstra, because it is Dijkstra with one extra term bolted on.

This lesson builds A* directly on the previous one. You will meet the cost function $f(n) = g(n) + h(n)$ , learn precisely what makes a heuristic admissible and consistent (and why those properties guarantee an optimal answer), trace A* by hand on a small map, and articulate the when and why of choosing A* over Dijkstra. Throughout, remember the dial: set the heuristic to zero and A* collapses back into Dijkstra exactly — the two are the same algorithm seen at two settings.

Spec Mapping

This lesson supports the OCR H446 section 2.3 content on the A* search algorithm and its relationship to Dijkstra's algorithm. Paraphrased, the assessable ideas are:

Understanding A* as a best-first, goal-directed shortest-path search combining actual cost $g(n)$ and a heuristic estimate $h(n)$ through $f(n) = g(n) + h(n)$ .
Explaining the role of the heuristic in steering the search and the meaning of admissibility (never overestimating) and, at a deeper level, consistency.
Tracing A* on a given weighted graph with supplied $g$ and $h$ values, maintaining open and closed sets and selecting the lowest- $f$ vertex each step.
Comparing A* with Dijkstra's — when and why A* is preferable, and the precise sense in which Dijkstra is the special case $h(n) = 0$ .

As ever this is a paraphrase; verify wording against the current OCR H446 specification.

What Is A*?

A* (pronounced "A-star") is a best-first search that finds the cheapest path from a start vertex to a goal vertex. For each vertex $n$ it tracks two quantities:

$g(n)$ — the actual cost of the best path found so far from the start to $n$ (this is the same value Dijkstra would compute).
$h(n)$ — a heuristic estimate of the remaining cost from $n$ onward to the goal.

It then orders its frontier by their sum:

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

so $f(n)$ is the algorithm's estimate of the total cost of the cheapest route that goes through $n$ . At every step A* expands the open vertex with the smallest $f$ . The genius is the split: $g$ keeps the search honest about cost already incurred, while $h$ gives it foresight about cost still to come. Dijkstra effectively uses $f(n) = g(n)$ — it has $g$ but no foresight — which is exactly why it wanders.

To make the intuition concrete, imagine you are walking through an unfamiliar town to a friend's house. Pure Dijkstra is like exploring every street outward from your start in order of how far you have walked, with no map of where the house is — eventually you arrive, but you have wandered down many streets in the wrong direction. A* is like having a compass that points roughly at the house: at each junction you favour the direction that both keeps your total walk short ( $g$ ) and points towards the destination ( $h$ ). You still occasionally backtrack when a promising street turns into a dead end — that is the $g$ term reasserting itself — but on the whole you head purposefully towards the goal. The "compass" is the heuristic, and the quality of your compass determines how much wandering you avoid.

How A* Differs from Dijkstra's

Feature	Dijkstra's	A*
Ordering key	$g(n)$ only	$f(n) = g(n) + h(n)$
Heuristic	None (implicitly $h(n)=0$ )	Uses $h(n)$ to guide search
Search shape	Uniform expanding wavefront	Beam directed at the goal
Goal	Shortest path to all vertices	Shortest path to one goal
Vertices explored	Often many irrelevant ones	Typically far fewer
When $h(n)=0$	—	Becomes Dijkstra's exactly

The single conceptual change is the ordering key. Everything else — the relax-and-update machinery, the priority queue, the predecessor pointers for path reconstruction — is inherited unchanged from Dijkstra. This is genuinely good news for revision: if you have mastered Dijkstra's trace technique you are most of the way to A*, and the few extra marks come from remembering to compute and carry the $h$ and $f$ columns and from being able to discuss the heuristic's properties. Treat A* as "Dijkstra plus a column" rather than as a brand-new algorithm to learn from scratch.

The Heuristic Function $h(n)$

The heuristic is an estimate, not a measurement: it is allowed to be wrong, but how it is wrong determines whether A* still gives a correct answer.

Properties of a good heuristic

Property	Formal condition	Plain meaning
Admissible	$h(n) \le h^*(n)$	Never overestimates the true remaining cost $h^*(n)$ .
Consistent (monotone)	$h(n) \le \text{cost}(n,m) + h(m)$ for every edge $(n,m)$	The estimate never drops by more than the edge actually costs — a "triangle inequality" for the heuristic.
Informative	larger (but still admissible) $h$	Estimates closer to the truth prune more, so the search is faster.

Why admissibility matters

If $h$ is admissible, A* is guaranteed to return an optimal (shortest) path. The intuition: because $h$ never overestimates, $f(n) = g(n) + h(n)$ is never an over-estimate of the best total route through $n$ , so A* will never settle the goal via an inflated estimate while a genuinely cheaper route is still sitting unexplored with a smaller $f$ . Lose admissibility — let $h$ overestimate even once — and A* can be fooled into committing to a suboptimal path because the better one looked more expensive.

Consistency is stronger than admissibility (every consistent heuristic is admissible, but not vice versa). Its practical pay-off is that with a consistent heuristic, the first time A* expands a vertex it already has that vertex's optimal $g$ , so — exactly as in Dijkstra — a vertex never needs to be re-opened from the closed set. This is why a consistent heuristic lets you safely skip closed vertices, whereas a merely admissible one may, in principle, require re-opening them.

Common heuristics

Heuristic	Formula	Best for
Euclidean (straight-line)	$\sqrt{(x_2-x_1)^2 + (y_2-y_1)^2}$	Continuous space, any-angle movement
Manhattan	$\lvert x_2-x_1 \rvert + \lvert y_2-y_1 \rvert$	Grid movement with no diagonals
Zero heuristic	$h(n) = 0$	Always admissible; reduces A* to Dijkstra

Why are straight-line and Manhattan distances admissible? Because a path can never be shorter than the direct geometric distance to the goal, so estimating with that distance can never overestimate. That is the standard recipe for inventing an admissible heuristic: take a relaxed version of the problem (ignore walls, allow diagonal movement, drop a constraint) and use its exact answer as the estimate — relaxing can only make the true cost smaller, so the estimate stays admissible.

Checking a heuristic by hand

Suppose a grid heuristic claims $h(\text{start}) = 9$ but the genuinely cheapest route to the goal costs only $7$ . Then $h(\text{start}) = 9 > 7 = h^*(\text{start})$ , so the heuristic overestimates and is inadmissible — A* using it could return a suboptimal path. To test consistency for an edge, check the triangle-inequality condition directly. Take an edge $(n,m)$ of cost $4$ with $h(n) = 10$ and $h(m) = 5$ . Consistency requires $h(n) \le \text{cost}(n,m) + h(m)$ , i.e. $10 \le 4 + 5 = 9$ . This is false ( $10 > 9$ ), so the heuristic is not consistent across that edge — the estimate dropped by $5$ while the edge only cost $4$ , which is "too steep". A heuristic that passes this check on every edge is consistent, and (because consistency implies admissibility) automatically admissible too. Being able to perform a one-line numeric admissibility or consistency check like this is exactly the kind of AO2/AO3 task an exam can set.

Algorithm Steps and Pseudocode

Create an open set (frontier — vertices discovered but not yet expanded) and a closed set (already expanded). A priority queue keyed on $f$ implements the open set.
Add the start with $g=0$ and $f = h(\text{start})$ .
While the open set is non-empty: a. Pop the vertex $n$ with the lowest $f$ . b. If $n$ is the goal, reconstruct the path from parent pointers and stop. c. Move $n$ to the closed set. d. For each neighbour $m$ : skip if closed; compute tentative $g(m) = g(n) + \text{weight}(n,m)$ ; if this beats $m$ 's current $g$ , update $g(m)$ , $f(m) = g(m) + h(m)$ , set parent $(m)=n$ , and add $m$ to the open set if absent.
If the open set empties without reaching the goal, no path exists.

# OCR-style pseudocode
function aStar(graph, start, goal, heuristic)
    openList = priority queue ordered by f value
    closedList = empty set
    g[start] = 0
    f[start] = heuristic(start, goal)
    parent[start] = null
    openList.add(start)

    while openList is not empty
        current = vertex in openList with lowest f value
        if current == goal then
            return reconstructPath(parent, goal)
        endif

        openList.remove(current)
        closedList.add(current)

        for each neighbour n of current
            if n in closedList then
                continue
            endif
            tentativeG = g[current] + weight(current, n)
            if n not in openList OR tentativeG < g[n] then
                parent[n] = current
                g[n] = tentativeG
                f[n] = g[n] + heuristic(n, goal)
                if n not in openList then
                    openList.add(n)
                endif
            endif
        next n
    endwhile
    return "No path found"
endfunction

Python implementation

import heapq

def a_star(graph, start, goal, h):
    # graph[v] -> list of (neighbour, weight); h(v) -> heuristic to goal
    g = {start: 0}
    parent = {start: None}
    open_heap = [(h(start), start)]   # (f, vertex)
    closed = set()

    while open_heap:
        f_current, current = heapq.heappop(open_heap)
        if current == goal:
            return reconstruct(parent, goal), g[goal]
        if current in closed:
            continue
        closed.add(current)

        for neighbour, weight in graph[current]:
            if neighbour in closed:
                continue
            tentative_g = g[current] + weight
            if neighbour not in g or tentative_g < g[neighbour]:
                g[neighbour] = tentative_g
                parent[neighbour] = current
                f = tentative_g + h(neighbour)
                heapq.heappush(open_heap, (f, neighbour))

    return None, float('inf')          # no path

def reconstruct(parent, goal):
    path = []
    node = goal
    while node is not None:
        path.append(node)
        node = parent[node]
    return path[::-1]                   # reverse: start -> goal

Compare this line-by-line with the Dijkstra implementation from the previous lesson: the only substantive difference is that the heap is keyed on tentative_g + h(neighbour) rather than on new_dist alone. That one change — adding h — is the entire algorithmic content of A*, which is exactly why the two algorithms should be learned together.

Best-first search: the wider family

A* belongs to a family of best-first searches, all of which expand whichever frontier vertex looks most promising according to some scoring function. The family is most easily understood by what each member uses as its score:

Algorithm	Score (ordering key)	Optimal?	Character
Dijkstra / uniform-cost	$g(n)$	Yes	Cautious, no foresight; explores by cost so far
Greedy best-first	$h(n)$	No	Reckless foresight; charges at the goal, ignores cost so far
A*	$g(n) + h(n)$	Yes (admissible $h$ )	Balances the two; the "sweet spot"

Reading the table top to bottom shows A* as the combination of its two neighbours: it borrows Dijkstra's honesty about accumulated cost and greedy search's foresight, while avoiding the failure mode of each (Dijkstra's aimlessness, greedy search's willingness to follow a cheap-looking but ultimately expensive corridor). This is the single most illuminating way to understand A* rather than merely memorise its formula, and it makes the role of each term — the $g$ and the $h$ — impossible to forget.

Worked Example (Fully Traced)

Consider a small map. Vertices are locations; edge weights are travel costs; we want the cheapest route from S to G.

flowchart LR
    S((S)) -- "1" --- A((A))
    S -- "4" --- B((B))
    A -- "2" --- B
    A -- "5" --- C((C))
    B -- "3" --- G((G))
    C -- "1" --- G

Heuristic values (an admissible straight-line estimate of the remaining cost to G):

$h(S)=7,\quad h(A)=6,\quad h(B)=2,\quad h(C)=1,\quad h(G)=0$

We expand the lowest- $f$ open vertex each step. Where two share the lowest $f$ we tie-break alphabetically.

Step	Expanded	$g$	$f=g+h$	Open set after (vertex: $f$ )	Closed set
Init	—	—	—	{S: 7}	{}
1	S	0	7	{B: 6, A: 7}	{S}
2	B	4	6	{A: 7, G: 7}	{S, B}
3	A	1	7	{G: 7, C: 7}	{S, A, B}
4	G	7	7	(goal reached)	{S, A, B, G}

Step-by-step reasoning

Step 1 — expand S ( $g=0$ ). Neighbours: A via $g=1$ , $f=1+6=7$ ; B via $g=4$ , $f=4+2=6$ . Both added; B has the smaller $f$ .
Step 2 — expand B ( $g=4$ , lowest $f=6$ ). Neighbour G via $g=4+3=7$ , $f=7+0=7$ . (A→B relaxation: B already has $g=4$ from S directly; the route S→A→B would give $g=1+2=3$ — but A has not been expanded yet, so we have not discovered that improvement at this point.) Add G: 7.
Step 3 — expand A ( $g=1$ , $f=7$ , alphabetical tie-break over G). Neighbour C via $g=1+5=6$ , $f=6+1=7$ . Neighbour B is already closed, so it is skipped. Add C: 7.
Step 4 — expand G ( $f=7$ , tie-break over C). Goal reached. Reconstruct via parent pointers: G's parent is B, B's parent is S → path S → B → G, cost $4+3=7$ .

A* Algorithm

A* Algorithm

Spec Mapping

What Is A*?

How A* Differs from Dijkstra's

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

Properties of a good heuristic

Why admissibility matters

Common heuristics

Checking a heuristic by hand

Algorithm Steps and Pseudocode

Python implementation

Best-first search: the wider family

Worked Example (Fully Traced)

Step-by-step reasoning

More in Computer Science

The Heuristic Function $h(n)$