A* search algorithm

A transcendental tree search algorithm, A* (pronounced "Ay-star") guarantees the shortest path from any beginning point to any end point. This is provided that there is any possible path at all. Despite this assurance, A* can be computationally expensive and is therefore not always used.

At the heart of the A* algorithm is the use of a "heuristic estimate" which ranks each node by an estimate of the best route that goes through that node.