• Jul 03, 2017 News!JACN Vol.4, No.2 has been indexed by EI (inspec)!   [Click]
  • Jul 12, 2017 News!JACN Vol.5, No.1 has been published with online version.
  • Jul 03, 2017 News!Welcome to join in the 2017 8th International Conference on Networking and Information Technology (ICNIT 2017), which will be held in Penang, Malaysia during November 24-26, 2017.
General Information
    • ISSN: 1793-8244
    • Frequency: Semiyearly
    • DOI: 10.18178/JACN
    • Editor-in-Chief: Dr. Ka Wai Gary Wong
    • Executive Editor: Ms. Nina Lee
    • Abstracting/ Indexing: EI (INSPEC, IET), Engineering & Technology Digital Library, DOAJ, Electronic Journals Library, Ulrich's Periodicals Directory, International Computer Science Digital Library (ICSDL), ProQuest, and Google Scholar.
    • E-mail: jacn@ejournal.net
Editor-in-chief
Dr. Ka Wai Gary Wong
Division of Information and Technology Studies, Faculty of Education, The University of Hong Kong.
It's a honor to serve as the editor-in-chief of JACN. I'll work together with the editors and reviewers to help the journal progress
JACN 2014 Vol.2(2): 142-146 ISSN: 1793-8244
DOI: 10.7763/JACN.2014.V2.99

Improvement of Thorup Shortest Path Algorithm by Reducing the Depth of A Component Tree

Yusi Wei and Shojiro Tanaka
Abstract—Wei and Tanaka have proposed a variant of the Thorup algorithm which showed a better result than the original Thorup algorithm and the Fibonacci-based Dijkstra algorithm in practice. In this paper, we propose a faster algorithm based on their work. Our new algorithm has a faster speed when visiting vertices, it is achieved by decreasing the depth of a component tree. The experimental result indicates, comparing to array-based Dijkstra, Fibonacci-based Dijkstra and the original Thorup algorithm, reduction by 7.5%, 72.9% and 85.6% of the time cost, respectively.

Index Terms—Dijkstra, single-source shortest path, thorup, undirected weights.

Yusi Wei is with the Information Systems Course, Interdisciplinary Graduate School of Science and Engineering, Shimane University, Matsue, Japan (e-mail: wayis@ live.com).
Shojiro Tanaka is with the Information Systems Division, Interdisciplinary Graduate School of Science and Engineering, Shimane University, Matsue, Japan(e-mail: tanaka@cis.shimane-u.ac.jp).

[PDF]

Cite:Yusi Wei and Shojiro Tanaka, "Improvement of Thorup Shortest Path Algorithm by Reducing the Depth of A Component Tree," Journal of Advances in Computer Networks vol. 2, no. 2, pp. 142-146, 2014.

Copyright © 2008-2017. Journal of Advances in Computer Networks.  All rights reserved.
E-mail: jacn@ejournal.net