>> 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