A star algorithm

A star (A*) pathfinding algorithm.

It works almost same with Dijkstra algorithm, but with heuristic approach. Distance to all unvisited nodes are calculated with $g(v) + h(v)$ where $g(v)$ is the actual cost from start to $v$, $h(v)$ is the estimated cost from v to end.

If $h(v)$ is always $0$, it does exact same thing with Dijkstra algorithm.

In many path finding problems, we can get spatial information. A* algorithm uses this information as $h(v)$ to make searching faster.