A New Polynomially Bounded Shortest Path Algorithm
Fred Glover, Darwin D. Klingman, Nancy V. Phillips · Operations Research · 1985
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.