A* Search: Dijkstra With a Sense of Direction

Introduction

A* is a shortest-path algorithm that adds one piece of information to Dijkstra's: an estimate of how far each node is from the goal. Dijkstra expands nodes in order of the cost to reach them, which means it grows outward evenly in every direction until it happens to touch the goal. A* expands nodes in order of the cost to reach them plus the estimated cost remaining, so the search leans toward the goal and leaves most of the graph untouched.

The estimate is called the heuristic, and nearly everything interesting about A* is a property of it. A good heuristic cuts the work by an order of magnitude and still returns the optimal path. A heuristic that overestimates returns a path faster but gives up the guarantee that it is the shortest one. A heuristic of zero turns A* back into Dijkstra. On the grid measured below, Dijkstra expanded 31,864 cells to cross it; A* with a Manhattan-distance heuristic expanded 3,105 and returned a path of identical cost.

This post builds A* on top of the Dijkstra implementation from the graph algorithms post, measures what the heuristic buys, covers the two rules a heuristic has to follow, and shows where trading optimality for speed is the right call. The priority queue underneath is the same binary heapHeap propertyIn a min-heap every parent's key is less than or equal to its children's keys, so the smallest item is always at the root.Read more from the post on heaps for event-driven systems.

The Problem Dijkstra Leaves on the Table

Dijkstra's algorithm keeps a frontier of nodes ordered by g, the cheapest known cost from the start. It always expands the node with the smallest g. That ordering is what makes it correct, and it is also what makes it wasteful when you have a single goal: a node one step behind the start has the same g as a node one step toward the goal, so both get expanded with equal enthusiasm.

On a small grid with the start in one corner and the goal in the opposite one, the difference is visible. Both searches below ran on the same map with the code from this post:

Use the zoom buttons, or focus the diagram and press plus or minus to zoom, arrow keys to pan, and 0 to reset.

Dijkstra fills the whole map because nothing in its ordering points anywhere. A* expands almost nothing off its own path, because every cell that leads away from G scores worse than one that leads toward it. Both find the same cost; the difference is how much of the map they had to read to be sure.

Adding the Heuristic

A* changes one line of Dijkstra. Instead of ordering the frontier by g, it orders by

where g(n) is the known cost from the start to n and h(n) is the heuristic's estimate of the cost from n to the goal. The node with the smallest f is the one whose best possible complete path looks cheapest, so A* expands that one next.

The heuristic has to come from something you know about the problem that the graph's edges do not tell you. On a grid where you move one cell at a time up, down, left, or right, the cost to reach the goal can never be less than the number of rows plus the number of columns between you and it. That is the Manhattan distance, |dx| + |dy|, and it is the standard heuristic for 4-connected grids. On a road network, straight-line distance divided by the highest speed limit plays the same role. In both cases the estimate is cheap to compute and never larger than the true remaining cost.

Running both algorithms on a 200×200 grid with 20% of cells randomly walled, 4-connected with unit step cost, start at the top-left, goal at the bottom-right:

Manhattan distance cuts the work by a factor of ten and the path cost is unchanged. Euclidean distance, the straight-line estimate, is also correct but barely helps: on a grid where diagonal moves are not allowed, the straight line underestimates the real distance by up to 30%, and a heuristic that underestimates by that much carries little information. The closer h is to the true remaining cost without exceeding it, the fewer nodes A* expands.

A* in TypeScript

The whole algorithm is one loop around the priority queue. Every node that leaves the queue is either a stale duplicate, the goal, or a node whose neighbors get scored and pushed:

Expand a nodeSkip a stale copyGoal foundNo pathAll routes

The common case, and most of what A* does. The node at the top of the heap is new and is not the goal, so A* scores the node's neighbors and pushes every neighbor A* found a cheaper route to.

A node can sit in the heap more than once, because finding a cheaper route pushes a fresh copy instead of updating the old one. When the old, more expensive copy reaches the top, the node is already closed, so A* throws the copy away.

The node popped is the goal. A* checks for the goal when a node comes off the heap, not when the node is first pushed, and that check on pop is what makes the answer optimal: nothing cheaper can still be waiting.

Every reachable node has been expanded and the heap is empty, so there is no path. A* can only conclude no path exists after visiting every node A* can reach, the same work Dijkstra does.

Every route at once: one dot leaves the start and splits wherever the routes go different ways.

1

Push the start node. Nothing has been paid yet, so the start node's f is just the estimate h(start).

Pop the node with the smallest f: the one whose complete path currently looks cheapest.

The node has not been closed before, so this is the cheapest way to reach the node. Close the node.

The node is not the goal, so the search goes on from this node.

For each neighbor, compute the tentative cost g′ = g + cost: the cost so far plus the step to that neighbor. g′ is only a candidate until compared.

Where g′ beats the neighbor's best known g, g′ becomes the neighbor's new g: record this node as the neighbor's parent and push the neighbor with f = g′ + h.

Back to the heap for the next most promising node.

Push the start node.

Pop the node with the smallest f.

This node was closed earlier through a cheaper copy, so this heap entry is out of date. Skip the entry without expanding anything.

Pop again. Skipping cost one heap pop and pushed nothing.

Push the start node.

Pop the node with the smallest f.

Not closed before. Close the node.

The node is the goal. Every path still in the heap has an f at least this large, so no path in the heap can beat this one.

Follow the parent pointers from the goal back to the start to get the path.

Push the start node.

Try to pop, but the heap is empty: nothing reachable is left to explore.

Return no path (null).

All 7 steps

1. 1.Push the start node. Nothing has been paid yet, so the start node's f is just the estimate h(start).
2. 2.Pop the node with the smallest f: the one whose complete path currently looks cheapest.
3. 3.The node has not been closed before, so this is the cheapest way to reach the node. Close the node.
4. 4.The node is not the goal, so the search goes on from this node.
5. 5.For each neighbor, compute the tentative cost g′ = g + cost: the cost so far plus the step to that neighbor. g′ is only a candidate until compared.
6. 6.Where g′ beats the neighbor's best known g, g′ becomes the neighbor's new g: record this node as the neighbor's parent and push the neighbor with f = g′ + h.
7. 7.Back to the heap for the next most promising node.

1. 1.Push the start node.
2. 2.Pop the node with the smallest f.
3. 3.This node was closed earlier through a cheaper copy, so this heap entry is out of date. Skip the entry without expanding anything.
4. 4.Pop again. Skipping cost one heap pop and pushed nothing.

1. 1.Push the start node.
2. 2.Pop the node with the smallest f.
3. 3.Not closed before. Close the node.
4. 4.The node is the goal. Every path still in the heap has an f at least this large, so no path in the heap can beat this one.
5. 5.Follow the parent pointers from the goal back to the start to get the path.

1. 1.Push the start node.
2. 2.Try to pop, but the heap is empty: nothing reachable is left to explore.
3. 3.Return no path (null).

• Expand a node · expand a node, push its neighborsStep through
• Skip a stale copy · pop a stale duplicate, skip itStep through
• Goal found · pop the goal, return the pathStep through
• No path · heap runs dry, no pathStep through

Use the zoom buttons, or focus the diagram and press plus or minus to zoom, arrow keys to pan, and 0 to reset.

This version is generic over the node type, so the same function searches a grid, a road graph, or a state space like a puzzle. The caller describes the problem; the algorithm does not know what a node is.

1export interface SearchProblem<N> {2  start: N;3  isGoal(node: N): boolean;4  neighbors(node: N): Iterable<[next: N, cost: number]>;5  heuristic(node: N): number;6  key(node: N): string | number;7}8 9export interface SearchResult<N> {10  path: N[];11  cost: number;12  expanded: number;13}14 15class MinHeap<T> {16  private items: { f: number; h: number; value: T }[] = [];17 18  get size(): number {19    return this.items.length;20  }21 22  // Order by f, and break ties toward the smaller h (the node nearer the goal).23  private less(a: number, b: number): boolean {24    const x = this.items[a], y = this.items[b];25    return x.f < y.f || (x.f === y.f && x.h < y.h);26  }27 28  push(value: T, f: number, h: number): void {29    const items = this.items;30    items.push({ f, h, value });31    let i = items.length - 1;32    while (i > 0) {33      const parent = (i - 1) >> 1;34      if (!this.less(i, parent)) break;35      [items[parent], items[i]] = [items[i], items[parent]];36      i = parent;37    }38  }39 40  pop(): T | undefined {41    const items = this.items;42    if (items.length === 0) return undefined;43    const top = items[0].value;44    const last = items.pop()!;45    if (items.length > 0) {46      items[0] = last;47      let i = 0;48      for (;;) {49        const l = 2 * i + 1;50        const r = l + 1;51        let min = i;52        if (l < items.length && this.less(l, min)) min = l;53        if (r < items.length && this.less(r, min)) min = r;54        if (min === i) break;55        [items[min], items[i]] = [items[i], items[min]];56        i = min;57      }58    }59    return top;60  }61}62 63export function aStar<N>(problem: SearchProblem<N>): SearchResult<N> | null {64  const { start, key } = problem;65  const g = new Map<string | number, number>([[key(start), 0]]);66  const parent = new Map<string | number, N>();67  const closed = new Set<string | number>();68  const open = new MinHeap<N>();69  const h0 = problem.heuristic(start);70  open.push(start, h0, h0);71  let expanded = 0;72 73  while (open.size > 0) {74    const node = open.pop()!;75    const k = key(node);376    // Lazy deletion: a node can sit in the heap more than once.77    if (closed.has(k)) continue;178    closed.add(k);79    expanded++;80 81    if (problem.isGoal(node)) {282      const path = [node];83      let cur = node;84      while (parent.has(key(cur))) {85        cur = parent.get(key(cur))!;86        path.push(cur);87      }88      return { path: path.reverse(), cost: g.get(k)!, expanded };89    }90 91    const gNode = g.get(k)!;92    for (const [next, cost] of problem.neighbors(node)) {93      const nk = key(next);94      if (closed.has(nk)) continue;95      const tentative = gNode + cost;96      if (tentative < (g.get(nk) ?? Infinity)) {97        g.set(nk, tentative);98        parent.set(nk, node);99        const h = problem.heuristic(next);100        open.push(next, tentative + h, h);101      }102    }103  }104  return null;105}

Three details carry the correctness. The heap uses lazy deletion 1: when a cheaper route to a node is found, the node is pushed again rather than updated in place, and the stale copy is skipped when it surfaces because the node is already closed. That keeps the heap a plain binary heap with no decrease-key operation. The goal check happens when a node is popped, not when it is first discovered 2; checking on discovery returns the first path that touches the goal, which is not necessarily the cheapest one. And the key function 3 lets nodes be objects while the bookkeeping maps use a primitive, so two different object instances describing the same grid cell count as the same node.

Checked against Dijkstra on 200 random grids at 30% walls, this implementation returned the same cost on every one, agreed on every unreachable goal, and produced paths whose every step was a legal move into an open cell.

Breaking Ties Toward the Goal

The comparison function in the heap has a second clause: when two nodes have the same f, prefer the one with the smaller h. It looks like a cosmetic detail. It is the difference between the two rows here, on the same 200×200 grids with the Manhattan heuristic:

The effect shows up even on a small open grid:

Use the zoom buttons, or focus the diagram and press plus or minus to zoom, arrow keys to pan, and 0 to reset.

On an open grid, every cell inside the rectangle between S and G has exactly the same f under Manhattan distance: any step right or down lowers h by exactly as much as it raises g. With tens of thousands of nodes tied for the lowest f, the heap picks among them arbitrarily, and arbitrary means it wanders through most of the rectangle. Breaking ties toward smaller h means that among equally promising nodes, A* always extends the one that has gotten furthest, and on the open grid it walks straight to the goal expanding only the 399 cells on the path.

Ties are rare on graphs with irregular real-valued weights, like road networks. They are everywhere on grids and in puzzle state spaces with unit costs, which are exactly the places A* gets used most.

The Two Rules for a Heuristic

A heuristic can be any function from a node to a number, but only two kinds keep A*'s guarantees.

Admissible means the heuristic never overestimates: h(n) is less than or equal to the true cheapest cost from n to the goal, for every n. An admissible heuristic guarantees that A* returns an optimal path. The reasoning is short: if h never overestimates, then f(n) never overestimates the cost of the best path through n, so A* cannot pop the goal through an expensive route while a cheaper one is still waiting in the frontier with a smaller f.

Consistent is the stronger property: for every edge from n to m with cost c, h(n) ≤ c + h(m). In words, the estimate can never drop by more than the cost of the step that moved you. A consistent heuristic guarantees that the first time a node is popped, it has been reached by its cheapest path, so a closed node never needs reopening. The implementation above depends on that: it skips closed neighbors outright. Every consistent heuristic is admissible; Manhattan distance on a 4-connected grid and straight-line distance on a road map are both consistent.

The rule is easy to break by changing the problem without changing the heuristic. Allow diagonal moves at cost √2, keep the Manhattan heuristic, and it now overestimates, because one diagonal step reduces Manhattan distance by 2 while costing only 1.41:

On a 200×200 grid with 20% walls and diagonal moves allowed:

Trading Optimality for Speed

Sometimes the 3.3% longer path is a good trade. Weighted A* makes the trade deliberately: it multiplies an admissible heuristicAdmissible heuristicA heuristic that never overestimates the true cheapest cost to the goal, which guarantees A* returns an optimal path.Read more by a weight w greater than 1, so f = g + w × h. The search becomes greedier, expanding far fewer nodes, and the result comes with a bound: the path found costs at most w times the optimal one.

Averaged over the 43 solvable grids among 50 random 200×200 maps at 20% walls, Manhattan heuristic:

A weight of 1.5 expanded 4.4 times fewer cells and returned paths 9.5% longer on average, comfortably inside the guaranteed 50%. Going to 3.0 bought very little additional speed for a noticeably worse path; most of the savings arrive with the first small increase in weight. That curve is typical, and it means the useful weights are usually between 1.1 and 2.

This is the right trade when the path is recomputed often and a slightly worse answer now beats a perfect one later: units in a game re-planning every few frames, a robot that re-plans as its sensors update, or a route suggestion that will be refined once the user starts moving. It is the wrong trade when the path is computed once and executed many times, like a delivery route or a network route table, where every percent of extra cost is paid on every trip.

Where A* Shows Up Outside Games

Grid pathfinding is the textbook example, but A* applies to any search with a single goal and a meaningful estimate of distance to it.

• Routing and maps. Turn-by-turn navigation runs A* or a descendant of it over the road graph, with straight-line distance divided by maximum speed as the heuristic. Production systems add precomputed shortcuts on top, but the core ordering is the same.
• Puzzle and planning solvers. The 15-puzzle, warehouse robot planning, and job-shop scheduling all search a state space where each state is a node. The heuristic is a relaxed version of the problem: for the 15-puzzle, the sum of each tile's Manhattan distance to its home square.
• Diff and alignment. Computing an edit script between two sequences is a shortest path through an edit graph, and A*-style search with a lower bound on remaining edits is one way diff tools avoid exploring the whole grid.
• Network and query planning. Choosing a route through a service graph, or a join order through a space of query plans, is a cost-minimizing search where a cheap lower bound on remaining cost prunes most candidates.

The pattern in each: the graph is too large to explore completely, the search has one target, and there is a quick way to compute a number that never exceeds the real distance to it.

When You Do Not Need It

A* is Dijkstra plus an estimate, so it only helps when there is an estimate worth having.

• You need distances to every node. Building a routing table or computing a shortest-path tree from one source wants all destinations, and A* is built around one. Run Dijkstra.
• There is no good heuristic. If the best admissible estimate you can find is zero or near it, A* does Dijkstra's work plus the cost of computing h. The Euclidean row above is that case in miniature: 30,312 expansions instead of 31,864, and slower in wall-clock time.
• The goal may be unreachable. A* cannot prove there is no path until it has exhausted every reachable node, so on an unsolvable map it does all of Dijkstra's work. In the measured case, walling off the goal turned a 1.8ms search into a 26.5ms one that returned null. If unreachable goals are common, check connectivity first with a cheap breadth-first search or a precomputed component label.
• The graph is small. Under a few thousand nodes, Dijkstra's full expansion takes well under a millisecond, and the heuristic is one more function to keep correct as the problem changes.

Conclusion

A* is Dijkstra with a single change to the priority: expand the node whose cost so far plus estimated cost remaining is smallest. That change cut the work on a 200×200 grid tenfold with an identical result, and the result stays optimal as long as the heuristic never overestimates. The work that remains is all in the heuristic: derive it from the movement rules, re-derive it when they change, break ties toward the goal, and decide deliberately whether a bounded, slightly longer path is worth a fourfold speedup. A heuristic that guesses wrong never raises an error, so the measurement against plain Dijkstra on known maps is the only test that catches it.

Key Takeaways

• A* orders its frontier by f = g + h, the known cost so far plus an estimate of the cost remaining, which steers the search toward the goal.
• With a Manhattan heuristic on a 200×200 grid, A* expanded 3,105 cells against Dijkstra's 31,864 and returned a path of identical cost.
• An admissible heuristic never overestimates and guarantees an optimal path; a consistent one also guarantees no node needs reopening.
• Breaking f ties toward smaller h cut expansions on an open grid from 26,614 to 399; on unit-cost grids it is not optional.
• Keeping Manhattan distance after allowing diagonal moves cut expansions 18× and made the path silently 3.3% longer; octile distance is the admissible replacement.
• Weighted A* with w = 1.5 expanded 4.4× fewer cells for paths 9.5% longer on average, always within the guaranteed factor of w.