A* Search

Dijkstra's guided by a heuristic: it settles the node with the smallest f = g + h, where g is the cost so far and h is the straight-line distance to the goal. With an admissible heuristic it finds the optimal path while exploring far fewer nodes.

Best

O(E)

Average

O(E log V)

Worst

O(E log V)

Space

O(V)