We study the point-to-point shortest path problem in a setting where preprocessing is allowed. We improve the reach-based approach of Gutman 17 in several ways. In particular, we introduce a bidirectional version of the algorithm that uses implicit lower bounds and we add shortcut arcs to reduce vertex reaches. Our modifications greatly improve both preprocessing and query times. The resulting algorithm is as fast as the best previous method, due to Sanders and Schultes 28. However, our algorithm is simpler and combines in a natural way with A* search, which yields significantly better query times.
Goldberg et al. (Sat,) studied this question.