Shortest Path Algorithms: An Evaluation Using Real Road Networks

F. Benjamin Zhan and Charles E. Noon
Additional contact information
F. Benjamin Zhan: Department of Geography and Planning, Southwest Texas State University, San Marcos, Texas 78666
Charles E. Noon: Management Science Program, The University of Tennessee, Knoxville, Tennessee 37996

Transportation Science, 1998, vol. 32, issue 1, 65-73

Abstract: The classic problem of finding the shortest path over a network has been the target of many research efforts over the years. These research efforts have resulted in a number of different algorithms and a considerable amount of empirical findings with respect to performance. Unfortunately, prior research does not provide a clear direction for choosing an algorithm when one faces the problem of computing shortest paths on real road networks. Most of the computational testing on shortest path algorithms has been based on randomly generated networks, which may not have the characteristics of real road networks. In this paper, we provide an objective evaluation of 15 shortest path algorithms using a variety of real road networks. Based on the evaluation, a set of recommended algorithms for computing shortest paths on real road networks is identified. This evaluation should be particularly useful to researchers and practitioners in operations research, management science, transportation, and Geographic Information Systems.

Date: 1998
References: View complete reference list from CitEc
Citations: View citations in EconPapers (27)

Downloads: (external link)
http://dx.doi.org/10.1287/trsc.32.1.65 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ortrsc:v:32:y:1998:i:1:p:65-73

Access Statistics for this article

More articles in Transportation Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().