Reach for A*: Efficient Point-to-Point Shortest Path Algorithms

By Andrew Vladislav Goldberg, Haim Kaplan, Renato F. Werneck. Workshop on Algorithm Engineering and Experimentation, 2006

310 citations recorded by the source corpus.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Fast shortest path distance estimation in large networks (2009, methodology): “[20, 21] address the problem of point-topoint shortest path (PPSP) and employ landmarks in order to prune the search space of the shortest path computation.”
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (2008, methodology): “Examples of possible applications are reach-based routing [12] or SHARC [5].”
Exact Routing in Large Road Networks Using Contraction Hierarchies (2012, background): “This concept is called node contraction: deleting a node u and adding shortcut edges (shortcuts) [Sanders and Schultes 2005; Goldberg et al. 2006] to preserve shortest path distances between the remaining nodes.”
Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm (2008, methodology): “The basic approach was considerably strengthened by Goldberg et al. [ 19 ,20], in particular by a clever integration of shortcuts [31,32], i.e., single edges that represent whole paths in the original graph.”
Engineering Route Planning Algorithms (2009, methodology): “Landmark A∗ harmonizes very well with reach-based routing [26] whereas it gives only a small additional speedup when combined with HHs [17].”