cf.completefrontend
GRAPHS · ADVANCED

A* search

Find a shortest path to one goal faster than Dijkstra by also using a guess of how far each node still is from the goal.

Time O(c log c)Space O(c)2 practice problemsStep-through picture

The idea

Dijkstra's algorithm spreads out evenly in every direction, even away from the goal. When you know where the goal is, you can do better. A* (said "A star") picks the next node by f = g + h, where g is the real cost from the start so far and h is a guess of the cost still left to the goal.

The guess is called a heuristic. On a grid where you move up, down, left, or right one cell at a time, a good guess is the Manhattan distance: the number of rows plus the number of columns between a cell and the goal. It is never more than the real remaining cost, because walls can only make the trip longer.

When the guess never overestimates, A* still finds a shortest path, but it heads toward the goal and leaves most of the map unexplored. With h = 0 everywhere, A* becomes Dijkstra's algorithm.

An everyday example

Walking to a tall tower you can see

You're walking through a city toward a tall tower you can see above the rooftops. At each corner you prefer the street that has been short so far and also points toward the tower. You don't wander down streets that lead away from it unless the direct ones are blocked. You might still need a detour around a park, but you rarely explore the wrong side of town.

How the example maps to the code
In the exampleIn the code
How far you've walkedg
How far the tower looks from hereh(r, c), the Manhattan distance
The corner that looks most promisingThe heap entry with the smallest f = g + h
A blocked streetA wall cell "#"
Reaching the towerr === goal[0] && c === goal[1]

From the slow way to a* search

  1. Start with what Dijkstra's algorithm, or BFS on a grid, does: it grows a diamond of explored cells around the start, the same size in every direction. To reach a goal 100 cells to the east on an open map, it explores every cell within 100 steps, about 20,000 cells, even though the path itself has only 100.
  2. But we know where the goal is. For any cell we can compute a guess of the remaining distance that is never too high: the Manhattan distance, rows apart plus columns apart, because each move changes one of them by 1 and walls only make things longer. So the cheapest complete path through a cell costs at least g + h, where g is the real cost so far.
  3. Pick the next cell by that lower bound instead of by g alone. Cells in the direction of the goal keep the same f = g + h as the start, because each step adds 1 to g and takes 1 off h. Cells behind the start gain 2 in f per step, so they wait until the cheap options run out.
  4. The rest is Dijkstra's machinery: a min-heap ordered by f, a best table of the cheapest known g per cell, outdated entries skipped, and a stop when the goal comes out of the heap, not when it goes in. That loop is A* search.

How it works

  1. Define h(r, c), the Manhattan distance from a cell to goal.
  2. Make best, the cheapest known g for every cell, all Infinity except the start at 0.
  3. Push the start into the open heap as [f, g, r, c] with g = 0 and f = h(start).
  4. Pop the entry with the smallest f. If it is the goal, return its g: that is the shortest path length.
  5. If g is bigger than best[r][c], it is an old entry: skip it.
  6. For each open neighbor, if g + 1 beats its best, store it and push [g + 1 + h(nr, nc), g + 1, nr, nc].
  7. If the heap runs out, the goal can't be reached: return -1.

Watch it run

This picture runs the code below on a real input. Press Step to move one step at a time, or Play to watch. The highlighted line is the one that just ran. Change the input to see other cases.

Loading the picture…
See every step at onceThe same run, laid out side by side
Drawing every step…

The code

Point at a note to light up the lines it explains.

JavaScriptOpen in the code editor (opens in a new tab)
  1. function aStar(grid, start, goal) {
  2. const rows = grid.length;
  3. const cols = grid[0].length;
  4. const h = (r, c) => Math.abs(r - goal[0]) + Math.abs(c - goal[1]);
  5. const best = Array.from({ length: rows }, () => new Array(cols).fill(Infinity));
  6. best[start[0]][start[1]] = 0;
  7. const open = [[h(start[0], start[1]), 0, start[0], start[1]]];
  8. while (open.length > 0) {
  9. const [, g, r, c] = pop(open);
  10. if (r === goal[0] && c === goal[1]) return g;
  11. if (g > best[r][c]) continue;
  12. for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
  13. const nr = r + dr;
  14. const nc = c + dc;
  15. if (nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] === "#") continue;
  16. if (g + 1 >= best[nr][nc]) continue;
  17. best[nr][nc] = g + 1;
  18. push(open, [g + 1 + h(nr, nc), g + 1, nr, nc]);
  19. }
  20. }
  21. return -1;
  22. }
  24. function push(heap, item) {
  25. heap.push(item);
  26. let i = heap.length - 1;
  27. while (i > 0 && heap[(i - 1) >> 1][0] > heap[i][0]) {
  28. const parent = (i - 1) >> 1;
  29. [heap[parent], heap[i]] = [heap[i], heap[parent]];
  30. i = parent;
  31. }
  32. }
  34. function pop(heap) {
  35. const top = heap[0];
  36. const last = heap.pop();
  37. if (heap.length === 0) return top;
  38. heap[0] = last;
  39. let i = 0;
  40. while (true) {
  41. let small = i;
  42. for (const child of [2 * i + 1, 2 * i + 2]) {
  43. if (child < heap.length && heap[child][0] < heap[small][0]) small = child;
  44. }
  45. if (small === i) return top;
  46. [heap[small], heap[i]] = [heap[i], heap[small]];
  47. i = small;
  48. }
  49. }

How fast it is

TimeO(c log c)
Extra memoryO(c)

c is the number of cells. Each cell can be pushed a few times, and each heap step costs O(log c). A good heuristic usually explores far fewer cells than that.

  • Best caseO(d log d)

    The goal is in the same row as the start with nothing in between: only the d + 1 cells on that line are popped, while side cells, 2 higher in f, wait in the heap.

  • Average caseO(c log c)

    c is the number of cells. With a few walls A* usually pops a narrow band around the straight line, far fewer than c, but the bound stays the same as Dijkstra's.

  • Worst caseO(c log c)

    The goal can't be reached, or a U-shaped wall faces the start, so every reachable cell is popped before the way around is found.

Common mistakes

  • Using a heuristic that can overestimate, like Euclidean distance times 2. The path found may not be the shortest.
  • Returning when the goal is pushed instead of when it is popped. A cheaper path to it might still be in the heap.
  • Ordering the heap by h only (greedy search). It is fast but doesn't guarantee the shortest path.
  • Using Manhattan distance when diagonal moves are allowed. It can overestimate; use the larger of the row and column differences.

When to use it

Look for these clues in a problem:

  • There is one start and one known goal, and you need the shortest path between them.
  • The graph is a grid or a map where you can estimate the remaining distance, such as by rows and columns.
  • Plain BFS or Dijkstra explores too much of a large map.
  • The problem defines a heuristic, or a lower bound on the remaining cost is easy to compute.

Check yourself

Answer each one in your head first, then open it.

Why must A* stop when the goal is popped and not when it's pushed?

When pushed, a shorter path might still be waiting in the heap. When popped, every remaining entry has f >= g, so none can beat it.

What does A* become if h always returns 0?

Dijkstra's algorithm, because the heap is then ordered by g alone.

Why do cells behind the start get f 2 higher per step?

Each step away from the goal adds 1 to g and also adds 1 to h, while a step toward the goal adds 1 to g and takes 1 off h.

In the trace, why did A* explore the bottom route at all?

Its cells had f = 6, the same as the top route, so the guess couldn't tell them apart. It stopped only when moving away from the goal raised f to 8.

Practice problems

Stuck on one? Tuto is in the playground too, and gives you hints, never the answer.

Not started

0 of 2 solved. Solve one to earn the bronze medal, half for silver, and all of them for gold.

Start practicing

medium

hard

Go further

You don't need these to start practicing. Open one when you want more.

Why it works

The reasoning that makes it always right

The Manhattan distance never overestimates, and it's consistent: for neighboring cells a and b, h(a) <= 1 + h(b), because one move changes it by exactly 1. That makes f never go down along a path: the next cell's f is g + 1 + h(next), which is at least g + h(current).

That's the same as running Dijkstra's algorithm on adjusted costs: each move from a to b costs 1 - h(a) + h(b), which is 0 or 2, never negative. Dijkstra's proof then says the first time a cell comes out with g === best[r][c], that g is final.

When the goal comes out, h is 0, so its f equals its g. Every entry still in the heap has f >= g, and because h never overestimates, any path through those entries costs at least their f. So no remaining path to the goal is shorter, and returning g is correct. If the heap empties first, every reachable cell has been explored without meeting the goal, so it returns -1.

Going deeper

3 more ideas

Why the answer is still the shortest

The Manhattan distance never overestimates, and it changes by at most 1 when you take one step, which costs 1. Because of that, f never goes down along a path, and cells come out of the heap in order of f, just like Dijkstra with adjusted costs. When the goal comes out, its h is 0, so its f equals its real cost g, and nothing left in the heap can lead to a cheaper path.

Choosing a heuristic

For 4-way grid moves use Manhattan distance. For 8-way moves where diagonals cost the same as straight moves, use the larger of the row and column differences. A heuristic that overestimates can make A* faster but may return a path that is too long. If moves cost more than 1, the heuristic must still never exceed the true remaining cost, for example Manhattan distance times the smallest possible move cost.

Ties

Many cells often share the same f. The heap may return them in any order, which can change how many cells are explored and which of several equal paths is found, but never the length of the shortest path. If a problem asks about the route itself, it must define how ties are broken.

Work it by hand

Every step in a table, with why

A 4 by 5 grid where the straight line to the goal hits a wall. A* first heads right, gets blocked, and finds the way over the top.

grid = [".....", ".###.", "...#.", ".#..."], start = [2, 1], goal = [0, 3]

StepPop [f, g, r, c]Pushed (cell: f)What happensWhy
1[4, 0, 2, 1](2, 2): 4, (2, 0): 6Start: h = 2 + 2 = 4Down (3, 1) and up (1, 1) are walls. Right keeps f at 4 because it's closer to the goal; left raises f to 6.
2[4, 1, 2, 2](3, 2): 6Blocked above and rightUp (1, 2) and right (2, 3) are walls, and left is the start, already reached in fewer steps. Only down is new.
3[6, 1, 2, 0](3, 0): 8, (1, 0): 6Ties at 6 beginEvery entry left now has f of 6 or more. The heap returns (2, 0) first among the ties.
4[6, 2, 3, 2](3, 3): 6Bottom routeThe bottom route still looks as good as any other, so it keeps going.
5[6, 2, 1, 0](0, 0): 6Top routeMoving up toward row 0 keeps f at 6.
6[6, 3, 3, 3](3, 4): 8Bottom route turns awayFrom (3, 3) the only new cell is (3, 4), and moving down and away pushes f to 8.
7[6, 3, 0, 0](0, 1): 6Top routeFrom the top-left corner, moving right heads straight at the goal.
8[6, 4, 0, 1](0, 2): 6Top route(1, 1) below is a wall, so only right is new.
9[6, 5, 0, 2](0, 3): 6Goal pushed, not done yetThe goal goes into the heap, but the answer isn't final until it comes out.
10[6, 6, 0, 3]-Goal popped: return 6The goal has h = 0, so f = g = 6, and nothing left in the heap has a smaller f.

It returns 6 after 10 pops. The entries [8, 2, 3, 0] and [8, 4, 3, 4] were never popped, and the cells (2, 4), (1, 4), and (0, 4) were never reached, even though the bottom route looked promising at first.

Compared with other ways

When to pick something else
ApproachTimeExtra memoryChoose it when
A* searchO(c log c)O(c)One start, one known goal, and a guess of the remaining distance that never overestimates.
Dijkstra's algorithmO(c log c)O(c)There's no useful guess, or you need distances to many targets at once.
BFSO(rows × cols)O(rows × cols)Every move costs 1 and the grid is small. BFS is simpler and has no heap.
Greedy best-first searchO(c log c)O(c)Speed matters more than the shortest path. It orders by h alone and may return a longer route.

Extra memory: O(c): the best table has one number per cell, and the heap can hold a few entries per cell.

How the steps grow

1101001k10k100k1M116324864input size n
Steps as the input grows, for A* search and the other approaches, on a scale where each line up is 10 times more steps.
  • A* search, Dijkstra's algorithm, Greedy best-first search O(c log c)
  • BFS O(rows × cols)
About how many steps for bigger inputs
Approachn = 10n = 1,000n = 1,000,000
A* search339,96620 million
Dijkstra's algorithm339,96620 million
BFS1001 million1 trillion
Greedy best-first search339,96620 million

Inputs that need care

5 tricky inputs
start equals goal
The first pop is the goal, so it returns 0 without exploring anything.
The goal is a wall, or walled off
No entry for the goal is ever pushed, the heap runs out, and it returns -1 after exploring everything reachable.
The start cell is a wall
The code doesn't check it and searches from there anyway. If the problem says that means no path, check grid[start[0]][start[1]] first.
Many cells with the same f
The heap returns ties in any order. The length returned is always the same, but the number of pops and the route found can change.
A U-shaped wall around the straight line
The guess points into the U, so A* fills it before going around. The answer is still right; only the work grows toward Dijkstra's.

Variations and follow-ups

Twists interviewers add

Weighted A*

Order the heap by g + w * h with w above 1, such as 1.5. It heads for the goal more eagerly and pops fewer cells, but the path it returns can be up to w times longer than the shortest.

Other heuristics

For 8-way moves that all cost 1, use Math.max of the row and column distances. For any-angle movement, use the straight-line distance. Any guess works as long as it never exceeds the real remaining cost.

Returning the route

Keep a from table and set from[nr][nc] = [r, c] whenever best[nr][nc] improves. After popping the goal, walk from back to the start and reverse the list.

Searching from both ends

Bidirectional A* runs one search from the start and one from the goal and stops when they meet in the right way. It helps on big maps, but the stopping rule is harder to get right than in plain A*.

In an interview

Spot it, explain it, answer follow-ups
  • Spot it from a grid or map with one start and one goal, where BFS or Dijkstra would explore too much. Say "A* is Dijkstra with a guess added"; that frames the whole answer.
  • Explain why the answer is still the shortest: the guess never overestimates, so when the goal comes out of the heap, nothing left can lead to a shorter path.
  • Test by hand a grid where the straight line is blocked, like the trace, and check that the answer is the real detour length, not the Manhattan distance.
  • Expect "what if diagonal moves are allowed?". Answer: Manhattan distance can then overestimate, so switch to Math.max(Math.abs(dr), Math.abs(dc)) when diagonals cost 1.

Where frontend code uses it

The same idea in real UI code
  • Browser games move characters around obstacles on tile maps with A* path finding.
  • Diagram and whiteboard tools route connector lines around shapes by running A* on a grid of the canvas, often with extra cost for turns.
  • Map widgets that show walking routes inside a building or a venue, where the floor plan is a grid or graph with known coordinates.

Related algorithms