A* Search
Software Engineer path · lesson 24 of 99An informed search algorithm that uses heuristics to guide the search. It guarantees the shortest path (if heuristic is admissible) and is usually much faster than Dijkstra.
Switch and compare the expanded-cells count.
Start at (4,1), goal (4,11).
- 1g[start] = 0; open = [(h(start), start)]
- 2while open:
- 3 cell = open.pop_min(g + h) # cheapest estimate first
- 4 if cell == goal: return path
- 5 for nb in neighbours(cell):
- 6 if g[cell] + cost(nb) < g[nb]: g[nb] = …; parent[nb] = cell; open.push(nb, g[nb] + h(nb))
- 7return "no path"
- Cells expanded
- 0 / 61
- Frontier pushes
- 1 / 91
Tap any element in the diagram to inspect its state at this step.
Keys: ← → step, Space play/pause. Predict mode pauses before key steps and asks what happens next.
g, h, or f?
Sort each description into the part of f(n) = g(n) + h(n) it describes.
Tap a piece, then tap where it goes — or drag it. Tap the tray to take one back.
g(n) — cost so far
Drop items hereh(n) — heuristic
Drop items heref(n) — priority
Drop items hereTest your knowledge
What is the role of the Heuristic (h) in A*?
The short version
Think of driving with a GPS. It doesn't just look at road distance; it also estimates the remaining time to the destination (Heuristic) to guide you, avoiding paths that clearly lead away from the goal.
In more depth
Smart Search with Heuristics
A* (A-Star) is an extension of Dijkstra's algorithm. Instead of blindly exploring the closest nodes, A* uses a Heuristic to guess which nodes are more promising (closer to the goal).
f(n) = g(n) + h(n)
By prioritizing nodes with the lowest total estimated cost f(n), A* directs the search towards the target, often visiting far fewer nodes than Dijkstra.
Admissibility
For A* to guarantee the shortest path, the heuristic h(n) must be admissible, meaning it never overestimates the true cost to reach the goal. Common heuristics include Manhattan Distance (for grids) and Euclidean Distance.
When to reach for this
- Pathfinding in games/maps where you know the target location
- Grid traversal with obstacles
- Solving puzzles (like 8-puzzle) efficiently
Interview Questions
References & Further Reading
Love this visualization?
Sign up to track your progress, earn achievements, use the AI assistant, and access your personal learning dashboard.
100% free • No credit card required