When I went to London, I wondered how to visit all the London Underground stations as fast as possible.
- a randomly-chosen start station,
- timetable of train arriving & departing of every station,
- the time it takes to change from one to another line.
Assuming that there is no Tube strike on that day, and trains run on time, what is the best route to visit all the London Tube stations? (By visiting, just passing the station while being on the train counts.)
I've tried breaking the problem down to a smaller size and computing all possible routes, but that'd take ages to run with all 270 stations.
So, could you guys give me some ideas how to do this better? Or if this something similar to this problem, could you please show me those?
What I've tried:
- I've Googled, and I found something like
optimum road trips, but it doesn't work with train stations that have interchanges.
- Took a look at
Dijkstra'sbut they give a tree as an answer which ignores loops.