A* Search

A* finds a shortest path to a goal by guiding Dijkstra's search with an admissible heuristic that estimates the remaining distance.

Dijkstra with a compass

A* searches for a shortest path from a start to a specific goal. It prioritises each node by f(n) = g(n) + h(n), where g(n) is the known cost from the start and h(n) is a heuristic estimate of the cost from n to the goal. Where Dijkstra expands the nearest node blindly, A* expands the node that looks most promising overall, so it heads toward the goal.

Admissibility and consistency

A* returns an optimal path when the heuristic is admissible: it never overestimates the true remaining cost. A stronger condition, consistency, requires that the estimate obeys a triangle inequality along edges; a consistent heuristic guarantees each node is finalised only once. With h identically zero, A* degenerates exactly into Dijkstra's algorithm.

• f(n) = g(n) + h(n): known cost plus estimated remainder
• Admissible heuristic: never overestimates, guarantees optimality
• Common heuristics: straight-line and Manhattan distance
• Zero heuristic reduces A* to Dijkstra

The trade-off

A better-informed heuristic expands fewer nodes and finds the goal faster, but must stay admissible or the result may be suboptimal. The art of applying A* is designing a heuristic that is as close to the true cost as possible while never exceeding it.

import heapq
def astar(graph, start, goal, h):
    g = {start: 0}
    pq = [(h(start), start)]
    while pq:
        _, u = heapq.heappop(pq)
        if u == goal: return g[u]
        for v, w in graph[u]:
            ng = g[u] + w
            if ng < g.get(v, float('inf')):
                g[v] = ng
                heapq.heappush(pq, (ng + h(v), v))
    return None

Where it is used

A* is the standard pathfinder in games, robotics, and route planning, wherever a goal is fixed and a geometric estimate of remaining distance is cheap to compute. Its focus on the goal makes it far faster than an all-pairs or single-source method when only one destination matters.