Building a Shanghai Metro Transfer Planner with Dijkstra’s Algorithm

Data Acquisition

The code repository includes a MetroRequester module that connects to the official Shanghai Metro website and downloads all station information. The function request_shanghai_metro_data() returns a StationManager (containing 344 stations and their line memberships) and a LineManager (describing line‑to‑station relationships).

Graph Representation

Stations are abstracted as vertices and the number of stations between two vertices as edge weights. A two‑dimensional adjacency matrix v_matrix stores these weights; a value of 9999 (or infinity) indicates no direct connection. The matrix enables the algorithm to compute shortest paths for both directly reachable stations and those requiring transfers.

Dijkstra Algorithm

Dijkstra’s algorithm is used to relax edges and find the minimal number of stations from a source vertex to all others. The distance array dis is initialized with the first column of the adjacency matrix. By repeatedly selecting the vertex with the smallest tentative distance and relaxing its outgoing edges, the algorithm discovers shorter routes such as reducing the distance from 徐家汇 to 汉中路 from 7 to 5 stations.

Implementation Details

To retain actual transfer paths, each matrix element stores a Route object whose stops field holds the station count (or 9999 for no direct route). The dis array holds a map from distance to a list of possible Route instances, allowing enumeration of all viable transfer sequences. Example output shows a route from 徐家汇 to 上海科技馆 via 11号线 and 2号线 with a total of 10 stations.

Optimization with Transfer Bias

Pure Dijkstra may favor routes with fewer stations but more transfers, which is unrealistic. A bias value (e.g., 3) is added to the edge weight whenever a transfer occurs, effectively treating a transfer as equivalent to three stations. This adjustment makes direct routes preferable when the station savings do not outweigh the transfer penalty, producing more practical itineraries.

Conclusion

The resulting system can generate realistic metro transfer plans, and the same principles can be extended to locate the nearest stations or other geographic queries, as discussed in the author’s earlier GeoHash article.