A* search
Time complexity: O(E log V) with a good heuristic.
Result
Examples
How it works
A* explores the cell with the lowest cost so far plus a guess of the distance left. The guess pulls the search towards the goal, so it usually looks at far fewer cells than Dijkstra and still finds the shortest path.
When to use it
Route finding in games and maps, where you know roughly where the goal is.