The problem of finding the shortest path in a transit network, such as a municipal bus system, is somewhat different from that of finding the shortest path in a road system. In a transit system, buses and trains have routes and transfer points, leading to a different path space that must be explored to find the shortest path.

This paper first describes the nature of the problem, and defines necessary terms. The word “pattern,” for example, is used for a route in the sense used above. The paper then describes an algorithm for finding the fastest path between nodes. There are three steps in the algorithm: Dijkstra’s algorithm is used to obtain a weighted quickest path, which is used to bound the search in the two subsequent phases; a backward search; and, finally, a heuristic-based forward sweep.

The author shows that the algorithm does determine the shortest path, provided that the destination node is selected during the forward sweep. The algorithm is illustrated with an example. The author discusses the worst-case cost of the algorithm; however, in practice this is unlikely. The author provides actual results based on the Milwaukee County transit system and the Waukesha transit system, and shows that the performance is acceptable. The result is an interesting variation on a classic problem.