Adding a guess
A star is Dijkstra with a sense of direction. For each node it tracks the known cost from the start plus a heuristic estimate of the cost remaining to the goal. It always expands the node with the smallest total of those two parts.
Admissible and consistent
The heuristic must never overestimate the true remaining cost; such a heuristic is called admissible, and it guarantees the optimal path. A stronger property, consistency, means the estimate drops by at most the edge weight along any step, which lets settled nodes stay settled.
- Known cost from start: measured exactly.
- Estimated cost to goal: supplied by the heuristic.
- Expand the node minimizing their sum.
A common heuristic on a grid is straight line distance, which never exceeds the real path length.
Key idea
A star ranks nodes by known cost plus an admissible heuristic estimate of remaining cost, focusing the search toward the goal while still returning an optimal path.