A* Search: Heuristics, Admissibility and When It Beats Dijkstra

Dijkstra explores outward evenly in every direction. When you know where the goal is, that's wasteful. A* adds a heuristic estimate of the remaining distance so the search leans toward the target.

The priority

Each node gets f(n) = g(n) + h(n): g is the known cost from the start, and h estimates the cost to the goal. A* always expands the node with the smallest f.

import heapq

def astar(start, goal, neighbors, h):
    g = {start: 0}
    pq = [(h(start), start)]
    while pq:
        f, u = heapq.heappop(pq)
        if u == goal:
            return g[u]
        if f > g[u] + h(u):
            continue                       # stale entry
        for v, w in neighbors(u):
            ng = g[u] + w
            if ng < g.get(v, float("inf")):
                g[v] = ng
                heapq.heappush(pq, (ng + h(v), v))
    return None

Admissible and consistent heuristics

• Admissible: h never overestimates the true remaining cost. That guarantees the first time the goal is popped, its cost is optimal.
• Consistent (monotone): h(u) ≤ w(u, v) + h(v) for every edge. Then nodes never need reopening, and A* behaves like Dijkstra on reweighted edges.

With h = 0, A* is exactly Dijkstra. With a perfect h, it walks straight to the goal.

Grid heuristics

• 4-directional moves: Manhattan distance |dx| + |dy|.
• 8-directional with diagonal cost √2: octile distance.
• Any-angle movement: Euclidean distance.

Using Euclidean distance on a 4-directional grid is still admissible but weaker, so it expands more nodes; using Manhattan on an 8-directional grid overestimates and breaks optimality.

Interview talking points

• Worst case is still exponential in some state spaces; memory (the open set) is usually the limit, and IDA* trades time for memory.
• Weighted A* (f = g + ε·h with ε > 1) finds slightly suboptimal paths much faster, which is common in games and robotics.
• For puzzles like the 8-puzzle, the sum of Manhattan distances of tiles is a classic admissible heuristic.

One-liner: "A* is Dijkstra ordered by g + h; with an admissible, consistent heuristic it stays optimal while exploring far fewer nodes."

Disclosure: from the team behind Linkjob AI interview copilot.