Reach for A*: shortest path algorithms with preprocessing

Abstract

We study the point-to-point shortest path problem with preprocessing. Given an input graph, we preprocess it so as to be able to answer a series of source-to-destination queries efficiently. Our work is motivated by an algorithm of Gutman [ALENEX’04], based on the notion of reach, which measures how important each vertex is with respect to shortest paths. We present a simplified version of his algorithm that does not require explicit lower bounds during queries. We also show how the addition of shortcuts to the graph greatly improves the performance of both preprocessing and queries. Finally, we combine a reach-based algorithm with landmark-based A search to obtain a wide range of space-time trade-offs. For our motivating application, driving directions for road networks, the resulting algorithm is very efficient and practical. The road networks of the USA and Western Europe have roughly 20 million vertices, but on average our algorithm must visit fewer than a thousand to find the distance between two points. Our algorithm also works reasonably well on 2-dimensional grid graphs with random arc weights.

Cite this paper

@incollection{goldberg2009reach,
  title = {{Reach for A*: shortest path algorithms with preprocessing}},
  author = {Goldberg, Andrew V. and Kaplan, Haim and Werneck, Renato F.},
  booktitle = {DIMACS series in discrete mathematics and theoretical computer science},
  pages = {93--139},
  year = {2009},
  doi = {10.1090/dimacs/074/05}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.

Related papers