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

You're beginning to invent the A* algorithm there ;-)

http://en.wikipedia.org/wiki/A*

I assume in real life applications there is some custom algorithm with many 
additions and hacks based on knowledge of the road system (as opposed to 
applying this to say a computer network).  Also I assume that roads are 
classified into speed ratings, so first it checks for any nearby motorways 
at either end and then checks a route based on that, before fiddling with 
the end sections etc, I imagine it can be quite complex!

Post a reply to this message