Better Landmarks within Reach

  • Andrew Goldberg
  • Haim Kaplan
  • Renato Werneck

Workshop on Experimental Algorithms (WEA) |

A preliminary version has been presented at the 9th DIMACS Implementation Challenge Workshop

We present significant improvements to a practical algorithm for the point-to-point shortest path problem on road networks that combines A∗ search, landmark-based lower bounds, and reach-based pruning. Through reach-aware landmarks, better use of cache, and improved algorithms for reach computation, we make preprocessing and queries faster while reducing the overall space requirements. On the road networks of the USA or Europe, the shortest path between two random vertices can be found in about one millisecond after one or two hours of preprocessing. The algorithm is also effective on two-dimensional grids.