Improving Contraction Hierarchies by Combining with All-Pairs Shortest Paths Problem Algorithms

Contraction hierarchies (CH) is a two-phase effective shortest path algorithm for large-scale road networks based on node contraction. However, the remaining graphs tend to be complete near the end of preprocessing, which slows down the preprocessing speed. We combine CH with the all-pairs shortest paths (APSP) problem algorithms which are efficient on complete graphs, to propose a new method. Near the end of the CH preprocessing phase, we use the APSP algorithm to obtain a distance table that contains the shortest path between all remaining nodes. Query performs a bidirectional Dijkstra search combined with a table lookup. Experimental results show that our method achieves both preprocessing and query acceleration compared to the raw CH algorithm. It allows for parameter adjustment based on spatial requirements and can be interpreted as an interpolation between CH and APSP algorithms.