Skip to content

A k-shortest routes algorithm for urban public transportation network

Notifications You must be signed in to change notification settings

wlxiong/k_shortest_bus_routes

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

16 Commits
 
 
 
 
 
 

Repository files navigation

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.

About

A k-shortest routes algorithm for urban public transportation network

Topics

Resources

Stars

Watchers

Forks

Releases

No releases published

Packages

No packages published

Languages