A note on the partitioning shortest path algorithm

Recently Glover, Klingman and Phillips 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 Schneider, they proposed several variants of the PSP and conducted computational tests. Three of the variants were the first polynomially bounded shortest path algoriths to maintain sharp labels as defined by Shier and Witzgall. Two of these variants had computational complexity O(|N|²|A|), the other O(|N|³). 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|³) for two of them and O(|N|²) for the other. This new step also provides a test for the early detection of negative length cycles.