
For FullText PDF, please login, if you are a member of IEICE,
or go to Pay Per View on menu list, if you are a nonmember of IEICE.

Performance of Thorup's Shortest Path Algorithm for LargeScale Network Simulation
Yusuke SAKUMOTO Hiroyuki OHSAKI Makoto IMASE
Publication
IEICE TRANSACTIONS on Communications
Vol.E95B
No.5
pp.15921601 Publication Date: 2012/05/01
Online ISSN: 17451345
DOI: 10.1587/transcom.E95.B.1592
Print ISSN: 09168516 Type of Manuscript: PAPER Category: Fundamental Theories for Communications Keyword: SSSP (singlesource shortest path problem), largescale 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 largescale network simulations. One of the challenges toward the realization of largescale 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 singlesource shortest path (SSSP) problem with Dijkstra's algorithm with a binary heap (DIJKSTRABH) is O((M + N) log N). An sophisticated algorithm called Thorup's algorithm has been proposed. The original version of Thorup's algorithm (THORUPFR) has the time complexity of O(M + N). A simplified version of Thorup's algorithm (THORUPKL) 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 THORUPKL and DIJKSTRABH since it is known that THORUPFR is at least ten times slower than Dijkstra's algorithm with a Fibonaccii heap. We find that (1) THORUPKL is almost always faster than DIJKSTRABH for largescale network simulations, and (2) the performances of THORUPKL and DIJKSTRABH deviate from their time complexities due to the presence of the memory cache in the microprocessor.

