Episode #125 of the Stack Overflow podcast is here. We talk Tilde Club and mechanical keyboards. Listen now

A* is a graph shortest-path algorithm that uses a heuristic function to speed up the search

A* is a single-source shortest path algorithm that use a heuristic function in order to speed up its search. The algorithm is similar to dijkstra's algorithm, but uses the heuristic evaluation of each node to determine which node should first be explored.

The A* algorithm is both complete (will always find a path if one exists) and optimal (finds the shortest path) if the heuristic function provided is admissible. If more than one path exists with the same "lowest" cost score, the algorithm will return the path first explored.

Related tags:

history | excerpt history