Members don't see the ad below. Register now!

# Difference between A* and Dijkstra's shortest path algorithm?

 0 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? asked 16 Oct '11, 06:46 Vaidhy 21●1●4 Maxim 1.5k●1●12

 1 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. answered 16 Oct '11, 07:39 lrq3000 2.0k●3●17 Merlin 4.2k●5●13●27
Members don't see the ad. Register now!
 2 A* (f) uses two algorithms to balance each other: (g) - Favouring paths closest to start point (Dijkstra's shortest path) (h) - Favouring paths closest to end point (Best First Search) This is what makes up the elements of f(n) = g(n) + h(n). Therefore if your h=0, then f(n) becomes g(n) or it becomes Dijkstra's algorithm. If your h='arbitrarily large number' then g(n) essentially gets ignored due to scale and A becomes Best First Search. By having a heuristic that is admissible and at the same scale as the path cost, it gives A the power to balance them both out and make a fast directed shortest path algorithm! answered 21 Oct '11, 08:42 GeekDownUnder 1.1k●8
 0 Actually, Dijkstra is a particular case of A* with the heuristic h set to always return 0. answered 16 Oct '11, 07:05
 0 There are some cool little animations onthe wikipedia page for this http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm AND http://en.wikipedia.org/wiki/A-star_algorithm answered 16 Oct '11, 07:28 Merlin 4.2k●5●13●27
 toggle preview community wiki