Graph AlgosAlgorithmaka A-star, best-first search with admissible heuristic

A* Search

Point-to-point shortest path that steers Dijkstra toward the goal with a heuristic h(v): pop by f = g + h; optimal when h never overestimates.

▶ VisualizePattern: Heap / Priority QueuePractice (1)
Progress

Overview

A* finds a shortest path from a source to a specific target. It is Dijkstra's Algorithm with one change: the Priority Queue is ordered by f(v) = g(v) + h(v), where g(v) is the best known cost from the source and h(v) is a heuristic estimate of the remaining cost to the goal. A good heuristic makes the search expand nodes roughly along the straight line to the goal instead of in every direction.

Preconditions: non-negative edge weights, a single target, and a heuristic that is admissible (h(v) ≤ true remaining cost for all v) — then the first time the goal is popped its g is optimal. If h is additionally consistent (h(u) ≤ w(u, v) + h(v) for every edge, a triangle inequality), each node is settled once, exactly like Dijkstra, and the stale-entry skip is enough. With h ≡ 0 A* is exactly Dijkstra; worst-case complexity is the same O((V + E) log V), but the explored region is usually far smaller.

shortest pathheuristicinformed searchpathfindingadmissibleconsistent

Intuition

A mental model before the formal terms.

Finding a route on a map, you would not explore roads leading away from your destination just because they are close to you. A* keeps Dijkstra's "cheapest so far" accounting (g) but adds "roughly how far is it still?" (h, e.g. straight-line distance) and always continues from the node whose total looks best. As long as the guess never claims a route is longer than it really is, it can never fool you into skipping the true shortest path.

How it works

  1. Set g[s] = 0, push (f = h(s), s) into a min-heap.
  2. Pop the entry with the smallest f. If it is the goal, stop: g[goal] is the answer. If the popped g is stale (larger than the stored g[u]), skip.
  3. For each edge u → v with weight w: if g[u] + w < g[v], set g[v] = g[u] + w, parent[v] = u, and push (g[v] + h(v), v).
  4. Heuristics for grids: Manhattan distance |dr| + |dc| for 4-directional moves, Chebyshev max(|dr|, |dc|) for 8-directional unit moves, Euclidean for continuous movement. All are admissible and consistent because they are exact distances on an obstacle-free grid, and obstacles can only lengthen paths.
  5. Weighted A* uses f = g + ε·h with ε > 1: faster, but the result may be up to ε times longer than optimal — a deliberate trade, not a bug.

Why it works

Admissibility ⇒ optimality of the first goal pop: suppose the goal is popped with cost C > C* (the optimum). Some node y on an optimal path is in the open set with g(y) = g*(y), so f(y) = g*(y) + h(y) ≤ g*(y) + h*(y) = C* < C. Then y would have been popped before the goal. Contradiction.

Consistency ⇒ f is non-decreasing along any path: f(v) = g(u) + w + h(v) ≥ g(u) + h(u) = f(u). So nodes are popped in non-decreasing f order and each node's first pop already has optimal g — identical to Dijkstra's argument. Without consistency (only admissibility) a closed node can be rediscovered with a better g and must be reopened; the lazy stale-check version handles this automatically because it never permanently closes nodes.

A* is optimally efficient: among algorithms using the same consistent h, no other one expands fewer nodes and still guarantees optimality.

Recognition

How to tell a problem wants this.

  • One source, one target, and a cheap lower-bound estimate of distance exists (geometry, coordinates, Manhattan distance).
  • Pathfinding on large grids or maps where Dijkstra explores too much (game AI, robotics, routing).
  • Puzzle solving with a state space and a lower-bound cost (15-puzzle with Manhattan tile distance).
“k most frequent” → Heap / Priority Queue“weighted graph” → Shortest Path (Weighted)

Interactive visualization

Play, step, change the input. ← → and space work too.

11
#
#
#
#
#
#
#
#
#
#
#
#
#
Open set (by f = g + h)
cellghf
(0,0)01111
1/54Start at (0,0), target (4,7). h = Manhattan distance to the target — it never overestimates on a 4-connected grid, so A* with this heuristic still finds an optimal path while expanding far fewer cells than plain BFS.
StartTargetWallOpen set (cell shows f)Expanding nowClosedFinal path
PseudocodeLearn A* Search →
1g[start] = 0; open = {start with f = h(start)}
2while open not empty:
3  u = cell in open with smallest f = g + h
4  if u == target: reconstruct path and stop
5  closed.add(u)
6  for v in 4-neighbors(u) not wall, not closed:
7    if g[u] + 1 < g[v]:
8      g[v] = g[u] + 1; parent[v] = u; f[v] = g[v] + h(v); open.add(v)
9open empty → no path
Variables
h11
Complexity
best O(L log L)
avg depends on heuristic
worst O((V + E) log V)
space O(V)
Speed

Pseudocode

1g = {v: INF}; g[s] = 0; heap = [(h(s), s)]
2while heap not empty:
3  f, u = heap.pop_min(); if u == goal: return g[u]
4  if f - h(u) > g[u]: continue      # stale
5  for (v, w) in adj[u]:
6    if g[u] + w < g[v]:
7      g[v] = g[u] + w; parent[v] = u
8      heap.push((g[v] + h(v), v))

Implementations

1import heapq
2import math
3from typing import Callable
4 
5 
6def astar(
7    adj: list[list[tuple[int, float]]],
8    start: int,
9    goal: int,
10    h: Callable[[int], float],
11) -> tuple[float, list[int]]:
12    """A*: Dijkstra plus a heuristic. The frontier is ordered by f = g + h,
13    where g is the cost already paid and h estimates the cost remaining. An
14    admissible h means the first pop of the goal is optimal. Returns
15    (cost, path); cost is -1 and path is empty when the goal is unreachable."""
16    n = len(adj)
17 
181 · g[v] is the best cost found so far from start to v
19    g: list[float] = [math.inf] * n
20    parent = [-1] * n
21    closed = [False] * n
22 
23    g[start] = 0
24    open_heap: list[tuple[float, int]] = [(h(start), start)]
25 
26    while open_heap:
272 · Expand the node with the smallest f; closed nodes are already final
28        _, u = heapq.heappop(open_heap)
29        if closed[u]:
30            continue
31        closed[u] = True
32 
333 · With an admissible heuristic, popping the goal ends the search
34        if u == goal:
35            path = []
36            at = goal
37            while at != -1:
38                path.append(at)
39                at = parent[at]
40            return g[goal], path[::-1]
41 
424 · Relax like Dijkstra, but order the frontier by g + h, not g
43        for v, w in adj[u]:
44            if closed[v]:
45                continue
46            if g[u] + w < g[v]:
47                g[v] = g[u] + w
48                parent[v] = u
49                heapq.heappush(open_heap, (g[v] + h(v), v))
50 
51    return -1, []
52 
53 
545 · A consistent heuristic for a grid: Manhattan distance with unit steps
55def manhattan(width: int, goal_index: int) -> Callable[[int], float]:
56    gx, gy = goal_index % width, goal_index // width
57 
58    def h(v: int) -> float:
59        return abs(v % width - gx) + abs(v // width - gy)
60 
61    return h
Walkthrough
  1. heapq provides the open set directly; entries are (f, vertex) tuples ordered lexicographically by f.
  2. _, u = heapq.heappop(open_heap) discards the stale f — g[u] is the authoritative cost.
  3. closed[u] implements lazy deletion, so no decrease-key operation is needed.
  4. The goal test is on pop rather than on discovery, which is what preserves optimality.
  5. manhattan returns a nested function closing over gx/gy; v // width is integer division for the row, matching the % width column.
Complexity (this implementation)
time O(E log V) worst case; far less in practice, depending entirely on how well h guides the search · space O(V) for the lists, O(E) worst case for the open set

The heuristic is a Python-level call per push, which on a large grid can rival the heap operations in cost — caching it into a list is a common optimisation.

Language notes
  • heapq is a min-heap, which is what A* wants with no comparator inversion.
  • // is floor division and / is float division; the grid heuristic needs // for the row and would silently break with /.
  • networkx.astar_path implements this directly and takes the heuristic as a two-argument callable (u, v).
  • Tuple comparison falls through to the second element on an f tie, so pushing a non-comparable payload as a third element would raise TypeError.
Common mistakes in this language
  • Using / instead of // for the row index, producing a float coordinate and an incorrect heuristic.
  • Returning as soon as the goal is *discovered* rather than *popped*, which sacrifices optimality for no real speed gain.
  • Pushing (f, vertex, path_list) and hitting TypeError when two entries tie on both f and vertex.
Language differences that matter here
  • A* is Dijkstra plus one term, so it inherits the same split: heapq and std::priority_queue supply the open set, while JS/TS ship an inline binary heap for the third time.
  • Grid index arithmetic exposes the division difference — Python needs //, JS/TS need Math.floor, and C++ / on int already truncates.
  • Passing the heuristic: C++ pays an indirect call through std::function (or inlines it via a template), while JS/TS/Python pass a closure with a real call per push.
  • Library A* exists only in Python (networkx.astar_path) and, with a dependency, C++ (Boost.Graph astar_search); JS/TS have neither.

Complexity

Best
O(L log L)
Average
depends on heuristic
Worst
O((V + E) log V)
Space
O(V)

Best case: a perfect heuristic expands only the L nodes on the optimal path. Worst case (h ≡ 0 or misleading h): identical to Dijkstra. Memory is the practical limit — the open set can hold most of the graph.

Compare growth rates in the Complexity Explorer →

When to use — and when not to

Use it when
  • Single-target shortest path on a large graph with a natural distance lower bound (grids, maps, coordinates).
  • Real-time pathfinding where Dijkstra explores too much of the map.
  • State-space search with a cheap admissible bound (puzzles, planning).
Avoid it when
  • No meaningful heuristic — then it is Dijkstra with extra function calls.
  • Distances to all nodes are needed — the heuristic only helps for one target; use Dijkstra's Algorithm.
  • Negative edges — same failure as Dijkstra; use Bellman-Ford.
  • Memory-constrained huge searches — the open set can explode; consider IDA* (iterative deepening A*).

Alternatives

Dijkstra's AlgorithmBFS Shortest Path (Unweighted)0-1 BFS

Common mistakes

  • Using an inadmissible heuristic (e.g. Euclidean distance × 2, or Manhattan on a grid that allows diagonal moves) — the returned path may not be optimal.
  • Closing nodes permanently on first pop with an admissible-but-inconsistent heuristic — they may need reopening. The lazy stale-check version avoids the issue.
  • Checking for the goal when a node is pushed rather than popped — the first push is not guaranteed optimal.
  • Heuristic that ignores obstacles is fine; a heuristic that ignores edge weights while edges cost less than 1 per unit distance is not (it overestimates).
  • Floating-point ties: comparing f - h(u) > g[u] with rounding errors; use an epsilon or store g in the heap entry instead.

Interview patterns

  • Grid pathfinding with Manhattan heuristic — usually as a follow-up to a BFS solution ("how would you speed this up for a huge map?").
  • Sliding puzzle / 8-puzzle with sum-of-Manhattan-tile-distances heuristic.
  • Explain admissible vs consistent and why Dijkstra is A* with h = 0.
  • Tie-breaking on larger g (prefer deeper nodes) to reduce expansions when many paths tie.
Interview questions on this
Mock interviews

Example problems

Shortest Path in Binary Matrixmedium