Practical efficiency of the linear-time algorithm for the single source shortest path problem

Thorup's linear-time algorithm for the Single Source Shortest Path problem consists of two phases: a construction phase of constructing a data structure suitable for a shortest path search from a given query source s; and a search phase of finding shortest paths from the query source s to all vertices using the data structure constructed in construction phase. Since once the data structure is constructed, it can be repeatedly used for shortest path searches from given query sources, Thorup's algorithm has a nice feature not only on its linear time complexity but also on its data structure suitable for a repetitive mode of queries (not single query). In this paper, we evaluate the practical efficiency of the Thorup's linear-time algorithm through computational experiments comparing with some of well known previous algorithms. In particular, we evaluate Thorup's algorithm mainly from the point of repetitive mode of queries of view.