A New Polynomially Bounded Shortest Path Algorithm
- 1 February 1985
- journal article
- Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research
- Vol. 33 (1) , 65-73
- https://doi.org/10.1287/opre.33.1.65
Abstract
This paper develops a new polynomially bounded shortest path algorithm, called the partitioning shortest path (PSP) algorithm, for finding the shortest path from one node to all other nodes in a network containing no cycles with negative lengths. This new algorithm includes as variants the label setting algorithm, many of the label correcting algorithms, and the apparently computationally superior threshold algorithm.Keywords
This publication has 0 references indexed in Scilit: