wlxiong/k_shortest_bus_routes

A k-shortest routes algorithm for urban public transportation network

Summary

The k-shortest transit paths algorithm contains two parts. The first part computes the least transfer times matrix, which provides a heuristic value to the second part, the k-shortest transit paths searching.

An revised Bellman-Ford algorithm is implemented to search the first k shortest paths from one source to all the other destinations. The algorithm is implemented and tested with a real world transit network including more than 500 lines and 4000 stops.

Here is a note on Dijkstra's algorithm and priority queue. Dijkstra's algorithm is not the core of my algorithm (only used to calculate the heuristic value), but someone asked me about the implementation. So I post this note in the wiki page.

Publication

Liyuan Zhao, Yiliang Xiong, and Hong Sun. The K Shortest Transit Paths Choosing Algorithm in Stochastic Transit Network. Lecture Notes in Computer Science, Vol. 5009 (2008), pp. 747--754, Fulltext.