How does Dijkstra's Algorithm and A-Star compare?

algorithm artificial-intelligence graph a-star dijkstra
KingNestor picture KingNestor · Aug 26, 2009 · Viewed 79.2k times · Source

I was looking at what the guys in the Mario AI Competition have been doing and some of them have built some pretty neat Mario bots utilizing the A* (A-Star) Pathing Algorithm.

alt text
(Video of Mario A* Bot In Action)

My question is, how does A-Star compare with Dijkstra? Looking over them, they seem similar.

Why would someone use one over the other? Especially in the context of pathing in games?

Answer

leiz picture leiz · Aug 26, 2009

Dijkstra is a special case for A* (when the heuristics is zero).

Related questions

A* heuristic, overestimation/underestimation?

I am confused about the terms overestimation/underestimation. I perfectly get how A* algorithm works, but i am unsure of the effects of having a heuristic that overestimate or underestimate. Is overestimation when you take the square of the direct …

Read More
Why is the complexity of A* exponential in memory?

Wikipedia says on A* complexity the following (link here): More problematic than its time complexity is A*’s memory usage. In the worst case, it must also remember an exponential number of nodes. I fail to see this is correct …

Read More
What is the optimal algorithm for the game 2048?

I have recently stumbled upon the game 2048. You merge similar tiles by moving them in any of the four directions to make "bigger" tiles. After each move, a new tile appears at random empty position with a value of either 2 …

Read More