New Polynomial Shortest Path Algorithms and Their Computational Attributes

Fred Glover, Darwin D. Klingman, Nancy V. Phillips and Robert F. Schneider
Additional contact information
Fred Glover: School of Business, University of Colorado, Boulder, Colorado 80303
Darwin D. Klingman: Graduate School of Business, University of Texas, Austin, Texas 78712
Nancy V. Phillips: Graduate School of Business, University of Texas, Austin, Texas 78712
Robert F. Schneider: Graduate School of Business, University of Texas, Austin, Texas 78712

Management Science, 1985, vol. 31, issue 9, 1106-1128

Abstract: This paper presents six new variants of the polynomially bounded Partitioning Shortest Path (PSP) algorithm for finding the shortest path from one node to all other nodes in a network. Three of these variants, one for negative arc lengths, but without negative cycles, and two for nonnegative arc lengths, augment the PSP algorithm to maintain a property called sharp by Shier and Witzgall. The other three variants augment the PSP algorithm to maintain a property called near-sharp for nonnegative arc lengths. Extensive computational testing is presented on one of the sharp variants for nonnegative arc lengths and two of the near-sharp variants. The empirical results based on 4500 test problems with 90 different configurations and three different network topologies indicate that these new algorithms have excellent computational performance characteristics. Based on total solution times for the 4500 test problems, these new algorithms out-perform all other algorithms tested. In addition, one of the near-sharp algorithms strictly dominates all others on all problem topologies tested.

Keywords: shortest; path; algorithms (search for similar items in EconPapers)
Date: 1985
References: Add references at CitEc
Citations: View citations in EconPapers (4)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.31.9.1106 (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:ormnsc:v:31:y:1985:i:9:p:1106-1128

Access Statistics for this article

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