Shortest Path Algorithms: Engineering Aspects

Abstract. We review shortest path algorithms based on the multi-level bucket data structure [6] and discuss the interplay between theory and engineering choices that leads to efficient implementations. Our experimental results suggest that the caliber heuristic [17] and adaptive parameter selection give an efficient algorithm, both on typical and on hard inputs, for a wide range of arc lengths