DocumentCode
2139224
Title
An improved Thorup shortest paths algorithm with a modified component tree
Author
Yusi Wei ; Tanaka, Shoji
Author_Institution
Interdiscipl. Grad. Sch. of Sci. & Eng., Shimane Univ., Matsue, Japan
fYear
2013
fDate
23-25 July 2013
Firstpage
1160
Lastpage
1165
Abstract
This paper provides an improved Thorup algorithm which modified the component tree of the original Thorup algorithm to make it able to maintain the tentative distance of each vertex without the unvisited structure. According to the experimental result, our algorithm showed a better result than the original Thorup algorithm and Fibonacci-based Dijkstra algorithm in practice. By comparison, the time cost of query is reduced by 75.04% and 58.26%, respectively.
Keywords
trees (mathematics); Fibonacci-based Dijkstra algorithm; improved Thorup shortest path algorithm; modified component tree; tentative distance; Algorithm design and analysis; Arrays; Educational institutions; Indexes; Periodic structures; Dijkstra; Single-Source Shortest Path; Undirected Weights;
fLanguage
English
Publisher
ieee
Conference_Titel
Natural Computation (ICNC), 2013 Ninth International Conference on
Conference_Location
Shenyang
Type
conf
DOI
10.1109/ICNC.2013.6818153
Filename
6818153
Link To Document