Skip to content

level 7 · Graphs

A* Search

Dijkstra with a sense of direction — it guesses what's left, and aims.

13 min 110 XP

what is it

Start here

Dijkstra has no idea where it's going. It spreads outward in every direction equally, treating a node *behind* you exactly like a node in front of you. On a map of a whole country, asked for a route across one city, it will happily explore halfway to the coast before it happens to stumble on the destination.

A* adds one thing: a **guess**. For each node, estimate how far is still left to go — call it **h**. Then, instead of expanding the node with the lowest cost-so-far (that's Dijkstra), expand the one with the lowest **f = g + h**: what it actually cost to get here, plus what we reckon remains.

That single addition gives the search a sense of direction. Nodes pointing away from the goal get a big h and sink down the queue, and A* barely glances at them. Look at the final step of the visualization: it names the nodes it never even touched.

But the guarantee comes with a condition, and it's the thing to actually remember. The heuristic must never **overestimate**. It has to be optimistic. Straight-line distance is perfect for this — roads bend, so the true distance is always at least the straight line, never less.

Let h overestimate and A* becomes fast, confident, and wrong: it will happily dismiss the genuinely best route because it *guessed* that route was expensive. Speed bought with a lie.

One last thing worth carrying with you: set h = 0 and A* *is* Dijkstra, exactly. The entire difference between the two is the guess.

real-life analogy

Picture it

Walking to a landmark you can see

Dijkstra explores every street outward from you in rings until it bumps into the cathedral. You can see the cathedral spire, so when you reach a junction you take the road that heads towards it. You might still backtrack from a dead end — but you'll never wander into the suburbs behind you. The spire is the heuristic.

interactive visualization

Watch it run

Each node shows g + h — the real cost so far, plus the guess of what's left.

3243463542
S 0+9
A ∞+7
B ∞+7
C ∞+4
D ∞+6
E ∞+3
F ∞+3
G ∞+0

queue · FIFO

S 0+9

take from the front

Get from S to G. Each node shows two numbers: **g**, what it actually cost to reach it, and **h**, a straight-line *guess* of what's left. A* always expands the node with the smallest g + h — so it aims at the goal instead of spreading out blindly like Dijkstra.

step 01/19

  • just discovered
  • visited
  • found it
  • visiting now
1// Dijkstra explores in every direction. A* aims.
2function aStar(graph, start, goal) {
3 const g = {}; // real cost from the start
4 for (const v of graph.nodes) g[v] = Infinity;
5 g[start] = 0;
6
7 const open = new PriorityQueue();
8 // f = what it cost to get here + a GUESS of what's left
9 open.push(start, h(start, goal));
10
11 while (!open.isEmpty()) {
12 const u = open.pop(); // lowest f, not lowest g
13 if (u === goal) return g[goal];
14
15 for (const [v, w] of graph.edges[u]) {
16 if (g[u] + w < g[v]) {
17 g[v] = g[u] + w;
18 open.push(v, g[v] + h(v, goal)); // f = g + h
19 }
20 }
21 }
22 return Infinity;
23}

variables right now

start
S
goal
G
note
labels show g + h
comparisons 0moves 0

the dry run · every step, in words

19 steps

complexity

What it costs

best case
O(E)
average
O(E log V)
worst case
O(E log V)
extra memory
O(V)

The same worst case as Dijkstra — with a useless heuristic it degrades to exactly Dijkstra. In practice a good heuristic slashes the number of nodes expanded, often dramatically. The complexity class doesn't change; the real-world work does.

  • O(1)
  • O(log n)
  • O(n)
  • O(n log n) · this one
  • O(n²)
input size →work →

common mistakes

Common traps

  • Using a heuristic that overestimates.

    Then A* can discard the genuinely best route because it guessed wrongly that the route was expensive. It stays fast and becomes wrong. The heuristic MUST be optimistic.

  • Expanding on the lowest g instead of the lowest f.

    That's just Dijkstra with extra steps. The whole point is to prioritise by g + h, so the guess actually steers the search.

  • Using A* when there's no meaningful heuristic.

    If you can't estimate the remaining distance, h = 0 — and A* is precisely Dijkstra. Use A* when the problem has real geometry to exploit.

  • Thinking A* has a better Big-O than Dijkstra.

    It doesn't. Same worst case. What it improves is how many nodes it actually expands in practice, which is often the difference that matters.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+110 XP

01What is f in A*?

02What must be true of the heuristic for A* to stay correct?

03You set h = 0 for every node. What is A* now?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.