Improvement of Thorup Shortest Path Algorithm by Reducing the Depth of a Component Tree
In this paper, the authors 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, they propose a faster algorithm based on their work. Their 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.