|
![](/i/fill.gif) |
>> As far as I can tell, Dijkstra's algorithm appears to visit *all* the
>> nodes of the graph.
>
> No, it doesn't. It starts advancing from the starting node towards all
> possible directions, and then follows those paths which are most promising
> (according to the sum of weights of those paths).
>
> In a way it's a kind of breadth-first search, where the weight of the
> paths searched so far is kept as equal as possible. It stops immediately
> when it reaches the end node (because it would, rather obviously, not make
> any sense to continue because the optimal path has already been found).
Ah. Wikipedia's article doesn't seem to mention a stopping condition
other than "all nodes have been visited".
Also, I ran the algorithm by hand with pencil and paper and it appeared
to give me a suboptimal route. I ran it for a bit longer and it became
optimal. I don't know if I misunderstood the algorithm or just made a
trivial mistake in running it.
> Dijkstra's algorithm doesn't need any cutoff. It starts advancing in a
> breadth-first order (according to the sum of weights of the paths) and
> when it reaches the end node, it has found the optimal path.
Any idea how the A* algorithm is better than Dijkstra's 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...
Post a reply to this message
|
![](/i/fill.gif) |