So I was thinking after discussing with my friend the other day, how would I use something like breadth-first or depth-first search to find the fastest time to go from one station to another station if there are a number of different train lines in a subway system. They may cross over each other, maybe multiple times even.
Train line in this case means a train that goes from a starting station to a ending station, with many station stops on the way, where certain station stops may give the option for the rider to swap to another "line" that also has its starting and stoping station. A simple example is a two-line subway system like so:
o : station - : track Line 2 START | o | Line 1 START o -- o -- o -- o -- o -- o END | END
I live in Taipei, Taiwan, so you may reference the MRT train map there for reference but it may look fairly complicated. I was looking for tips for a simpler start and ways to work out a solution to a smaller problem first, but the MRT system is my friend and I's target goal.
What I have though of so far
- Have an array that holds each stop name on along with the time it takes for previous stop to reach this stop represent a single train line, with each connection to another train line being a nested array at that item.
- Figure out how to tell the algorithm to look through each route to find the destination stop, adding the time taken along the way comparing to find the shortest time.
Things to Consider
- The time between each station is known to us. But for the purpose of this question just assume its 5 minutes between each station.
- A train line has a starting stop and a ending stop, but on the way it may stop on a stop that connects to any other train line.
- Any connection to another train line may connect to another line - but access to this third line may be reached by taking a further more complicated route by switching train lines. Meaning if I try out all possibilities it may take looping routes and test forever.
- Its possible to take a transfer from one line to another, and go either left or right on the new line, i.e. the trains are not one-way.
So how is it possible to
Avoid our algorithm making loops, e.g.:
If line 1 connects to line 2 on its third stop, and that connects to a third line, and then back to line 1 later on down line 3. Then if we were to try find the shortest way to go from a stop in line 1 to another stop in line 1, the algorithm may test going from line 1 to line 2 taking the connection then to line 3 back to line 1 and back around.
And also, how do we make it decide where to make the turns, and what is a better way to represent this problem and find the shortest time?