Invisible <voi### [at] devnull> wrote:
> >   Not all roads have the same weight. Some of them are marked as being
> > more desirable than others. After that it's just a question of running
> > an algorithm like http://en.wikipedia.org/wiki/Dijkstra's_algorithm

> 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). It
actually works even if all the arcs between nodes have the same weight, but
of course then there's no "most promising" path which would take priority.
However, even in this case it will not search through *all* nodes: It will
perform a pure breadth-first search and stop when it has found the shortest
path to the end node.

> I guess if you know "approximately" what the optimal distance ought to 
> be, you can just ignore any node that's further away then that or 
> something... You're still computing quite a lot of data though.

  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.

-- 
                                                          - Warp

Post a reply to this message