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

I imagine it regards the road network as a "network of networks", 
similar to the way the high-level Internet routing protocols work.

As in, it probably attempts to construct a route on main roads only with 
endpoints "near" to the desired endpoints, and then attempts to augment 
that with the minor roads needed at each end. (Probably builds several 
possible motorway routes so it can find a reasonably optimal one.)

The selections like "prefer motorways" and "avoid motorways" probably 
adjust the internal cost function driving the algorithm. Of course, in 
terms of distance, Euclid straight-line distance is a pretty good 
estimate until you compute the actual road distances.

I wonder: Does it cost more to design a better routing algorithm, or fit 
a faster CPU? ;-)

Post a reply to this message