Dijkstra is a special case for A* (when the heuristics is zero).
leiz
2009-08-26 05:18:30
+4
A:
What previous poster said, plus because Dijkstra has no heuristic and at each step picks edges with smallest cost it tends to "cover" more of your graph. Because of that Dijkstra could be more useful than A*. Good example is when you have several candidate target nodes, but you don't know, which one is closest (in A* case you would have to run it multiple times: once for each candidate node).
ttvd
2009-08-26 05:45:10
If there are several potential goal nodes, one could simply change the goal testing function to include them all. This way, A* would only need to be run once.
Bradford Larsen
2010-04-04 02:11:14
+1
A:
Dijkstra's algorithm would never be used for pathfinding. Using A* is a no-brainer if you can come up with a decent heuristic (usually easy for games, especially in 2D worlds). Depending on the search space, Iterative Deepening A* is sometimes preferable because it uses less memory.
Shaggy Frog
2009-08-26 05:45:11
Why would Dijkstra's never be used for pathfinding? Can you elaborate?
KingNestor
2009-08-26 05:47:15
Because even if you can come up with a lousy heuristic, you'll do better than Dijkstra. Sometimes even if it's inadmissible. It depends on the domain. Dijkstra also won't work in low-memory situations, whereas IDA* will.
Shaggy Frog
2009-08-26 05:59:32
Check out the slides at http://www.cs.ualberta.ca/~jonathan/Courses/657/Notes/10.Single-agentSearch.pdf
Shaggy Frog
2009-08-26 06:00:31
A:
Dijkstra algorithm finds the shortest path definitely. On the other hand A* depends on the heuristic. For this reason A* is faster that A* and give good results if you have a good heuristic.
Hani
2009-09-20 03:40:58
A* gives the same results as Dijkstra, but faster when you use a good heuristic. A* algorithm imposes some conditions for to work correctly such as the estimated distance between current node and the final node should be lower than the real distance.
Alexandru
2009-11-15 22:36:45
A* is guaranteed to give the shortest path when the heuristic is admissible (always underestimates)
Robert
2010-05-22 23:14:48
A:
Dijkstra finds the minimum costs from the starting node to all others. A* finds the minimum cost from the start node to the goal node.
Therefore it would seem that Dijkstra would be less efficient when all you need is the minimum distance from one node to another.
Robert
2010-05-22 23:19:34