Fastest Shortest Path Algorithms on Road Networks

This page contains information about Professor Benjamin Zhan's work on shortest path algorithms and information about the recommended fastest shortest path algorithms on road networks.  In addition to the algorithm itself, one key issue in designing and implementing a fast shortest path algorithm is the utilization of an effective data structure to represent networks in a computer.  Past research indicates that the forward-star representation is one of the best data structures for representing a network.  A detailed description of the forward-star representation can be found in NCGIA Core Curriculum in GIScience -- Unit 064 Representing Networks.

A second key issue in designing and implementing a fast shortest path algorithm is the data structure used to manage the "labeled (but not scanned) nodes."  Dr. Zhan's article titled "Three Fastest Shortest Path Algorithms on Real Road Networks: Data Structures and Procedures" provides a detailed summary about the most effective data structures (to date) that can be used for managing labeled nodes.  A set of recommended fastest shortest path algorithms on road networks and the evaluation procedures used to identify this set of algorithms are described in an article by Drs. Zhan and Noon in their Transportation Science article titled "Shortest Path Algorithms: An Evaluation Using Real Road Networks" (Transportation Science 32(1): 65-73, 1998). 

You may find the C source codes of these shortest path algorithms from Dr. Andrew Goldberg's Network Optimization Library. If you desire to have the data sets that Dr. Zhan used for the evaluation of shortest path algorithms on road networks, then please send him an email at: zhan@txstate.edu. 

References