SPT_L shortest path algorithms: review, new proposals and some experimental results

This paper presents in a unified framework the most efficient shortest path algorithms of the List class to highlight strategies for handling the candidate node set as well as issues related to the efficient implementation of such strategies. A deep analysis of the strategies which inspired two of the most robust algorithms for the shortest path tree problem, due to Tarjan and to Goldberg and Radzik, allows the proposal of some variants. A computational study of such variants is conducted on the same test problem families used in Cherkassky et al. 96, in order to validate “a posteriori” the implementation choices. The experimental data suggest that all of the new variants are robust in practice and, for each of the tested problem families, at least one of the new variants either improves the performance or performs as well as both benchmark algorithms.