5

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.

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
Jessica
  • 2,335
  • 2
  • 23
  • 36
  • 2
    [wikipedia](http://en.wikipedia.org/wiki/A*_search_algorithm) Seems to talk a fair amount about the difference between it and Djikstra's. I'd start there – hankd Nov 08 '13 at 21:57
  • 1
    Yeah, the Wikipedia article says A* is equivalent to Dijkstra's algorithm. Which is what I am confused about. – Jessica Nov 08 '13 at 21:58
  • 1
    No, it says "...and A* is equivalent to running Dijkstra's algorithm **with the reduced cost d'(x, y) := d(x, y) - h(x) + h(y).**" – hankd Nov 08 '13 at 22:00
  • 1
    Yeah, which means it should take the same amount of time right? – Jessica Nov 08 '13 at 22:02
  • Dijkstra is a special case of A*. When h gives no information complexitiy is the same. See previous answer in [SO](http://stackoverflow.com/questions/1332466/how-does-dijkstras-algorithm-and-a-star-compare) – Louis Hugues Nov 08 '13 at 22:17
  • The time-complexity of both algorithms is the same. The first is considering only the number of edges that need to be expanded, while the second also includes the time-complexity of using the priority queue. It's comparing apples to oranges. – BlueRaja - Danny Pflughoeft Nov 08 '13 at 23:03

2 Answers2

10

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!

templatetypedef
  • 362,284
  • 104
  • 897
  • 1,065
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.

Dale Myers
  • 2,703
  • 3
  • 26
  • 48