2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Will Floyd-Warshall all pair shortest path solve this problem? $\endgroup$ – asds_asds Oct 17 '19 at 10:54
2
$\begingroup$

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.

example

$\endgroup$
  • $\begingroup$ How does this make sure that even if there is a shorter path available if we change lines we stick to our longer path with no line changes. $\endgroup$ – asds_asds Oct 17 '19 at 13:18
  • $\begingroup$ It doesn't. Is that a constraint in the original post? I can't find it... $\endgroup$ – Steven Oct 17 '19 at 14:10
  • $\begingroup$ No that wasn't a requirement, and thanks for the answer. Is there a way to know where you made the "turns" or line swaps in the answer for the shortest time taken? $\endgroup$ – Kranti Nebhwani Oct 17 '19 at 15:28
  • $\begingroup$ The Dijkstra algorithm will not only return the distance from the starting station to the end station but also the shortest path $P$ itself. Then, if you look at $P$, you will swap lines every time the path encounters a super-vertex $v$. In particular, the vertex preceding $v$ will be on one line, and the vertex following $v$ will be on a different line. $\endgroup$ – Steven Oct 17 '19 at 15:32
  • 1
    $\begingroup$ I edited the post adding the graph resulting when the construction in the answer is applied to the example metro network in the question. HTH $\endgroup$ – Steven Oct 18 '19 at 9:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.