Warp wrote:
> Invisible <voi### [at] devnull> 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