Warp wrote:
> Invisible <voi### [at] dev null> wrote:
>> That doesn't *sound* very impressive... until you sit down and try to
>> think of a way to program such a thing yourself. How would you do that??
>
> 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. You can then read off the optimal path from the
initial node to any desired node - but surely computing the distance
function for every road in the country would be infeasible?
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.
Post a reply to this message
|