|
![](/i/fill.gif) |
Invisible <voi### [at] dev null> 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
|
![](/i/fill.gif) |