A* Search Algorithm

A* algorithm is Dijkstra's algorithm plus guessing.

At each iteration in Dijkstra's algorithm, you pick a node whose distance from the start node is minimum. On the other hand, you pick a node whose sum of the distance from the start node and the estimation cost to reach the goal node. The function which gives the estimation is called heuristic function.

The property of heuristic function $h$ determines the overall behavior of A* algorithm:

• $h(\text{node}) = 0$ for all nodes in the graph: The behavior of A* algorithm becomes identical to Dijkstra's algorithm.
• $h(\text{node})$ is no greater than the actual shortest path to the goal for all nodes in the graph, a.k.a. $h$ is admissive: A* algorithm will return a shortest path from the start to the goal.
• $h(\text{node}_{x}) - h(\text{node}_{y})$ is less than actual cost from $\text{node}_{x}$ to $\text{node}_{y}$ for all edges, a.k.a. $h$ is monotonic: A* will not visit any node more than once.