Learn
Understand A*, Greedy and Dijkstra with one 7-node graph
Every number on this page is small enough to check in your head. Read the idea, step through the example, then follow the math for why A* finds the shortest path and Greedy doesn't.
01 The idea
You're at S and want to reach G. Roads have costs. A search keeps two lists: the open set (places you've seen but not explored yet) and the closed set (places you've finished with). Each round, it takes the most promising place out of the open set and looks at its neighbors.
Every node carries two numbers:
If S→A costs 2, then g(A) = 2.
We guess A is about 4 from the goal: h(A) = 4.
f = g + h, the estimated cost of the full route through n.f(A) = 2 + 4 = 6.
02 One loop, three rules
All three algorithms run the same loop. Only the highlighted line differs:
open = { start } g(start) = 0
while open is not empty:
n = the node in open with the smallest PRIORITY
if n is the goal: follow parents back and stop
move n from open to closed
for each neighbor m of n (not closed):
new_g = g(n) + cost(n, m)
if new_g < g(m): # found a cheaper way to m
g(m) = new_g; parent(m) = n; add m to open| Algorithm | PRIORITY | Plain English |
|---|---|---|
| Dijkstra | g(n) | "Explore whatever is cheapest to reach." |
| Greedy best-first | h(n) | "Explore whatever looks closest to the goal." |
| A* | g(n) + h(n) | "Explore whatever gives the cheapest estimated total trip." |
Think of A* as Dijkstra with a sense of direction, and Greedy as a sense of direction with no memory of what it has already spent.
03 Interactive walkthrough
Press Next step. Each step shows which node gets popped, the arithmetic for every neighbor, and the open set after the update. Switch tabs to run a different algorithm on the same graph. Numbers above a node are its g; numbers below are its h.
fAlways expand the open node with the smallest f = g + h, the estimated total.
- Put the start S in the open set with
g = 0. Nothing is closed yet.
- S066
The top row gets popped next.
| On this graph | Nodes expanded | Path found | Cost |
|---|---|---|---|
| Dijkstra | 7 (S, D, A, E, C, B, G) | S → A → C → G | 7 ✓ shortest |
| Greedy best-first | 3 (S, B, G) | S → B → G | 9 ✗ not shortest |
| A* | 4 (S, A, C, G) | S → A → C → G | 7 ✓ shortest |
04 Worked by hand
Here's the same thing as three paper traces. Read each row as "pop this node, do this arithmetic, and this is the open set afterwards (best first)".
g| # | Pop | Arithmetic | Open after |
|---|---|---|---|
| 0 | — | Start: g(S) = 0 | S:0 |
| 1 | S (0) | D = 0+1 = 1, A = 0+2 = 2, B = 0+5 = 5 | D:1, A:2, B:5 |
| 2 | D (1) | E = 1+2 = 3 | A:2, E:3, B:5 |
| 3 | A (2) | C = 2+2 = 4 | E:3, C:4, B:5 |
| 4 | E (3) | dead end | C:4, B:5 |
| 5 | C (4) | G = 4+3 = 7 | B:5, G:7 |
| 6 | B (5) | G via B = 5+4 = 9 ≥ 7, ignore | G:7 |
| 7 | G (7) | goal → stop | — |
S → A → C → G, cost 7, 7 expansions
h| # | Pop | Arithmetic | Open after |
|---|---|---|---|
| 0 | — | Start: h(S) = 6 | S:6 |
| 1 | S (h 6) | B h=3, A h=4, D h=7 | B:3, A:4, D:7 |
| 2 | B (h 3) | G h=0 (g = 5+4 = 9) | G:0, A:4, D:7 |
| 3 | G (h 0) | goal → stop | A:4, D:7 (never explored) |
S → B → G, cost 9, 3 expansions
f = g + h| # | Pop | Arithmetic | Open after |
|---|---|---|---|
| 0 | — | Start: f(S) = 0 + 6 = 6 | S:6 |
| 1 | S (6) | A = 2+4 = 6, B = 5+3 = 8, D = 1+7 = 8 | A:6, B:8, D:8 |
| 2 | A (6) | C = (2+2) + 2 = 6 | C:6, B:8, D:8 |
| 3 | C (6) | G = (4+3) + 0 = 7 | G:7, B:8, D:8 |
| 4 | G (7) | goal → stop | B:8, D:8 (never explored) |
S → A → C → G, cost 7, 4 expansions
05 Why Greedy fails here
Look at the moment right after S is expanded. Greedy compares only the h values:
It never asks what it costs to get to B. Add that in and the picture flips:
A* catches this. At that same moment it compares f(A) = 2 + 4 = 6 withf(B) = 5 + 3 = 8 and picks A. The expensive first road counts against B.
Takeaway: Greedy minimizes the wrong thing. "Close to the goal" isn't the same as "cheap to finish from here, counting what you've paid."
06 Heuristics and the math
On a grid, h is usually a distance formula computed from dx and dy, the column and row gaps between node n and the goal. Move the points and watch each formula change:
dx = |8 − 1| = 7dy = |1 − 4| = 3
| Heuristic | Formula | Worked out | h | ≤ 10 (4-way)? | ≤ 8.24 (8-way)? |
|---|---|---|---|---|---|
| Manhattan | |dx| + |dy| | 7 + 3 | 10 | ✓ | ✗ over |
| Euclidean | √(dx² + dy²) | √(49 + 9) = √58 | 7.62 | ✓ | ✓ |
| Octile | max + (√2 − 1)·min | 7 + 0.414 × 3 | 8.24 | ✓ | ✓ |
| Chebyshev | max(|dx|, |dy|) | max(7, 3) | 7 | ✓ | ✓ |
The last two columns compare h with the real cost of the cheapest route on an empty grid. A ✓ means this h is admissible for that kind of movement. Hover a row to highlight the route it "imagines".
The rule that matters: admissibility
h*(n) is the true cheapest cost from n to the goal. An admissible heuristic never overestimates, so it's always optimistic. In the table above:
- 4-way moves: the true cost on an empty grid is
dx + dy. Manhattan equals it exactly, so it's admissible and as informed as possible. The others come out smaller: still admissible, just less informed. - 8-way moves (diagonal = √2): the true cost is Octile. Manhattan now gives a value that's too high, for example dx = dy = 3 → Manhattan 6 versus true 4.24. That makes it inadmissible, and A* can return a path that isn't the shortest.
Bigger h = less work, as long as it stays ≤ h*. The best heuristic is the largest one that never overshoots. h = 0 is always admissible, and it turns A* into Dijkstra.
07 Why A* finds the shortest path
Start with the example. When A* pops G, the open set is:
Could a route through B beat 7? Its total is at least g(B) + h*(B). Since h never overestimates,h*(B) ≥ h(B), so:
The same goes for D. Nothing left in the open set can beat 7, so stopping is safe.
The general argument (4 lines)
- Let C* be the true shortest cost. Suppose A* pops G with a worse cost C > C*.
- Some node n on the true shortest path is still in the open set, with g(n) = its optimal cost so far.
- Then
f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C* < C = f(G). - So n has a smaller f than G and would have been popped first. Contradiction ∎
Step 3 is the only place admissibility is used. If h overestimates, f(n) can look larger than C* and the argument breaks. That's exactly what happens with Manhattan on diagonal grids.
08 Consistency (the stronger version)
A heuristic is consistent if crossing one edge can't make the guess drop by more than the edge costs:
Check it on every edge of the example:
| Edge | h(n) | cost + h(m) | OK? |
|---|---|---|---|
| S–A | h(S) = 6 | 2 + h(A) = 6 | ✓ |
| S–B | h(S) = 6 | 5 + h(B) = 8 | ✓ |
| S–D | h(S) = 6 | 1 + h(D) = 8 | ✓ |
| A–C | h(A) = 4 | 2 + h(C) = 4 | ✓ |
| C–G | h(C) = 2 | 3 + h(G) = 3 | ✓ |
| B–G | h(B) = 3 | 4 + h(G) = 4 | ✓ |
| D–E | h(D) = 7 | 2 + h(E) = 10 | ✓ |
Why it matters: with a consistent h, f never goes down along a path. On A*'s route,f(S) = 6, f(A) = 6, f(C) = 6, f(G) = 7. So the first time A* pops a node, it already has that node's cheapest g, and nothing ever needs to be reopened.
09 Weighted A*: the dial between them
For w > 1, the path costs at most w × C*. With w = 2 you might pay up to twice the best cost, but you usually expand far fewer nodes. Try the weight slider in the playground.
10 Check yourself
Use the graph from the walkthrough. Work out each one, then open the answer.
Q1. In A*, right after S is expanded, what is f(D)?
g(D) = 0 + 1 = 1, h(D) = 7, so f(D) = 8. It ties with B, and never gets popped because G (f = 7) comes out first.
Q2. Dijkstra expands E, but A* doesn't. Why?
Dijkstra expands every node with g < 7 (the best cost), and g(E) = 3. A* would needf(E) = 3 + 8 = 11 to be below 7, and it isn't. h tells A* that E points the wrong way.
Q3. If h(B) were 6 instead of 3, which path would Greedy pick? Is that h admissible?
Greedy now picks A (h = 4) over B (h = 6), then C, then G. That gives S → A → C → G, cost 7, the right answer. But h(B) = 6 > h*(B) = 4, so it's not admissible. A* would still be fine here, but in general an overestimate can hide the best path.
Q4. What does A* do if every h is 0?
f = g + 0 = g, so it orders the open set exactly like Dijkstra. Same pops, same 7 expansions.
11 Cheat sheet
| Dijkstra | Greedy best-first | A* | |
|---|---|---|---|
| Priority | g | h | g + h |
| Shortest path? | Always | No guarantee | Yes, if h is admissible |
| Work done | Most: expands in all directions | Least, usually | In between, and far less with a good h |
| Needs a heuristic? | No | Yes | Yes |
| Use when | No goal direction, or you need distances to everything | Any path fast is fine | You want the shortest path to one goal |