This is an algorithm that finds optimal-time routes in public transit networks. It is designed to be fast; on a 2.16GHz Core 2, a typical problem for a medium-sized city can be solved in about 0.1s.

Introduction:

Many well-known graph search algorithms have been invented, including Dijkstra and A*. Most research has been directed toward traditional graphs where one may “travel” along edges at will. However, there exists a set of problems involving graph-like structures where one may only travel from one vertex to another according to a well-defined schedule. One practical example is planning trips via buses and trains in a public transportation network. This paper addresses the problem of optimal-time path planning in schedule-based graphs.

The paper can be downloaded as a PDF.

Source code is also available that implements this algorithm using schedule data in GTFS form. It's very experimental so contact me if you would like a copy.