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

Yusuke SAKUMOTO; Hiroyuki OHSAKI; Makoto IMASE

doi:10.1587/transcom.E95.B.1592

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

Yusuke SAKUMOTO, Hiroyuki OHSAKI, Makoto IMASE

Full Text Views

0

Cite this

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.

Publication: IEICE TRANSACTIONS on Communications Vol.E95-B No.5 pp.1592-1601

Publication Date: 2012/05/01

Publicized

Online ISSN: 1745-1345

DOI: 10.1587/transcom.E95.B.1592

Type of Manuscript: PAPER

Category: Fundamental Theories for Communications

Cite this

Copy

Yusuke SAKUMOTO, Hiroyuki OHSAKI, Makoto IMASE, "Performance of Thorup's Shortest Path Algorithm for Large-Scale Network Simulation" in IEICE TRANSACTIONS on Communications, vol. E95-B, no. 5, pp. 1592-1601, May 2012, doi: 10.1587/transcom.E95.B.1592.
Abstract: 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.
URL: https://global.ieice.org/en_transactions/communications/10.1587/transcom.E95.B.1592/_p

Copy

@ARTICLE{e95-b_5_1592,
author={Yusuke SAKUMOTO, Hiroyuki OHSAKI, Makoto IMASE, },
journal={IEICE TRANSACTIONS on Communications},
title={Performance of Thorup's Shortest Path Algorithm for Large-Scale Network Simulation},
year={2012},
volume={E95-B},
number={5},
pages={1592-1601},
abstract={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.},
keywords={},
doi={10.1587/transcom.E95.B.1592},
ISSN={1745-1345},
month={May},}

Copy

TY - JOUR
TI - Performance of Thorup's Shortest Path Algorithm for Large-Scale Network Simulation
T2 - IEICE TRANSACTIONS on Communications
SP - 1592
EP - 1601
AU - Yusuke SAKUMOTO
AU - Hiroyuki OHSAKI
AU - Makoto IMASE
PY - 2012
DO - 10.1587/transcom.E95.B.1592
JO - IEICE TRANSACTIONS on Communications
SN - 1745-1345
VL - E95-B
IS - 5
JA - IEICE TRANSACTIONS on Communications
Y1 - May 2012
AB - 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.
ER -