An improved Thorup shortest paths algorithm with a modified component tree
Yusi Wei, Shojiro Tanaka · 2013
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.