As part of The Fantastic Race, teams need to travel on buses from city to city in the order Omicron to Pi to Rho to Sigma to Tau. Each city has several different bus stations to choose from. Nate has created the following map showing all the different bus routes between the five cities, as well as the travel time, in minutes, for each. The different bus stations within each city are labeled \(\text{A}\), \(\text{B}\), \(\text{C}\), etc.
Which route from Omicron to Tau gives the shortest total travel time?
This problem was inspired by a past Beaver Computing Challenge (BCC) problem.
The shortest total travel time is \(130\) min, and can be achieved with the following route: Omicron \(\text{(D)}\) \(\rightarrow\) Pi \(\text{\(\text{(C)}\)}\) \(\rightarrow\) Rho \(\text{(A)}\) \(\rightarrow\) Sigma \(\text{(D)}\) \(\rightarrow\) Tau \(\text{(A)}\).
In order to find this route, we use a method called dynamic programming. In dynamic programming, we systematically build the solution from small pieces to bigger and bigger pieces. This saves us a significant amount of time because we don’t have to calculate the total travel time for every possible route.
We start by looking at the routes from Omicron to Pi, and determine the route with the shortest travel time to each of the bus stations in Pi. We will call these the "best" routes. The best route to reach Pi \(\text{(A)}\) takes \(27\) min and comes from Omicron \(\text{(A)}\). The only route to reach Pi \(\text{(B)}\) takes \(63\) min and comes from Omicron \(\text{(B)}\). The best route to reach Pi \(\text{(C)}\) takes \(45\) min and comes from Omicron \(\text{(D)}\). The only route to reach Pi \(\text{(D)}\) takes \(27\) min and comes from Omicron \(\text{(D)}\). We then ignore all other routes from Omicron to Pi.
Next we look at the routes from Omicron to Rho, using the information we just recorded. The best route to reach Rho \(\text{(A)}\) takes \(45 + 27 = 72\) min and comes from Pi \(\text{(C)}\). The best route to reach Rho \(\text{(B)}\) takes \(63 + 18 = 81\) min and comes from Pi \(\text{(B)}\). The best route to reach Rho \(\text{(C)}\) takes \(45 + 35 = 80\) min and comes from Pi \(\text{(C)}\).
Next we look at the routes from Omicron to Sigma, using the information we just recorded. The best route to reach Sigma \(\text{(A)}\) takes \(72 + 10 = 82\) min and comes from Rho \(\text{(A)}\). The best route to reach Sigma \(\text{(B)}\) takes \(81 + 25 = 106\) min and comes from Rho \(\text{(B)}\). The best route to reach Sigma \(\text{(C)}\) takes \(81 + 34 = 115\) min and comes from Rho \(\text{(B)}\). The best route to reach Sigma \(\text{(D)}\) takes \(72 + 36 = 108\) min and comes from Rho \(\text{(A)}\). The best route to reach Sigma \(\text{(E)}\) takes \(80 + 51 = 131\) min and comes from Rho \(\text{(C)}\).
Finally, we look at the routes from Omicron to Tau, using the information we just recorded. The best route to reach Tau \(\text{(A)}\) takes \(108 + 22 = 130\) min and comes from Sigma \(\text{(D)}\). The best route to reach Tau \(\text{(B)}\) takes \(108 + 25 = 133\) min and comes from Sigma \(\text{(D)}\).
Thus, the shortest total travel time is \(130\) min, and is achieved with
the route
Omicron \(\text{(D)}\) \(\rightarrow\) Pi \(\text{(C)}\)
\(\rightarrow\) Rho \(\text{(A)}\) \(\rightarrow\) Sigma \(\text{(D)}\) \(\rightarrow\) Tau \(\text{(A)}\).