A new polynomially bounded shortest path algorithm. (English) Zbl 0578.90089

Summary: 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.


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