Highway Hierarchies Hasten Exact Shortest Path Queries

By Peter Sanders, Dominik Schultes. Embedded Systems and Applications, 2005

421 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.

Route Planning in Transportation Networks (2015, methodology): “For that reason, Sanders and Schultes [223] introduced a methodology based on Dijkstra ranks.”
Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (2008, methodology): “The queries generated for x-value r are random s–t-queries under the constraint that t is the r-th node visited by Dijkstra’s algorithm (see also [4]).”
Engineering Route Planning Algorithms (2009, methodology): “Highway Hierarchies (HHs) [58,59] group nodes and edges in a hierarchy of levels by alternating between two procedures: Contraction (i.”
A Hub-Based Labeling Algorithm for Shortest Paths in Road Networks (2011, methodology): “To evaluate our algorithm on queries of various ranges, Figure 3 plots query times against Dijkstra rank [26].”
Exact Routing in Large Road Networks Using Contraction Hierarchies (2012, methodology): “The node ordering computed by HNR uses levels acquired by highway hierarchies (HHs) by Sanders and Schultes (2005).”
Reach for A*: Efficient Point-to-Point Shortest Path Algorithms (2006, methodology): “Data for hh on USA, which we take from [28] and from a personal communication from Dominik Schultes, is available for the travel time metric only.”