New polynomial shortest path algorithms and their computational attributes. (English) Zbl 0609.90103

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.


90C35 Programming involving graphs or networks
68Q25 Analysis of algorithms and problem complexity
65K05 Numerical mathematical programming methods
05C35 Extremal problems in graph theory
Full Text: DOI