How do I do list traversal?

Question

I've recently started a project that involves using data from a London Ungerground dataset, in order to find routes that are n amount of minutes from a given station.

So far I have been able to parse in the data from the dataset, and create possible routes between each station. I have now a list of route objects which have the following properties:

Parent - the first station
Child - the next linked station
Line - whichever line the station is on
Time - the time between the two stations

The data I currently have, using VICTORIA as a starting station is:

i've formatted my output to make it easier to read, but each line is a representation of a route object. So you have the starting station, the time, the next station, and the line.

VICTORIA => 1 <= PIMLICO : Victoria
VICTORIA => 2 <= GREEN PARK : Victoria
VICTORIA => 2 <= ST JAMES PARK : Circle
VICTORIA => 2 <= SLOANE SQUARE : Circle
PIMLICO => 2 <= VAUXHALL : Victoria
GREEN PARK => 2 <= OXFORD CIRCUS : Victoria
GREEN PARK => 1 <= WESTMINSTER : Jubilee
GREEN PARK => 2 <= BOND STREET : Jubilee
GREEN PARK => 1 <= PICCADILLY CIRCUS : Piccadilly
GREEN PARK => 1 <= HYDE PARK CORNER : Piccadilly
ST JAMES PARK => 1 <= WESTMINSTER : Circle
SLOANE SQUARE => 1 <= SOUTH KENSINGTON : Circle
VAUXHALL => 2 <= STOCKWELL : Victoria
VAUXHALL => 2 <= PIMLICO : Victoria
OXFORD CIRCUS => 1 <= PICCADILLY CIRCUS : Bakerloo
OXFORD CIRCUS => 2 <= REGENTS PARK : Bakerloo
OXFORD CIRCUS => 2 <= TOTTENHAM COURT ROAD : Central
OXFORD CIRCUS => 1 <= BOND STREET : Central
OXFORD CIRCUS => 2 <= GREEN PARK : Victoria
OXFORD CIRCUS => 1 <= WARREN STREET : Victoria

What would be the best method to gather all the possible routes, from VICTORIA?

For example:

VICTORIA > GREEN PARK > WESTMINSTER
VICTORIA > GREEN PARK > BOND STREET
VICTORIA > PIMLICO > VAUXHALL

Answer 1

Sounds like a Graph Theory problem. My favorite!

The problem with finding "all possible routes" is that, with the data you've given (or any realistic dataset in this situation), you're going to encounter loops. Therefore, for any given route, you're going to need to make sure that each station is visited only once.

Since you have a single starting point, I would recommend Djikstra's Alogrithm. This will find a path (actually, the shortest path) from VICTORIA to every other station. At least, every other station that is reachable. This is a well-known, fast, and relatively easy to implement algorithm. Runs in O(n^2) time normally, but can be massaged into O(m + nlogn) with some data structure jimmying.

Hopefully that at least gets you on the right track!