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

Vaidhy
2114

retagged 21 Oct '11, 05:19

Maxim's gravatar image

Maxim
1.5k112


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.

link

answered 16 Oct '11, 07:39

lrq3000's gravatar image

lrq3000
2.0k521

edited 16 Oct '11, 07:49

Merlin's gravatar image

Merlin
4.2k51430

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!

link

answered 21 Oct '11, 08:42

GeekDownUnder's gravatar image

GeekDownUnder
1.1k9

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

link

answered 16 Oct '11, 07:05

Cristian%20Dinu's gravatar image

Cristian Dinu
1

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

link

answered 16 Oct '11, 07:28

Merlin's gravatar image

Merlin
4.2k51430

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