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:

g(n)
Cost so far. The actual cost of the cheapest route from S to n found so far.

If S→A costs 2, then g(A) = 2.

h(n)
Guess of what's left. A cheap estimate of the cost from n to G, such as straight-line distance.

We guess A is about 4 from the goal: h(A) = 4.

f(n)
Estimated total trip. 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
AlgorithmPRIORITYPlain English
Dijkstrag(n)"Explore whatever is cheapest to reach."
Greedy best-firsth(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.

2235412Sh=6g=0Ah=4Ch=2Gh=0Bh=3Dh=7Eh=8
Step 0 of 4
  • Put the start S in the open set with g = 0. Nothing is closed yet.
Open setsorted by f
nodeghf

The top row gets popped next.

On this graphNodes expandedPath foundCost
Dijkstra7 (S, D, A, E, C, B, G)S → A → C → G7 ✓ shortest
Greedy best-first3 (S, B, G)S → B → G9 ✗ not shortest
A*4 (S, A, C, G)S → A → C → G7 ✓ 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)".

Dijkstrapriority = g
#PopArithmeticOpen after
0—Start: g(S) = 0S:0
1S (0)D = 0+1 = 1, A = 0+2 = 2, B = 0+5 = 5D:1, A:2, B:5
2D (1)E = 1+2 = 3A:2, E:3, B:5
3A (2)C = 2+2 = 4E:3, C:4, B:5
4E (3)dead endC:4, B:5
5C (4)G = 4+3 = 7B:5, G:7
6B (5)G via B = 5+4 = 9 ≥ 7, ignoreG:7
7G (7)goal → stop—

S → A → C → G, cost 7, 7 expansions

Greedypriority = h
#PopArithmeticOpen after
0—Start: h(S) = 6S:6
1S (h 6)B h=3, A h=4, D h=7B:3, A:4, D:7
2B (h 3)G h=0 (g = 5+4 = 9)G:0, A:4, D:7
3G (h 0)goal → stopA:4, D:7 (never explored)

S → B → G, cost 9, 3 expansions

A*priority = f = g + h
#PopArithmeticOpen after
0—Start: f(S) = 0 + 6 = 6S:6
1S (6)A = 2+4 = 6, B = 5+3 = 8, D = 1+7 = 8A:6, B:8, D:8
2A (6)C = (2+2) + 2 = 6C:6, B:8, D:8
3C (6)G = (4+3) + 0 = 7G:7, B:8, D:8
4G (7)goal → stopB: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:

h(B) = 3  <  h(A) = 4  <  h(D) = 7  ⇒  pick B

It never asks what it costs to get to B. Add that in and the picture flips:

via B:  5 + 4 = 9    via A:  2 + 2 + 3 = 7

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:

Click a square to move
nG

dx = |8 − 1| = 7dy = |1 − 4| = 3

HeuristicFormulaWorked outh≤ 10 (4-way)?≤ 8.24 (8-way)?
Manhattan|dx| + |dy|7 + 310✓✗ over
Euclidean√(dx² + dy²)√(49 + 9) = √587.62✓✓
Octilemax + (√2 − 1)·min7 + 0.414 × 38.24✓✓
Chebyshevmax(|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)  ≤  h*(n)   for every node n

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:

G: f = 7    B: f = 8    D: f = 8

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:

any route via B  ≥  g(B) + h(B) = f(B) = 8  >  7

The same goes for D. Nothing left in the open set can beat 7, so stopping is safe.

The general argument (4 lines)

  1. Let C* be the true shortest cost. Suppose A* pops G with a worse cost C > C*.
  2. Some node n on the true shortest path is still in the open set, with g(n) = its optimal cost so far.
  3. Then f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C* < C = f(G).
  4. 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:

h(n)  ≤  cost(n, m) + h(m)

Check it on every edge of the example:

Edgeh(n)cost + h(m)OK?
S–Ah(S) = 62 + h(A) = 6✓
S–Bh(S) = 65 + h(B) = 8✓
S–Dh(S) = 61 + h(D) = 8✓
A–Ch(A) = 42 + h(C) = 4✓
C–Gh(C) = 23 + h(G) = 3✓
B–Gh(B) = 34 + h(G) = 4✓
D–Eh(D) = 72 + 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

f(n) = g(n) + w · h(n)
w = 0Dijkstraoptimal, most work
w = 1A*optimal if h is admissible
w → ∞≈ Greedyleast work, no guarantee

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

DijkstraGreedy best-firstA*
Priorityghg + h
Shortest path?AlwaysNo guaranteeYes, if h is admissible
Work doneMost: expands in all directionsLeast, usuallyIn between, and far less with a good h
Needs a heuristic?NoYesYes
Use whenNo goal direction, or you need distances to everythingAny path fast is fineYou want the shortest path to one goal
Try all three in the playground →