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.
