Finding the shortest time to go from one stop to another stop in a train system with many train lines with connection stations 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?
Transform your input to a graph in which each vertex represents a stop on a line. If a stop is shared by multiple lines, then add one copy of the vertex per line and a new super-vertex connected to all such copies with edges of weight 2.5 (so there is a path of length 5 between any two of these stops). Add edges between consecutive stops of the same line with weights matching the travel times.

Use Dijkstra's algorithm to find the shortest path between the starting stop and the last stop.

The time required is $O(n\log n)$ where $n$ is the overall number of (not necessarily distinct) stops across the different lines. This is because is possible to assign edges to vertices so that: 1) each edge is assigned to a "stop" vertex, and 2) each "stop" vertex has at most $2$ edges assigned (i.e., the one towards the "next" stop w.r.t. an arbitrary direction of the line the vertex belongs to, if any, and possibly the one to a super-vertex), showing that the number of edges is at most $2n$.

EDIT:

Here is the graph obtained by applying the above transformation to the example in the question.
The edges of the horizontal line are in red, those of the vertical line are in blue. All the vertices representing stops on a specific line are white, while the only super-vertex is in black. Black edges have a weight of $2.5$ each (not shown). The tree vertices in the gray circle together represent the stop at the intersection of the horizontal line and vertical line.