Roland Perry

In message <487e7030$0$2520$da0feed9@news.zen.co.uk>, at 23:03:28 on
Wed, 16 Jul 2008, Tim Greening-Jackson
<zen167520_AT_zen_co_uk@?.?.invalid> remarked:
>I presume, though, that the push to calculate the distances at that
>time was either due to the modernisation programme or -- perhaps more
>prosaically -- due to the fact that the means to calculate them (LEO)
>had just come to hand.
>
>From my calculation, to calculate the distances between 7,000 separate
>places would require 24,500,000 calculations. So a computer -- even one
>with only 2,048 words of store like LEO would be attractive.

If trying to solve the problem by brute force, then you'll get a very
large number of calculations required. But there are many very simple
ways to optimise the search - although some of the techniques were still
in the research labs when I was at college in 1970.

The most obvious optimisation is to abandon the route you are exploring
as soon as the mileage exceeds your currently discovered minimum. eg If
you've already discovered that Waterloo-Portsmouth is no more than 73
miles via Haselemere, you abandon any alternative route (perhaps via
Basingstoke) as soon as it exceeds 73 miles. viz At Eastleigh which is
also 73 miles from London.

In practice you can truncate the process even quicker by working
backwards from the destination as well (you won't find any shorter route
from London to Portsmouth Harbour than starting from the already known
shortest route from London to Hilsea).
--
Roland Perry