A note on the partitioning shortest path algorithm (Q1101020): Difference between revisions

Recently \textit{F. Glover, D. Klingman} and \textit{N. Phillips} [Oper. Res. 33, 65-73 (1985; Zbl 0578.90089)] proposed the Partitioning Shortest Path (PSP) algorithm. The PSP algorithm includes as variants most of the known algorithms for the shortest path problem. In a subsequent paper, together with \textit{R. Schneider} [Manage. Sci. 31, 1106-1128 (1985; Zbl 0609.90103)], they proposed several variants of the PSP and conducted computational tests. Three of the variants were the first polynomially bounded shortest path algorithms to maintain sharp labels as defined by \textit{D. Shier} and \textit{C. Witzgall} [J. Res. Nat. Bur. Standards 86, 317-330 (1981)]. Two of these variants had computational complexity \(O(| N|^ 2| A|)\), the other \(O(| N|^ 3)\). In this note, we add a new step to the PSP algorithm resulting in new variants also scanning from sharp labels and having computational complexity \(O(| N|^ 3)\) for two of them and \(O(| N|^ 2)\) for the other. This new step also provides a test for the early detection of negative length cycles.