Why does A* run faster than Dijkstra's algorithm?

Question

Wikipedia says A* runs in O(|E|) where |E| is the number of edges in the graph. But my friend says A* is just a general case of Dijkstra's algorithm, and Dijkstra's algorithm runs in O(|E| + |V| log |V|). So I am confused about why A* runs faster than Dijkstra's algorithm.

Answer 1

I think the time complexity of A* listed on Wikipedia is incorrect (or at least, it's misleading). That time complexity only seems to count the number of states expanded in the search, rather than the time required to determine which states to explore.

To be efficient, A* search needs to store a priority queue containing what nodes in the fringe need to be explored and it has to be able to call decrease-key on those priorities. The runtime for this is, in the worst-case, O(n log n + m) if implemented using a good priority queue. Therefore, in the worst case, you'd expect A* to degrade to Dijkstra's algorithm. Given a good heuristic, A* will not expand out all the nodes and edges that Dijkstra's algorithm would, which is the main reason why A* is faster.

Of course, the time complexity of A* search needs to factor in the cost of computing the heuristic. Some complex heuristics might not be computable in time O(1), in which case the runtime for A* could actually be worse than Dijkstra's algorithm.

Hope this helps!

Answer 2

Essentially A* is faster because it can use heuristics to make more educated guesses about which route is the best to case, something which Dijkstra's algorithm does not do.