What is the essential difference between A and Dijkstra's shortest path algorithm? From what I can understand, A is directed while Dijkstra is not. I can also think of Dijkstra's as the cheapest first. Are they any other differences I am missing? |
A star is a general pseudo-formal formulation for defining greedy algorithms. For a real formal, mathematical definition, you have the Matroids Djikstra is a greedy algorithm, so technically you can implement it using an A star approach, or you can just use your own implementation of a greedy algorithm. A star is just a method, it's not an end. It's a container for any greedy algorithm. |
A*
This is what makes up the elements of answered 21 Oct '11, 08:42 GeekDownUnder |
Actually, Dijkstra is a particular case of A* with the heuristic h set to always return 0. answered 16 Oct '11, 07:05 |
There are some cool little animations onthe wikipedia page for this http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm AND answered 16 Oct '11, 07:28 Merlin |