A* search

Dijkstra with a sense of direction. Order the frontier by f = g + h: cost-so-far + estimate-to-go.

The one extra term

• Dijkstra picks the node closest to the START (g alone) → explores a circle
• A* picks the node on the most promising path to the GOAL (g + h)
• h(n) = heuristic estimate of remaining distance (e.g. Manhattan on a grid)
• h = 0 ⇒ A* IS Dijkstra. The heuristic is the whole difference.

Watch the frontier reach for the goal

Purple = start · red = goal · blue = open · grey = closed · green = path. The search bends around walls but strains toward the far corner.

Same path, a fraction of the work

3600 cells: Dijkstra expands ~3200 (the whole grid), A* ~290 → 11× fewer. Same optimal path.

The catch: admissibility

• Optimal iff h never OVERESTIMATES remaining distance (admissible)
• Overestimate → faster but returns a non-shortest path, silently
• Manhattan distance on a 4-grid is admissible (can't beat |Δr|+|Δc| steps)
• Tie-break: prefer larger g among equal f → hug the goal, not a plateau

Takeaway

Beat a general algorithm by injecting domain knowledge it can't use — here, geometry. Dijkstra optimal among the goal-blind; A* optimal among those who know h. Next: minimum spanning trees — Prim is this same heap traversal, one word changed.