What is the A* Search Algorithm?
Understand how A* search combines cost-so-far and a heuristic to find optimal paths efficiently, with code and interview guidance.
Expected Interview Answer
A* search finds the shortest path between two specific nodes by combining Dijkstra's guaranteed-shortest exploration with a heuristic estimate of remaining distance, expanding nodes in order of f(n) = g(n) + h(n), where g(n) is the known cost so far and h(n) is an estimated cost to the goal.
By prioritizing nodes with the lowest f(n) using a min-heap, A* focuses its search toward the goal instead of expanding uniformly in every direction like Dijkstra, which dramatically reduces the number of nodes explored on large maps or graphs. The heuristic h(n) must be admissible — never overestimating the true remaining cost — for A* to guarantee an optimal shortest path; a common choice is straight-line (Euclidean) distance for grid or map pathfinding, since it can never exceed the actual travel distance. If h(n) is also consistent (satisfying a form of the triangle inequality), A* never needs to re-expand a node once finalized, matching Dijkstra's efficiency characteristics with far fewer expansions in practice. This makes A* the standard algorithm for game pathfinding, robotics navigation, and route planners, where Dijkstra's blind, uniform expansion would waste time exploring in every direction away from the goal.
- Finds the optimal shortest path when the heuristic is admissible
- Explores far fewer nodes than Dijkstra by aiming toward the goal
- Flexible heuristic choice adapts to grids, maps, and abstract graphs
- Industry standard for pathfinding in games, robotics, and navigation
AI Mentor Explanation
A scout planning the fastest route from the team hotel to the stadium does not check every possible street in every direction like an exhaustive search would; instead, at each intersection they weigh the distance already walked plus a straight-line guess of how far the stadium still is, always continuing down the path with the lowest combined estimate. As long as that straight-line guess never overstates the true remaining walk, the scout is guaranteed to find the genuinely shortest route, not just a plausible one. This is far faster than checking every direction equally, because most streets pointing away from the stadium are quickly deprioritized. It is exactly why route apps reach a specific destination so much faster than a search that expands blindly outward in a ring.
Step-by-Step Explanation
Step 1
Initialize g and f scores
g(start) = 0, f(start) = h(start); push start onto a min-heap keyed by f(n).
Step 2
Pop the lowest f(n) node
Expand the node with the smallest known-cost-plus-estimate; stop early if it is the goal.
Step 3
Relax neighbors
For each neighbor, compute tentative g; if better than known, update g, f = g + h, and push to the heap.
Step 4
Guarantee optimality via admissible h
As long as h(n) never overestimates true remaining cost, the first time the goal is popped its path is optimal.
What Interviewer Expects
- Define f(n) = g(n) + h(n) and explain each term
- State the admissibility requirement for the heuristic to guarantee optimal paths
- Contrast with Dijkstra: A* is Dijkstra with a goal-directed heuristic (h(n) = 0 reduces A* to Dijkstra)
- Give a concrete heuristic example, e.g. Euclidean or Manhattan distance for grids
Common Mistakes
- Using an inadmissible heuristic (one that overestimates) and still expecting an optimal path
- Confusing A* with best-first search that ignores g(n) entirely
- Forgetting A* reduces to Dijkstra when h(n) = 0 for all nodes
- Not handling re-expansion correctly when the heuristic is admissible but not consistent
Best Answer (HR Friendly)
“A* search finds the shortest path to a specific goal by combining the actual distance traveled so far with a smart guess of how much further is left, always exploring the most promising direction first. I use it instead of plain Dijkstra whenever I have a good distance estimate to the goal, since it explores dramatically fewer nodes while still guaranteeing the optimal path.”
Code Example
import heapq
def a_star(start, goal, neighbors_fn, heuristic_fn):
open_set = [(heuristic_fn(start, goal), 0, start)]
g_score = {start: 0}
came_from = {}
while open_set:
_, g, current = heapq.heappop(open_set)
if current == goal:
path = [current]
while current in came_from:
current = came_from[current]
path.append(current)
return list(reversed(path))
for neighbor, weight in neighbors_fn(current):
tentative_g = g + weight
if tentative_g < g_score.get(neighbor, float("inf")):
g_score[neighbor] = tentative_g
came_from[neighbor] = current
f = tentative_g + heuristic_fn(neighbor, goal)
heapq.heappush(open_set, (f, tentative_g, neighbor))
return NoneFollow-up Questions
- What happens to A* if the heuristic overestimates the true remaining cost?
- How does A* reduce to Dijkstra when the heuristic is always zero?
- What is the difference between an admissible and a consistent heuristic?
- How would you use A* for pathfinding on a weighted grid with diagonal movement?
MCQ Practice
1. In A* search, what does f(n) = g(n) + h(n) represent?
g(n) is the actual cost from the start to n, and h(n) is the heuristic estimate from n to the goal.
2. For A* to guarantee an optimal path, the heuristic must be:
An admissible heuristic never overestimates the true remaining cost, which is what preserves optimality.
3. What does A* search become if the heuristic h(n) is zero for every node?
With h(n) = 0 everywhere, f(n) = g(n), which is exactly the ordering Dijkstra uses.
Flash Cards
What does f(n) represent in A* search? — f(n) = g(n) + h(n): known cost so far plus estimated remaining cost to the goal.
What property must the heuristic have for A* to be optimal? — Admissibility — it must never overestimate the true remaining cost.
How does A* relate to Dijkstra's algorithm? — A* is Dijkstra with a goal-directed heuristic; it reduces to Dijkstra when h(n) = 0.
Name a common heuristic for grid-based A* pathfinding. — Euclidean distance or Manhattan distance to the goal.