Basic Concepts

Search proceeds in rings of increasing f cost. Note that if h is a perfect heuristic, the source and destination have the same f cost.

• A^* brings inside all nodes with $f(v) \le f(t) = \delta(s,t)$.
• A^* may bring inside some nodes with $f(v) = \delta(s,t)$ before bringing inside t and terminating.

Correctness: Solution found is true shortest path because all subsequent contours have higher f cost, and therefore, higher distance.