Performance of Thorup's Shortest Path Algorithm for Large-Scale Network Simulation

Yusuke SAKUMOTO  Hiroyuki OHSAKI  Makoto IMASE  

Publication
IEICE TRANSACTIONS on Communications   Vol.E95-B   No.5   pp.1592-1601
Publication Date: 2012/05/01
Online ISSN: 1745-1345
DOI: 10.1587/transcom.E95.B.1592
Print ISSN: 0916-8516
Type of Manuscript: PAPER
Category: Fundamental Theories for Communications
Keyword: 
SSSP (single-source shortest path problem),  large-scale network simulation,  Dijkstra's algorithm,  Thorup's algorithm,  

Full Text: PDF(1.2MB)
>>Buy this Article


Summary: 
In this paper, we investigate the performance of Thorup's algorithm by comparing it to Dijkstra's algorithm for large-scale network simulations. One of the challenges toward the realization of large-scale network simulations is the efficient execution to find shortest paths in a graph with N vertices and M edges. The time complexity for solving a single-source shortest path (SSSP) problem with Dijkstra's algorithm with a binary heap (DIJKSTRA-BH) is O((M + N) log N). An sophisticated algorithm called Thorup's algorithm has been proposed. The original version of Thorup's algorithm (THORUP-FR) has the time complexity of O(M + N). A simplified version of Thorup's algorithm (THORUP-KL) has the time complexity of O(M α(N) + N) where α(N) is the functional inverse of the Ackerman function. In this paper, we compare the performances (i.e., execution time and memory consumption) of THORUP-KL and DIJKSTRA-BH since it is known that THORUP-FR is at least ten times slower than Dijkstra's algorithm with a Fibonaccii heap. We find that (1) THORUP-KL is almost always faster than DIJKSTRA-BH for large-scale network simulations, and (2) the performances of THORUP-KL and DIJKSTRA-BH deviate from their time complexities due to the presence of the memory cache in the microprocessor.