On Mon, 05 Jun 2006 23:56:38 +0100, Tristan Miller wrote:

What about the easier problem of the shortest journey where every *line* is
visited? That is, what is the shortest journey such that the traveller
uses some portion of each of the Bakerloo, Central, Circle, District, East
London, Hammersmith & City, Jubilee, Metropolitan, Northern, Picadilly,
Victoria, and Waterloo & City lines at least once?

There is admittedly some ambiguity here, since we can define "shortest" and
"visit" each in three different ways. Shortest can mean (a) least time,
(b) least distance, or (c) least number of station stops. (In the case of
(c), no walking between stations is permitted, or else the problem is
trivial.) And for a particular line to be "visited", we could say that
the traveller either (1) travelled on that line's train between at least
two stops on that line,

http://www.geofftech.co.uk/tubechall...sshortesttime/

(2) travelled on a different line's train between
at least two stops on that line, or (3) set foot in or passed through a
station where that line stops.

For example, here's one journey which attempts to satisfy definitions
(c.3), though I don't know if it's really the shortest:

1. King's Cross St. Pancras (Victoria, Northern, Hammersmith, Circle,
Metropolitan, Picadilly) to Whitechapel (East London, District) on the
Hammersmith & City Line: 6 stops, including Liverpool Street (Central)

2. Whitechapel to Liverpool Street on the Hammersmith & City Line: 2 stops

3. Liverpool Street to Bank (Waterloo & City) on the Central Line: 1 stop

4. Bank to Waterloo (Jubilee, Bakerloo) on the Waterloo & City Line: 1 stop

This is a total of 10 stops to visit all 12 LU lines. Can anyone find a
(c.3) route with less than 10 stops,

Jubilee from Canada Water to Baker Street does it in 8 stops with no
changes. (Probably the quickest.)

Starting at Green Park: Jubilee to Waterloo, W&C to Bank, Central to
Liverpool St, H&C to Whitechapel. That does it in 6.