The A algorithm* is a shortest path algorithm for weighted graphs. It can outperform Dijkstra’s algorithm by using problem-specific heuristic functions in the wavefront sorting and ordering, so it finds broad uses due to its efficiency. It essentially looks into the most promising partial solutions first, i.e., it acts as a best-first search.
The heuristic function must not overpredict, to guarantee the best path.
It has a worst-case time complexity of .