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's gravatar image


retagged 21 Oct '11, 05:19

Maxim's gravatar image


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's gravatar image


edited 16 Oct '11, 07:49

Merlin's gravatar image


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's gravatar image


Actually, Dijkstra is a particular case of A* with the heuristic h set to always return 0.


answered 16 Oct '11, 07:05

Cristian%20Dinu's gravatar image

Cristian Dinu

There are some cool little animations onthe wikipedia page for this





answered 16 Oct '11, 07:28

Merlin's gravatar image


edited 16 Oct '11, 07:29

Your answer
toggle preview

Follow this Question via Email

Once you sign in you will be able to subscribe for any updates here

Q&A Editor Basics

  • to upload an image into your question or answer hit
  • to create bulleted or numbered lists hit or
  • to add a title or header hit
  • to section your text hit
  • to make a link clickable, surround it with <a> and </a> (for example, <a>www.google.com</a>)
  • basic HTML tags are also supported (for those who know a bit of HTML)
  • To insert an EQUATION you can use LaTeX. (backslash \ has to be escaped, so in your LaTeX code you have to replace \ with \\). You can see more examples and info here