Invisible <voi### [at] devnull> wrote:
> Any idea how the A* algorithm is better than Dijkstra's algorithm?

  Dijkstra's algorithm doesn't use any heuristic and thus probably may
expand more nodes than A*. As wikipedia puts it:

"Generally speaking, depth-first search and breadth-first search are
two special cases of A* algorithm. Dijkstra's algorithm, as another
example of a best-first search algorithm, is the special case of A*
where h(x) = 0 for all x." (h(x) is the heuristic function given to
the A* algorithm.)

> I was working under the assumption that Dijkstra's algorithm visits all 
> the nodes of the graph and A* doesn't need to - but if that isn't the 
> case, I'm left wondering how A* is actually better...

  I don't know if it's completely correct analogy, but I think you could
think that A* is a bit like Dijkstra's, but using a heuristic function to
discard nodes more efficiently. A* seems to also be more generic, in that
you can make it perform other types of searches besides pure breadth-first.

-- 
                                                          - Warp

Post a reply to this message