On the Effectiveness of Thorup´s Shortest Path Algorithm for Large-Scale Network Simulation

An efficient solution for a single-source problem called Thorup´s algorithm has been proposed, whose computational complexity, O(N), is smaller than that of Dijkstra´s algorithm, O(N log N). In this paper, we compare the performance of Dijkstra´s algorithm and Thorup´s algorithm for large-scale network simulation. Through extensive experiments, we show that Thorup´s algorithm is slightly faster with approximately 30% larger memory consumption than Dijkstra´s algorithm for a large-scale network simulation, although difference in Dijkstra´s and Thorup´s algorithms is not so significant.