Dijkstra and A*: what the heuristic buys you

TL;DR:

• Dijkstra's algorithm expands cells in order of cost so far (g). A* orders them by g + h, where h estimates the cost still to go.

• If h never overestimates (admissible), A* finds the same shortest path as Dijkstra but usually expands far fewer cells.

• With h = 0, A* is Dijkstra. A misleading wall can make the saving small.

Two planners can return exactly the same route and yet do very different amounts of work. One looks outward in every direction like a ripple on a pond. The other leans toward the goal. The difference between them is a single added term, and it is worth seeing in numbers.

Dijkstra: the ripple

Dijkstra's algorithm finds the cheapest path from a start to every other cell. At each step it expands the open cell with the lowest g, the cost from the start. Because it always takes the nearest unexpanded cell, the first time it reaches the goal it has found a shortest path.

The cost is that it has no idea where the goal is. It expands every cell at distance 1, then every cell at distance 2, and so on, in a growing circle (a diamond on a 4-connected grid), until the circle touches the goal. That is thorough but wasteful.

A*: the same, with a guide

A* changes one thing: it orders the open cells by f = g + h, where h is a heuristic estimate of the cost from the cell to the goal. Cells that look closer to the goal get expanded first. In the extreme case of h = 0 for every cell, f = g and A* behaves exactly like Dijkstra.

What makes a heuristic safe

A heuristic is admissible if it never overestimates the true remaining cost. Then A* is guaranteed to return a shortest path. It is consistent if, in addition, h(n) ≤ cost(n, n') + h(n') for each step, which means f never decreases along a path, and each cell is expanded at most once.

On a 4-connected grid with unit costs, the Manhattan distance is both. It counts the steps if there were no walls, and walls can only make the real path longer.

Worked example: the same map searched both ways

Here is a 10 by 10 map. S is at the top left (0,0), G at the bottom right (9,9), and a wall stands in column 4 from row 2 to row 7.

S . . . . . . . . .
. . . . . . . . . .
. . . . # . . . . .
. . . . # . . . . .
. . . . # . . . . .
. . . . # . . . . .
. . . . # . . . . .
. . . . # . . . . .
. . . . . . . . . .
. . . . . . . . . G

The Manhattan distance from S to G is 9 + 9 = 18. A shortest path has length 18, because the wall can be passed along row 0 or row 1 (or row 8 or 9) without any detour.

I ran both searches with 4-direction unit moves, breaking ties in A* by the lower h and then by the order in which cells were added. The counts of cells expanded are:

There are 100 − 6 = 94 free cells on this map, so Dijkstra expanded every one of them before taking the goal. A* expanded 19, about a fifth. Both found a path of length 18. The saving is real, and the answer is the same.

The numbers depend on tie-breaking. When many cells tie on f, which one is taken first changes the count a little. With a different tie rule the A* count could be larger, though still well below 94 on this map.

When the heuristic helps less

Move the wall so it sits right in front of the goal, forming a pocket that the robot must enter and leave. The Manhattan guide then leads A* straight into the dead end, because cells inside the pocket look close to the goal. It must expand them all before it backs out and tries another way.

On a smaller 5 by 5 map with such a pocket, I counted 17 expansions for A* and 19 for Dijkstra, a small saving. The lesson is that h is only a guess made without looking at the walls. The better the guess matches the real remaining cost, the more the search is focused.

Heuristics that overestimate

If you multiply h by a number larger than 1 (for example h = 2 × Manhattan), A* becomes greedier: it rushes toward the goal and expands fewer cells, but it can accept a longer path. This is a deliberate trade-off known as weighted A*. It is useful when speed matters more than the best path, and the path is at most the weight times longer than the best one. Be aware that it is no longer guaranteed to find the shortest route.

Where it goes wrong

• Wrong heuristic for the moves. If diagonal moves are allowed, Manhattan distance overestimates. Use the octile or Euclidean distance.

• Non-uniform costs. If some cells are slower to cross, say rough ground, h must still not exceed the cheapest possible cost per step.

• Memory. Both algorithms store the open and closed lists. A huge grid can run out of memory.

• Dynamic obstacles. If the map changes, the old plan may be wrong. Re-plan, or use an incremental variant.

• Counting by wall clock. The number of expansions is a fair measure of effort, but a more complex heuristic can cost more per cell.

Safety: A planner only knows the map it was given. If the map is out of date, a robot following the plan can drive into something. Run a live obstacle sensor and a stop that cannot be overridden by the planner, and test routes at low speed with people clear of the path.

How real robots use them

Navigation stacks use Dijkstra or A* to find a global route across the map, then a local planner follows it and avoids new obstacles. Game engines use A* for characters. Some systems run Dijkstra from the goal once to build a cost-to-go map, and then reuse that for many starts. The first walk-through with open and closed lists is in path planning with A* on a grid.

Try it yourself

Code a grid planner that takes a map, and a flag for the heuristic. Count the number of cells you expand with the flag off and on. Try three maps: an empty one, one with a long wall and one with a pocket in front of the goal. Write down the counts. Then try h doubled, and check whether the path length changes.

Frequently asked questions

Is A* always faster than Dijkstra?

It never expands more cells than Dijkstra for a consistent heuristic (apart from ties), but the saving depends on the map. A misleading wall can make them nearly equal.

What does admissible mean?

It means the heuristic never claims the goal is farther than it really is. Straight-line or Manhattan distance on a grid are admissible, because walls can only lengthen the real path.