Course contentsShow
← Computer Science
Lesson 1008 of 2,87223. Shortest Path AlgorithmsFree lesson

A* Correctness and Optimality

Prove that A* with admissible heuristics always finds the shortest path and terminates.

A* Correctness and Optimality

What You'll Learn

You'll learn why A* is guaranteed to find the shortest path when using admissible heuristics and why it always terminates successfully.

Why A* Always Works

Think of A* like a careful explorer who never gives up on a promising path too early. The algorithm's correctness relies on two fundamental guarantees:

Termination: A* will always finish because it explores nodes in order of their f(n) = g(n) + h(n) value. Since g(n) (actual cost so far) grows as we move away from the start, and we have a finite graph, eventually we must reach the goal or exhaust all possibilities.

Optimality: Here's the key proof: When A* selects the goal node for expansion, it has the lowest f value among all nodes in the open set. If a shorter path existed, some node on that path would have a lower f value (because with an admissible heuristic, h(n) never overestimates). That node would've been expanded first! Since we're expanding the goal now, no better path exists.

The Admissibility Guarantee

An admissible heuristic never overestimates the true remaining cost. This is crucial—it ensures A* doesn't prematurely discard the optimal path. If h(n) is always ≤ true cost, then when we expand a node, we can be confident we haven't missed a better route.

Think of it like optimistic estimation: your GPS says "at least 20 minutes remaining" but never lies by saying 5 minutes when it's actually 30. This honesty keeps A* on track.

Key Takeaway: A* with an admissible heuristic is both correct (always terminates) and optimal (finds the shortest path) because it explores nodes systematically and never prematurely dismisses better alternatives.