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.
MSC:
90C35 | Programming involving graphs or networks |
68Q25 | Analysis of algorithms and problem complexity |
05C35 | Extremal problems in graph theory |