Contents

1 Problem Statement

Please refer to the tour the T problem on this page.

2 Analysis

This is an instance of the Traveling Salesman Problem. We can model the entire subway as a weighted graph G=(V,E) where V is a station and E is an edge connection two stations and w is the weight of the edge that represents the travel time between the two stations

3 Algorithm

• Build the weighted graph of the subway, while collecting those stations that are hubs connecting multiple lines. For example, Park St is a hub.
• Now find the minimum spanning tree and do a depth first traversal of the tree.
• Find the shortest path between the successive vertices sorted in depth first order. This will build a route that traverses all the stations at least once.
• Now on the route, find out the hubs where line has been changed and add the waiting time for such line changes.
• If your start station is not Kendall square, then find the shortest route between the penultimate station on the route and Kendall square, to build the final route.