#[1]alternate [2]Edit this page [3]Wikipedia (en) [4]Wikipedia Atom feed

[5]Jump to content

[ ] Main menu Main menu (BUTTON) move to sidebar (BUTTON) hide Navigation * [6]Main page * [7]Contents * [8]Current events * [9]Random article * [10]About Wikipedia * [11]Contact us

Contribute * [12]Help * [13]Learn to edit * [14]Community portal * [15]Recent changes * [16]Upload file * [17]Special pages

[18]Wikipedia The Free Encyclopedia [19]Search ____________________ (BUTTON) Search

[ ] Appearance

* [20]Donate * [21]Create account * [22]Log in

[ ] Personal tools * [23]Donate * [24]Create account * [25]Log in

Pages for logged out editors [26]learn more * [27]Contributions * [28]Talk

Contents

(BUTTON) move to sidebar (BUTTON) hide * [29](Top) * [30]1 Algorithm (BUTTON) Toggle Algorithm subsection + [31]1.1 Preprocessing phase o [32]1.1.1 Node order + [33]1.2 Query phase o [34]1.2.1 Path retrieval * [35]2 Customized contraction hierarchies * [36]3 Extensions and applications * [37]4 Theory (BUTTON) Toggle Theory subsection + [38]4.1 Preprocessing Performance + [39]4.2 Query Performance * [40]5 References * [41]6 External links (BUTTON) Toggle External links subsection + [42]6.1 Open source implementations

[ ] Toggle the table of contents

Contraction hierarchies

[ ] 2 languages * [43]Français * [44]Српски / srpski

[45]Edit links

* [46]Article * [47]Talk

[ ] English

* [48]Read * [49]Edit * [50]View history

[ ] Tools Tools (BUTTON) move to sidebar (BUTTON) hide Actions * [51]Read * [52]Edit * [53]View history

General * [54]What links here * [55]Related changes * [56]Upload file * [57]Permanent link * [58]Page information * [59]Cite this page * [60]Get shortened URL * [61]Download QR code

Print/export * [62]Download as PDF * [63]Printable version

In other projects * [64]Wikidata item

Appearance (BUTTON) move to sidebar (BUTTON) hide From Wikipedia, the free encyclopedia In applied mathematics, a technique to find the shortest path

In [65]computer science, the method of contraction hierarchies is a [66]speed-up technique for finding the [67]shortest path in a [68]graph. The most intuitive applications are car-navigation systems: a user wants to drive from [MATH: A {\displaystyle A} :MATH] {\displaystyle A} to [MATH: B {\displaystyle B} :MATH] {\displaystyle B} using the quickest possible route. The metric optimized here is the travel time. Intersections are represented by [69]vertices, the road sections connecting them by [70]edges. The edge weights represent the time it takes to drive along this segment of the road. A path from [MATH: A {\displaystyle A} :MATH] {\displaystyle A} to [MATH: B {\displaystyle B} :MATH] {\displaystyle B} is a sequence of edges (road sections); the shortest path is the one with the minimal sum of edge weights among all possible paths. The shortest path in a graph can be computed using [71]Dijkstra's algorithm but, given that road networks consist of tens of millions of vertices, this is impractical.^[72][1] Contraction hierarchies is a speed-up method optimized to exploit properties of graphs representing road networks.^[73][2] The speed-up is achieved by creating shortcuts in a preprocessing phase which are then used during a shortest-path query to skip over "unimportant" vertices.^[74][2] This is based on the observation that road networks are highly hierarchical. Some intersections, for example highway junctions, are "more important" and higher up in the hierarchy than for example a junction leading into a dead end. Shortcuts can be used to save the precomputed distance between two important junctions such that the algorithm doesn't have to consider the full path between these junctions at query time. Contraction hierarchies do not know about which roads humans consider "important" (e.g. highways), but they are provided with the graph as input and are able to assign importance to vertices using heuristics.

Contraction hierarchies are not only applied to speed-up algorithms in [75]car-navigation systems but also in web-based [76]route planners, [77]traffic simulation, and logistics optimization.^[78][3]^[79][1]^[80][4] Implementations of the algorithm are publicly available as [81]open source software.^[82][5]^[83][6]^[84][7]^[85][8]^[86][9]

Algorithm

[[87]edit]

The contraction hierarchies (CH) algorithm is a two-phase approach to the [88]shortest path problem consisting of a preprocessing phase and a query phase. As road networks change rather infrequently, more time (seconds to hours) can be used to once precompute some calculations before queries are to be answered. Using this precomputed data, many queries can be answered taking very little time (microseconds) each.^[89][1]^[90][3] CHs rely on shortcuts to achieve this speedup. A shortcut connects two vertices [MATH: u {\displaystyle u} :MATH] {\displaystyle u} and [MATH: v {\displaystyle v} :MATH] {\displaystyle v} not adjacent in the original graph. Its edge weight is the sum of the edge weights on the shortest [MATH: u {\displaystyle u} :MATH] {\displaystyle u} - [MATH: v {\displaystyle v} :MATH] {\displaystyle v} path.

Consider two large cities connected by a highway. Between these two cities, there is a multitude of junctions leading to small villages and suburbs. Most drivers want to get from one city to the other – maybe as part of a larger route – and not take one of the exits on the way. In the graph representing this road layout, each intersection is represented by a node and edges are created between neighboring intersections. To calculate the distance between these two cities, the algorithm has to traverse all the edges along the way, adding up their length. Precomputing this distance once and storing it in an additional edge created between the two large cities will save calculations each time this highway has to be evaluated in a query. This additional edge is called a "shortcut" and has no counterpart in the real world. The contraction hierarchies algorithm has no knowledge about road types but is able to determine which shortcuts have to be created using the graph alone as input. To find a path from [MATH: s {\displaystyle s} :MATH] {\displaystyle s} to [MATH: t {\displaystyle t} :MATH] {\displaystyle t} the algorithm can skip over the grey vertices and use the dashed shortcut instead. This reduces the number of vertices the algorithm has to look at. The edge weight of the shortcut from [MATH: u {\displaystyle u} :MATH] {\displaystyle u} to [MATH: v {\displaystyle v} :MATH] {\displaystyle v} is the sum of the edge weights of the shortest [MATH: u {\displaystyle u} :MATH] {\displaystyle u} - [MATH: v {\displaystyle v} :MATH] {\displaystyle v} path.

Preprocessing phase

[[91]edit]

The CH algorithm relies on shortcuts created in the preprocessing phase to reduce the search space – that is the number of vertices CH has to look at, at query time. To achieve this, iterative vertex contractions are performed. When contracting a vertex [MATH: v {\displaystyle v} :MATH] {\displaystyle v} it is temporarily removed from the graph [MATH: G {\displaystyle G} :MATH] {\displaystyle G} , and a shortcut is created between each pair [MATH: { u , w } {\displaystyle \{u,w\}} :MATH] {\displaystyle \{u,w\}} of neighboring vertices if the shortest path from [MATH: u {\textstyle u} :MATH] {\textstyle u} to [MATH: w {\textstyle w} :MATH] {\textstyle w} contains [MATH: v {\displaystyle v} :MATH] {\displaystyle v} .^[92][2] The process of determining if the shortest path between [MATH: u {\textstyle u} :MATH] {\textstyle u} and [MATH: w {\textstyle w} :MATH] {\textstyle w} contains [MATH: v {\displaystyle v} :MATH] {\displaystyle v} is called witness search. It can be performed for example by computing a path from [MATH: u {\displaystyle u} :MATH] {\displaystyle u} to [MATH: w {\displaystyle w} :MATH] {\displaystyle w} using a forward search using only not yet contracted nodes.^[93][3] The original graph is the line [MATH: ( a , b , c , d , e , f ) {\displaystyle (a,b,c,d,e,f)} :MATH] {\displaystyle (a,b,c,d,e,f)} (solid). Dashed edges represent shortcuts, grey arrows show which two edges are combined to form the respective shortcut. Vertices have been drawn to represent the node order in which the vertices are being contracted, bottom-to-top. Contracting vertex [MATH: c {\displaystyle c} :MATH] {\displaystyle c} introduces a shortcut between [MATH: b {\displaystyle b} :MATH] {\displaystyle b} and [MATH: d {\displaystyle d} :MATH] {\displaystyle d} with [MATH: d i s t ( b , d ) = d i s t ( b , c ) + d i s t ( c , d ) {\displaystyle \mathrm {dist} (b,d)=\mathrm {dist} (b,c)+\mathrm {dist} (c,d)} :MATH] {\displaystyle \mathrm {dist} (b,d)=\mathrm {dist} (b,c)+\mathrm {dist} (c,d)} . Contractions of the vertices [MATH: e {\displaystyle e} :MATH] {\displaystyle e} and [MATH: d {\displaystyle d} :MATH] {\displaystyle d} introduce one shortcut respectively. Contractions of [MATH: a {\displaystyle a} :MATH] {\displaystyle a} , [MATH: b {\displaystyle b} :MATH] {\displaystyle b} and [MATH: f {\displaystyle f} :MATH] {\displaystyle f} do not introduce any shortcuts and are therefore not shown.

Node order

[[94]edit]

The vertices of the input graph have to be contracted in a way which minimizes the number of edges added to the graph by contractions. As optimal node ordering is [95]NP-complete,^[96][10] [97]heuristics are used.^[98][2]

Bottom-up and top-down heuristics exist. On one hand, the [99]computationally cheaper bottom-up heuristics decide the order in which to contract the vertices in a [100]greedy fashion; this means the order is not known in advance but rather the next node is selected for contraction after the previous contraction has been completed. Top-down heuristics on the other hand precompute the whole node ordering before the first node is contracted. This yields better results but needs more preprocessing time.^[101][2]

In bottom-up heuristics, a combination of factors is used to select the next vertex for contraction. As the number of shortcuts is the primary factor that determines preprocessing and query runtime, we want to keep it as small as possible. The most important term by which to select the next node for contraction is therefore the net number of edges added when contracting a node [MATH: x {\displaystyle x} :MATH] {\displaystyle x} . This is defined as [MATH: A ( x ) − | { ( u , x ) : ( u , x ) ∈ E } | {\displaystyle A(x)-|\{(u,x)\colon (u,x)\in E\}|} :MATH] {\displaystyle A(x)-|\{(u,x)\colon (u,x)\in E\}|} where [MATH: A ( x ) {\displaystyle A(x)} :MATH] {\displaystyle A(x)} is the number of shortcuts that would be created if [MATH: x {\displaystyle x} :MATH] {\displaystyle x} were to be contracted and [MATH: | { ( u , x ) : ( u , x ) ∈ E } | {\displaystyle |\{(u,x)\colon (u,x)\in E\}|} :MATH] {\displaystyle |\{(u,x)\colon (u,x)\in E\}|} is the number of edges incident to [MATH: x {\displaystyle x} :MATH] {\displaystyle x} . Using this criterion alone, a linear path would result in a linear hierarchy (many [102]levels) and no created shortcuts. By considering the number of nearby vertices that are already contracted, a uniform contraction and a flat hierarchy (less levels) is achieved. This can, for example, be done by maintaining a counter for each node that is incremented each time a neighboring vertex is contracted. Nodes with lower counters are then preferred to nodes with higher counters.^[103][11]

Top-down heuristics, on the other hand, yield better results but need more preprocessing time. They classify vertices that are part of many shortest paths as more important than those that are only needed for a few shortest paths. This can be [104]approximated using [105]nested dissections.^[106][2] To compute a nested dissection, one recursively separates a graph into two parts, which are themselves then separated into two parts and so on. That is, find a subset of nodes [MATH: S ⊆ V {\displaystyle S\subseteq V} :MATH] {\displaystyle S\subseteq V} which when removed from the graph [MATH: G {\displaystyle G} :MATH] {\displaystyle G} separate [MATH: G {\displaystyle G} :MATH] {\displaystyle G} into two disjunct pieces [MATH: G 1 , G 2 {\displaystyle G_{1},G_{2}} :MATH] {\displaystyle G_{1},G_{2}} of approximately equal size such that [MATH: S ∪ G 1 ∪ G 2 = G {\displaystyle S\cup G_{1}\cup G_{2}=G} :MATH] {\displaystyle S\cup G_{1}\cup G_{2}=G} . Place all nodes [MATH: v ∈ S {\displaystyle v\in S} :MATH] {\displaystyle v\in S} last in the node ordering and then recursively compute the nested dissection for [MATH: G 1 {\displaystyle G_{1}} :MATH] {\displaystyle G_{1}} and [MATH: G 2 {\displaystyle G_{2}} :MATH] {\displaystyle G_{2}} ,^[107][12] the intuition being that all queries from one half of the graph to the other half of the graph need to pass through the small separator and therefore nodes in this separator are of high importance. Nested dissections can be efficiently calculated on road networks because of their small separators.^[108][13]

Query phase

[[109]edit]

In the query phase, a bidirectional search is performed starting from the starting node [MATH: s {\displaystyle s} :MATH] {\displaystyle s} and the target node [MATH: t {\displaystyle t} :MATH] {\displaystyle t} on the original graph augmented by the shortcuts created in the preprocessing phase.^[110][2] The most important vertex on the shortest path between [MATH: s {\displaystyle s} :MATH] {\displaystyle s} and [MATH: t {\displaystyle t} :MATH] {\displaystyle t} will be either [MATH: s {\displaystyle s} :MATH] {\displaystyle s} or [MATH: t {\displaystyle t} :MATH] {\displaystyle t} themselves or more important than both [MATH: s {\displaystyle s} :MATH] {\displaystyle s} and [MATH: t {\displaystyle t} :MATH] {\displaystyle t} . Therefore, the vertex [MATH: u {\displaystyle u} :MATH] {\displaystyle u} minimizing [MATH: d i s t ( s , u ) + d i s t ( u , t ) {\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)} :MATH] {\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)} is on the shortest [MATH: s − t {\displaystyle s-t} :MATH] {\displaystyle s-t} path in the original graph and [MATH: d i s t ( s , u ) + d i s t ( u , t ) = d i s t ( s , t ) {\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)=\mathrm {dist} (s,t)} :MATH] {\displaystyle \mathrm {dist} (s,u)+\mathrm {dist} (u,t)=\mathrm {dist} (s,t)} holds.^[111][2] This, in combination with how shortcuts are created, means that both forward and backward search only need to relax edges leading to more important nodes (upwards) in the hierarchy which keeps the search space small.^[112][3] In all up-(down-up)-down paths, the inner (down-up) can be skipped, because a shortcut has been created in the preprocessing stage. When computing the shortest path from [MATH: s {\displaystyle s} :MATH] {\displaystyle s} to [MATH: t {\displaystyle t} :MATH] {\displaystyle t} , forward (orange) and backward (blue) search only need to follow edges going upwards in the hierarchy. The found path marked in red and uses one shortcut (dashed).

Path retrieval

[[113]edit]

A CH query, as described above, yields the time or distance from [MATH: s {\displaystyle s} :MATH] {\displaystyle s} to [MATH: t {\displaystyle t} :MATH] {\displaystyle t} but not the actual path. To obtain the list of edges (roads) on the shortest path, the shortcuts taken have to be unpacked. Each shortcut is the concatenation of two edges: either two edges of the original graph, or two shortcuts, or one original edge and one shortcut. Storing the middle vertex of each shortcut during contraction enables linear-time recursive unpacking of the shortest route.^[114][2]^[115][3]

Customized contraction hierarchies

[[116]edit]

If the edge weights are changed more often than the network topology, CH can be extended to a three-phase approach by including a customization phase between the preprocessing and query phase. This can be used for example to switch between shortest distance and shortest time or include current traffic information as well as user preferences like avoiding certain types of roads (ferries, highways, ...). In the preprocessing phase, most of the runtime is spent on computing the order in which the nodes are contracted.^[117][3] This sequence of contraction operations in the preprocessing phase can be saved for when they are later needed in the customization phase. Each time the metric is customized, the contractions can then be efficiently applied in the stored order using the custom metric.^[118][2] Additionally, depending on the new edge weights it may be necessary to recompute some shortcuts.^[119][3] For this to work, the contraction order has to be computed using metric-independent nested dissections.^[120][1]

Extensions and applications

[[121]edit]

CHs as described above search for a shortest path from one starting node to one target node. This is called one-to-one shortest path and is used for example in car-navigation systems. Other applications include matching [122]GPS traces to road segments and speeding up [123]traffic simulators which have to consider the likely routes taken by all drivers in a network. In [124]route prediction one tries to estimate where a vehicle is likely headed by calculating how well its current and past positions agree with a shortest path from its starting point to any possible target. This can be efficiently done using CHs.^[125][2]

In one-to-many scenarios, a starting node [MATH: s {\displaystyle s} :MATH] {\displaystyle s} and a set of target nodes [MATH: T {\displaystyle T} :MATH] {\displaystyle T} are given and the distance [MATH: d i s t ( s , t ) {\displaystyle \mathrm {dist} (s,t)} :MATH] {\displaystyle \mathrm {dist} (s,t)} for all [MATH: t ∈ T {\displaystyle t\in T} :MATH] {\displaystyle t\in T} has to be computed. The most prominent application for one-to-many queries are point-of-interest searches. Typical examples include finding the closest gas station, restaurant or post office using actual travel time instead of [126]geographical distance as metric.^[127][2]

In the many-to-many shortest path scenario, a set of starting nodes [MATH: S {\displaystyle S} :MATH] {\displaystyle S} and a set of target nodes [MATH: T {\displaystyle T} :MATH] {\displaystyle T} are given and the distance [MATH: d i s t ( s i , t i ) {\displaystyle \mathrm {dist} (s_{i},t_{i})} :MATH] {\displaystyle \mathrm {dist} (s_{i},t_{i})} for all [MATH: ( s i , t j ) ∈ S × T {\displaystyle (s_{i},t_{j})\in S\times T} :MATH] {\displaystyle (s_{i},t_{j})\in S\times T} has to be computed. This is used for example in logistic applications.^[128][2] CHs can be extended to many-to-many queries in the following manner. First, perform a backward upward search from each [MATH: t j ∈ T {\displaystyle t_{j}\in T} :MATH] {\displaystyle t_{j}\in T} . For each vertex [MATH: u {\displaystyle u} :MATH] {\displaystyle u} scanned during this search, one stores [MATH: d i s t ( t j , u ) {\displaystyle \mathrm {dist} (t_{j},u)} :MATH] {\displaystyle \mathrm {dist} (t_{j},u)} in a bucket [MATH: β ( u ) {\displaystyle \beta (u)} :MATH] {\displaystyle \beta (u)} . Then, one runs a forward upward search from each [MATH: s i ∈ S {\displaystyle s_{i}\in S} :MATH] {\displaystyle s_{i}\in S} , checking for each non-empty bucket, whether the route over the corresponding vertex improves any best distance. That is, if [MATH: d i s t ( s i , u ) + d i s t ( u , t j ) < d i s t ( s i , t j ) {\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})} :MATH] {\displaystyle \mathrm {dist} (s_{i},u)+\mathrm {dist} (u,t_{j})<\mathrm {dist} (s_{i},t_{j})} for any [MATH: ( s i , t j ) ∈ S × T {\displaystyle (s_{i},t_{j})\in S\times T} :MATH] {\displaystyle (s_{i},t_{j})\in S\times T} .^[129][2]^[130][3]

Some applications even require one-to-all computations, i.e., finding the distances from a source vertex [MATH: s {\displaystyle s} :MATH] {\displaystyle s} to all other vertices in the graph. As Dijkstra's algorithm visits each edge exactly once and therefore runs in linear time it is theoretically optimal. Dijkstra's algorithm, however, is hard to [131]parallelize and is not [132]cache-optimal because of its bad locality. CHs can be used for a more cache-optimal implementation. For this, a forward upward search from [MATH: s {\displaystyle s} :MATH] {\displaystyle s} followed by a downward scan over all nodes in the shortcut-enriched graph is performed. The later operation scans through memory in a linear fashion, as the nodes are processed in decreasing order of importance and can therefore be placed in memory accordingly.^[133][14] Note, that this is possible because the order in which the nodes are processed in the second phase is independent of the source node [MATH: s {\displaystyle s} :MATH] {\displaystyle s} .^[134][2]

In production, car-navigation systems should be able to compute fastest travel routes using predicted traffic information and display alternative routes. Both can be done using CHs.^[135][2] The former is called routing with time-dependent networks where the travel time of a given edge is no longer constant but rather a function of the time of day when entering the edge. Alternative routes need to be smooth-looking, significantly different from the shortest path but not significantly longer.^[136][2]

CHs can be extended to optimize multiple metrics at the same time; this is called multi-criteria route planning. For example, one could minimize both travel cost and time. Another example are [137]electric vehicles for which the available battery charge constrains the valid routes as the battery may not run empty.^[138][2]

Theory

[[139]edit]

A number of bounds have been established on the preprocessing and query performance of contraction hierarchies. In the following let [MATH: n {\displaystyle n} :MATH] {\displaystyle n} be the number of vertices in the graph, [MATH: m {\displaystyle m} :MATH] {\displaystyle m} the number of edges, [MATH: h {\displaystyle h} :MATH] {\displaystyle h} the [140]highway dimension, [MATH: D {\displaystyle D} :MATH] {\displaystyle D} the graph diameter, [MATH: t d {\displaystyle td} :MATH] {\displaystyle td} is the [141]tree-depth and [MATH: t w {\displaystyle tw} :MATH] {\displaystyle tw} is the [142]tree-width.

The first analysis of contraction hierarchy performance relies in part on a quantity known as the [143]highway dimension. While the definition of this quantity is technical, intuitively a graph has a small highway dimension if for every [MATH: r > 0 {\displaystyle r>0} :MATH] {\displaystyle r>0} there is a sparse set of vertices [MATH: S r {\displaystyle S_{r}} :MATH] {\displaystyle S_{r}} such that every shortest path of length greater than [MATH: r {\displaystyle r} :MATH] {\displaystyle r} includes a vertex from [MATH: S r {\displaystyle S_{r}} :MATH] {\displaystyle S_{r}} . Calculating the exact value of the [144]highway dimension is [145]NP-hard^[146][15]^[147][16] and most likely [148]W[1]-hard,^[149][17] but for grids it is known that the [150]highway dimension is [MATH: h ∈ Θ ( n ) {\displaystyle h\in \Theta ({\sqrt {n}})} :MATH] {\displaystyle h\in \Theta ({\sqrt {n}})} .^[151][18]

An alternative analysis was presented in the Customizable Contraction Hierarchy line of work. Query running times can be bounded by [MATH: O ( t d 2 ) {\displaystyle O(td^{2})} :MATH] {\displaystyle O(td^{2})} . As the tree-depth can be bounded in terms of the tree-width, [MATH: O ( ( t w log ⁡ n ) 2 ) {\displaystyle O((tw\log n)^{2})} :MATH] {\displaystyle O((tw\log n)^{2})} is also a valid upper bound. The main source is ^[152][19] but the consequences for the worst case running times are better detailed in.^[153][20]

Preprocessing Performance

[[154]edit]

CAPTION: Preprocessing Time Complexity of Contraction Hierarchies

Algorithm Year Time Complexity Randomized Processing^[155][21] 2015 [MATH: O ( n 2 log ⁡ n + n m ) {\displaystyle O(n^{2}\log n+nm)} :MATH] {\displaystyle O(n^{2}\log n+nm)}

Query Performance

[[156]edit]

CAPTION: Query Time Complexity of Contraction Hierarchies

Algorithm/Analysis Technique Year Time Complexity Notes Bounded Growth Graphs^[157][22] 2018 [MATH: O ( n log ⁡ n ) {\displaystyle O({\sqrt {n}}\log n)} :MATH] {\displaystyle O({\sqrt {n}}\log n)} Customizable Contraction Hierarchies^[158][19]^[159][20] 2013-2018 [MATH: O ( t d 2 ) {\displaystyle O(td^{2})} :MATH] {\displaystyle O(td^{2})} or [MATH: O ( ( t w ∗ log ⁡ n ) 2 ) {\displaystyle O((tw*\log n)^{2})} :MATH] {\displaystyle O((tw*\log n)^{2})} . [MATH: t d {\displaystyle td} :MATH] {\displaystyle td} is the [160]tree-depth and [MATH: t w {\displaystyle tw} :MATH] {\displaystyle tw} is the [161]tree-width Randomized Processing^[162][21] 2015 [MATH: n ( 6 ln ⁡ ( 1 / p ) log ⁡ n + 2 ) {\displaystyle {\sqrt {n}}(6\ln(1/p)\log {\sqrt {n}}+2)} :MATH] {\displaystyle {\sqrt {n}}(6\ln(1/p)\log {\sqrt {n}}+2)} Exact, no O-notation; works with high probability Modified SHARC^[163][18] 2010 [MATH: O ( ( h log ⁡ n log ⁡ D ) 2 ) {\displaystyle O((h\log n\log D)^{2})} :MATH] {\displaystyle O((h\log n\log D)^{2})} Polynomial preprocessing Modified SHARC^[164][18] 2010 [MATH: O ( ( h log ⁡ D ) 2 ) {\displaystyle O((h\log D)^{2})} :MATH] {\displaystyle O((h\log D)^{2})} Superpolynomial preprocessing

References

[[165]edit] 1. ^ [166]^a [167]^b [168]^c [169]^d Dibbelt, Julian; Strasser, Ben; Wagner, Dorothea (5 April 2016). "Customizable Contraction Hierarchies". Journal of Experimental Algorithmics. 21 (1): 1–49. [170]arXiv:[171]1402.0402. [172]doi:[173]10.1145/2886843. [174]S2CID [175]5247950. 2. ^ [176]^a [177]^b [178]^c [179]^d [180]^e [181]^f [182]^g [183]^h [184]^i [185]^j [186]^k [187]^l [188]^m [189]^n [190]^o [191]^p [192]^q [193]^r Bast, Hannah; Delling, Daniel; Goldberg, Andrew V.; Müller-Hannemann, Matthias; Pajor, Thomas; Sanders, Peter; Wagner, Dorothea; Werneck, Renato F. (2016). "Route Planning in Transportation Networks". Algorithm Engineering. Lecture Notes in Computer Science. Vol. 9220. pp. 19–80. [194]arXiv:[195]1504.05140. [196]doi:[197]10.1007/978-3-319-49487-6_2. [198]ISBN [199]978-3-319-49486-9. [200]S2CID [201]14384915. 3. ^ [202]^a [203]^b [204]^c [205]^d [206]^e [207]^f [208]^g [209]^h Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Vetter, Christian (2012). [210]"Exact Routing in Large Road Networks Using Contraction Hierarchies". Transportation Science. 46 (3): 388–404. [211]doi:[212]10.1287/trsc.1110.0401. 4. [213]^ Delling, Daniel; Sanders, Peter; Schultes, Dominik; Wagner, Dorothea (2009). "Engineering Route Planning Algorithms". Algorithmics of Large and Complex Networks. Lecture Notes in Computer Science. Vol. 5515. pp. 117–139. [214]doi:[215]10.1007/978-3-642-02094-0_7. [216]ISBN [217]978-3-642-02093-3. 5. [218]^ [219]"OSRM – Open Source Routing Machine". 6. [220]^ [221]"Wiki – OpenTripPlanner". 7. [222]^ [223]"Web – GraphHopper". 8. [224]^ [225]"GitHub – Tempus". [226]GitHub. 9 September 2021. 9. [227]^ [228]"GitHub – RoutingKit". [229]GitHub. 24 January 2022. 10. [230]^ Bauer, Reinhard; Delling, Daniel; Sanders, Peter; Schieferdecker, Dennis; Schultes, Dominik; Wagner, Dorothea (2010-03-01). [231]"Combining hierarchical and goal-directed speed-up techniques for dijkstra's algorithm". Journal of Experimental Algorithmics. 15: 2.1. [232]doi:[233]10.1145/1671970.1671976. [234]ISSN [235]1084-6654. [236]S2CID [237]1661292. 11. [238]^ Geisberger, Robert; Sanders, Peter; Schultes, Dominik; Delling, Daniel (2008). "Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks". In McGeoch, Catherine C. (ed.). Experimental Algorithms. Lecture Notes in Computer Science. Vol. 5038. Springer Berlin Heidelberg. pp. 319–333. [239]doi:[240]10.1007/978-3-540-68552-4_24. [241]ISBN [242]9783540685524. [243]S2CID [244]777101. 12. [245]^ Bauer, Reinhard; Columbus, Tobias; Rutter, Ignaz; Wagner, Dorothea (2016-09-13). [246]"Search-space size in contraction hierarchies". Theoretical Computer Science. 645: 112–127. [247]doi:[248]10.1016/j.tcs.2016.07.003. [249]ISSN [250]0304-3975. 13. [251]^ Delling, Daniel; Goldberg, Andrew V.; Razenshteyn, Ilya; Werneck, Renato F. (May 2011). "Graph Partitioning with Natural Cuts". 2011 IEEE International Parallel & Distributed Processing Symposium. pp. 1135–1146. [252]CiteSeerX [253]10.1.1.385.1580. [254]doi:[255]10.1109/ipdps.2011.108. [256]ISBN [257]978-1-61284-372-8. [258]S2CID [259]6884123. 14. [260]^ Delling, Daniel; Goldberg, Andrew V.; Nowatzyk, Andreas; Werneck, Renato F. (2011). "PHAST: Hardware-Accelerated Shortest Path Trees". 2011 IEEE International Parallel & Distributed Processing Symposium. pp. 921–931. [261]doi:[262]10.1109/ipdps.2011.89. [263]ISBN [264]978-1-61284-372-8. [265]S2CID [266]1419921. 15. [267]^ Feldmann, Andreas Emil; Fung, Wai Shing; Könemann, Jochen; Post, Ian (2018-01-01). [268]"A $(1+\varepsilon)$-Embedding of Low Highway Dimension Graphs into Bounded Treewidth Graphs". SIAM Journal on Computing. 47 (4): 1667–1704. [269]arXiv:[270]1502.04588. [271]doi:[272]10.1137/16M1067196. [273]ISSN [274]0097-5397. [275]S2CID [276]11339698. 16. [277]^ Blum, Johannes (2019). "Hierarchy of Transportation Network Parameters and Hardness Results". In Jansen, Bart M. P.; Telle, Jan Arne (eds.). [278]14th International Symposium on Parameterized and Exact Computation (IPEC 2019). Leibniz International Proceedings in Informatics. Vol. 148. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik. pp. 4:1–4:15. [279]doi:[280]10.4230/LIPIcs.IPEC.2019.4. [281]ISBN [282]978-3-95977-129-0. [283]S2CID [284]166228480. 17. [285]^ Blum, Johannes; Disser, Yann; Feldmann, Andreas Emil; Gupta, Siddharth; Zych-Pawlewicz, Anna (2022). "On Sparse Hitting Sets: From Fair Vertex Cover to Highway Dimension". In Dell, Holger; Nederlof, Jesper (eds.). 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics. Vol. 249. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik. pp. 5:1–5:23. [286]doi:[287]10.4230/LIPIcs.IPEC.2022.5. [288]ISBN [289]978-3-95977-260-0. 18. ^ [290]^a [291]^b [292]^c Abraham, Ittai; Fiat, Amos; Goldberg, Andrew (2010). [293]Highway dimension, shortest paths, and provably efficient algorithms (PDF). Proceedings of the 2010 annual ACM-SIAM symposium on discrete algorithms. [294]doi:[295]10.1137/1.9781611973075.64. 19. ^ [296]^a [297]^b Dibbelt, Julian; Strasser, Ben; Wagner, Dorothea (2016). "Customizable Contraction Hierarchies". ACM Journal of Experimental Algorithmics. 21: 1–49. [298]arXiv:[299]1402.0402. [300]doi:[301]10.1145/2886843. [302]S2CID [303]5247950. 20. ^ [304]^a [305]^b Hamann, Michael; Strasser, Ben (2018). "Graph Bisection with Pareto Optimization". ACM Journal of Experimental Algorithmics. 23: 1–34. [306]arXiv:[307]1504.03812. [308]doi:[309]10.1145/3173045. [310]S2CID [311]3395784. 21. ^ [312]^a [313]^b Funke, Stefan; Storandt, Sabine (2015). "Provable Efficiency of Contraction Hierarchies with Randomized Preprocessing". Algorithms and Computation. Lecture Notes in Computer Science. Vol. 9472. pp. 479–490. [314]doi:[315]10.1007/978-3-662-48971-0_41. [316]ISBN [317]978-3-662-48971-0. 22. [318]^ Blum, Johannes; Funke, Stefan; Storandt, Sabine (2018). [319]Sublinear Search Spaces for Shortest Path Planning in Grid and Road Networks (PDF). AAAI.

External links

[[320]edit]

Open source implementations

[[321]edit] * [322]https://www.graphhopper.com/ * [323]https://github.com/ifsttar/Tempus * [324]https://github.com/RoutingKit/RoutingKit * [325]http://project-osrm.org/ * [326]http://www.opentripplanner.org/

Retrieved from "[327]https://en.wikipedia.org/w/index.php?title=Contraction_hierarchie s&oldid=1282016643" [328]Categories: * [329]Graph algorithms * [330]Search algorithms * [331]Routing algorithms

Hidden categories: * [332]Articles with short description * [333]Short description is different from Wikidata

* This page was last edited on 23 March 2025, at 20:23 (UTC). * Text is available under the [334]Creative Commons Attribution-ShareAlike 4.0 License; additional terms may apply. By using this site, you agree to the [335]Terms of Use and [336]Privacy Policy. Wikipedia® is a registered trademark of the [337]Wikimedia Foundation, Inc., a non-profit organization.

* [338]Privacy policy * [339]About Wikipedia * [340]Disclaimers * [341]Contact Wikipedia * [342]Code of Conduct * [343]Developers * [344]Statistics * [345]Cookie statement * [346]Mobile view

* [347]Wikimedia Foundation * [348]Powered by MediaWiki

(BUTTON) Search ____________________ (BUTTON) Search

[ ] Toggle the table of contents Contraction hierarchies (BUTTON) 2 languages [349]Add topic

References

Visible links: 1. https://en.m.wikipedia.org/wiki/Contraction_hierarchies 2. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit 3. https://en.wikipedia.org/w/rest.php/v1/search 4. https://en.wikipedia.org/w/index.php?title=Special:RecentChanges&feed=atom 5. https://en.wikipedia.org/wiki/Contraction_hierarchies#bodyContent 6. https://en.wikipedia.org/wiki/Main_Page 7. https://en.wikipedia.org/wiki/Wikipedia:Contents 8. https://en.wikipedia.org/wiki/Portal:Current_events 9. https://en.wikipedia.org/wiki/Special:Random 10. https://en.wikipedia.org/wiki/Wikipedia:About 11. https://en.wikipedia.org/wiki/Wikipedia:Contact_us 12. https://en.wikipedia.org/wiki/Help:Contents 13. https://en.wikipedia.org/wiki/Help:Introduction 14. https://en.wikipedia.org/wiki/Wikipedia:Community_portal 15. https://en.wikipedia.org/wiki/Special:RecentChanges 16. https://en.wikipedia.org/wiki/Wikipedia:File_upload_wizard 17. https://en.wikipedia.org/wiki/Special:SpecialPages 18. https://en.wikipedia.org/wiki/Main_Page 19. https://en.wikipedia.org/wiki/Special:Search 20. https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en 21. https://en.wikipedia.org/w/index.php?title=Special:CreateAccount&returnto=Contraction+hierarchies 22. https://en.wikipedia.org/w/index.php?title=Special:UserLogin&returnto=Contraction+hierarchies 23. https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=en.wikipedia.org&uselang=en 24. https://en.wikipedia.org/w/index.php?title=Special:CreateAccount&returnto=Contraction+hierarchies 25. https://en.wikipedia.org/w/index.php?title=Special:UserLogin&returnto=Contraction+hierarchies 26. https://en.wikipedia.org/wiki/Help:Introduction 27. https://en.wikipedia.org/wiki/Special:MyContributions 28. https://en.wikipedia.org/wiki/Special:MyTalk 29. https://en.wikipedia.org/wiki/Contraction_hierarchies 30. https://en.wikipedia.org/wiki/Contraction_hierarchies#Algorithm 31. https://en.wikipedia.org/wiki/Contraction_hierarchies#Preprocessing_phase 32. https://en.wikipedia.org/wiki/Contraction_hierarchies#Node_order 33. https://en.wikipedia.org/wiki/Contraction_hierarchies#Query_phase 34. https://en.wikipedia.org/wiki/Contraction_hierarchies#Path_retrieval 35. https://en.wikipedia.org/wiki/Contraction_hierarchies#Customized_contraction_hierarchies 36. https://en.wikipedia.org/wiki/Contraction_hierarchies#Extensions_and_applications 37. https://en.wikipedia.org/wiki/Contraction_hierarchies#Theory 38. https://en.wikipedia.org/wiki/Contraction_hierarchies#Preprocessing_Performance 39. https://en.wikipedia.org/wiki/Contraction_hierarchies#Query_Performance 40. https://en.wikipedia.org/wiki/Contraction_hierarchies#References 41. https://en.wikipedia.org/wiki/Contraction_hierarchies#External_links 42. https://en.wikipedia.org/wiki/Contraction_hierarchies#Open_source_implementations 43. https://fr.wikipedia.org/wiki/Contractions_hiérarchiques 44. https://sr.wikipedia.org/wiki/Kontrakcija_hijerarhija 45. https://www.wikidata.org/wiki/Special:EntityPage/Q5165688#sitelinks-wikipedia 46. https://en.wikipedia.org/wiki/Contraction_hierarchies 47. https://en.wikipedia.org/wiki/Talk:Contraction_hierarchies 48. https://en.wikipedia.org/wiki/Contraction_hierarchies 49. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit 50. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=history 51. https://en.wikipedia.org/wiki/Contraction_hierarchies 52. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit 53. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=history 54. https://en.wikipedia.org/wiki/Special:WhatLinksHere/Contraction_hierarchies 55. https://en.wikipedia.org/wiki/Special:RecentChangesLinked/Contraction_hierarchies 56. https://en.wikipedia.org/wiki/Wikipedia:File_Upload_Wizard 57. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&oldid=1282016643 58. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=info 59. https://en.wikipedia.org/w/index.php?title=Special:CiteThisPage&page=Contraction_hierarchies&id=1282016643&wpFormIdentifier=titleform 60. https://en.wikipedia.org/w/index.php?title=Special:UrlShortener&url=https://en.wikipedia.org/wiki/Contraction_hierarchies 61. https://en.wikipedia.org/w/index.php?title=Special:QrCode&url=https://en.wikipedia.org/wiki/Contraction_hierarchies 62. https://en.wikipedia.org/w/index.php?title=Special:DownloadAsPdf&page=Contraction_hierarchies&action=show-download-screen 63. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&printable=yes 64. https://www.wikidata.org/wiki/Special:EntityPage/Q5165688 65. https://en.wikipedia.org/wiki/Computer_science 66. https://en.wikipedia.org/wiki/Speedup 67. https://en.wikipedia.org/wiki/Shortest_path_problem 68. https://en.wikipedia.org/wiki/Graph_theory 69. https://en.wikipedia.org/wiki/Vertex_(graph_theory) 70. https://en.wikipedia.org/wiki/Edge_(graph_theory) 71. https://en.wikipedia.org/wiki/Dijkstra's_algorithm 72. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-dibbelt2015-1 73. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 74. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 75. https://en.wikipedia.org/wiki/Automotive_navigation_system 76. https://en.wikipedia.org/wiki/Journey_planner 77. https://en.wikipedia.org/wiki/Traffic_simulation 78. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 79. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-dibbelt2015-1 80. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-delling09-4 81. https://en.wikipedia.org/wiki/Open-source_software 82. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-5 83. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-6 84. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-7 85. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-8 86. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-RoutingKit-9 87. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=1 88. https://en.wikipedia.org/wiki/Shortest_path_problem 89. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-dibbelt2015-1 90. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 91. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=2 92. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 93. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 94. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=3 95. https://en.wikipedia.org/wiki/NP-completeness 96. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-10 97. https://en.wikipedia.org/wiki/Heuristic_(computer_science) 98. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 99. https://en.wikipedia.org/wiki/Computational_complexity_theory 100. https://en.wikipedia.org/wiki/Greedy_algorithm 101. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 102. https://en.wikipedia.org/wiki/Level_(logarithmic_quantity) 103. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-11 104. https://en.wikipedia.org/wiki/Approximation_algorithm 105. https://en.wikipedia.org/wiki/Nested_dissection 106. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 107. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-12 108. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-13 109. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=4 110. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 111. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 112. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 113. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=5 114. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 115. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 116. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=6 117. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 118. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 119. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 120. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-dibbelt2015-1 121. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=7 122. https://en.wikipedia.org/wiki/Global_Positioning_System 123. https://en.wikipedia.org/wiki/Traffic_simulation 124. https://en.wikipedia.org/w/index.php?title=Route_prediction&action=edit&redlink=1 125. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 126. https://en.wikipedia.org/wiki/Geographical_distance 127. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 128. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 129. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 130. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-geisberger12-3 131. https://en.wikipedia.org/wiki/Parallel_computing 132. https://en.wikipedia.org/wiki/Cache_(computing) 133. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-14 134. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 135. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 136. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 137. https://en.wikipedia.org/wiki/Electric_vehicle 138. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-bast2016-2 139. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=8 140. https://en.wikipedia.org/wiki/Highway_dimension 141. https://en.wikipedia.org/wiki/Tree-depth 142. https://en.wikipedia.org/wiki/Treewidth 143. https://en.wikipedia.org/wiki/Highway_dimension 144. https://en.wikipedia.org/wiki/Highway_dimension 145. https://en.wikipedia.org/wiki/NP-hardness 146. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-15 147. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-16 148. https://en.wikipedia.org/wiki/Parameterized_complexity 149. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-17 150. https://en.wikipedia.org/wiki/Highway_dimension 151. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-Abraham2010-18 152. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-ReferenceA-19 153. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-ReferenceB-20 154. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=9 155. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-Funke2015-21 156. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=10 157. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-22 158. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-ReferenceA-19 159. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-ReferenceB-20 160. https://en.wikipedia.org/wiki/Tree-depth 161. https://en.wikipedia.org/wiki/Treewidth 162. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-Funke2015-21 163. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-Abraham2010-18 164. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_note-Abraham2010-18 165. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=11 166. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-dibbelt2015_1-0 167. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-dibbelt2015_1-1 168. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-dibbelt2015_1-2 169. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-dibbelt2015_1-3 170. https://en.wikipedia.org/wiki/ArXiv_(identifier) 171. https://arxiv.org/abs/1402.0402 172. https://en.wikipedia.org/wiki/Doi_(identifier) 173. https://doi.org/10.1145/2886843 174. https://en.wikipedia.org/wiki/S2CID_(identifier) 175. https://api.semanticscholar.org/CorpusID:5247950 176. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-0 177. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-1 178. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-2 179. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-3 180. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-4 181. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-5 182. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-6 183. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-7 184. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-8 185. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-9 186. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-10 187. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-11 188. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-12 189. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-13 190. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-14 191. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-15 192. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-16 193. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-bast2016_2-17 194. https://en.wikipedia.org/wiki/ArXiv_(identifier) 195. https://arxiv.org/abs/1504.05140 196. https://en.wikipedia.org/wiki/Doi_(identifier) 197. https://doi.org/10.1007/978-3-319-49487-6_2 198. https://en.wikipedia.org/wiki/ISBN_(identifier) 199. https://en.wikipedia.org/wiki/Special:BookSources/978-3-319-49486-9 200. https://en.wikipedia.org/wiki/S2CID_(identifier) 201. https://api.semanticscholar.org/CorpusID:14384915 202. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-0 203. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-1 204. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-2 205. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-3 206. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-4 207. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-5 208. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-6 209. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-geisberger12_3-7 210. https://publikationen.bibliothek.kit.edu/1000028701 211. https://en.wikipedia.org/wiki/Doi_(identifier) 212. https://doi.org/10.1287/trsc.1110.0401 213. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-delling09_4-0 214. https://en.wikipedia.org/wiki/Doi_(identifier) 215. https://doi.org/10.1007/978-3-642-02094-0_7 216. https://en.wikipedia.org/wiki/ISBN_(identifier) 217. https://en.wikipedia.org/wiki/Special:BookSources/978-3-642-02093-3 218. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-5 219. http://project-osrm.org/ 220. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-6 221. http://www.opentripplanner.org/ 222. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-7 223. http://graphhopper.com/ 224. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-8 225. https://github.com/ifsttar/Tempus 226. https://en.wikipedia.org/wiki/GitHub 227. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-RoutingKit_9-0 228. https://github.com/RoutingKit/RoutingKit 229. https://en.wikipedia.org/wiki/GitHub 230. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-10 231. https://publikationen.bibliothek.kit.edu/1000014952 232. https://en.wikipedia.org/wiki/Doi_(identifier) 233. https://doi.org/10.1145/1671970.1671976 234. https://en.wikipedia.org/wiki/ISSN_(identifier) 235. https://search.worldcat.org/issn/1084-6654 236. https://en.wikipedia.org/wiki/S2CID_(identifier) 237. https://api.semanticscholar.org/CorpusID:1661292 238. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-11 239. https://en.wikipedia.org/wiki/Doi_(identifier) 240. https://doi.org/10.1007/978-3-540-68552-4_24 241. https://en.wikipedia.org/wiki/ISBN_(identifier) 242. https://en.wikipedia.org/wiki/Special:BookSources/9783540685524 243. https://en.wikipedia.org/wiki/S2CID_(identifier) 244. https://api.semanticscholar.org/CorpusID:777101 245. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-12 246. https://doi.org/10.1016/j.tcs.2016.07.003 247. https://en.wikipedia.org/wiki/Doi_(identifier) 248. https://doi.org/10.1016/j.tcs.2016.07.003 249. https://en.wikipedia.org/wiki/ISSN_(identifier) 250. https://search.worldcat.org/issn/0304-3975 251. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-13 252. https://en.wikipedia.org/wiki/CiteSeerX_(identifier) 253. https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.385.1580 254. https://en.wikipedia.org/wiki/Doi_(identifier) 255. https://doi.org/10.1109/ipdps.2011.108 256. https://en.wikipedia.org/wiki/ISBN_(identifier) 257. https://en.wikipedia.org/wiki/Special:BookSources/978-1-61284-372-8 258. https://en.wikipedia.org/wiki/S2CID_(identifier) 259. https://api.semanticscholar.org/CorpusID:6884123 260. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-14 261. https://en.wikipedia.org/wiki/Doi_(identifier) 262. https://doi.org/10.1109/ipdps.2011.89 263. https://en.wikipedia.org/wiki/ISBN_(identifier) 264. https://en.wikipedia.org/wiki/Special:BookSources/978-1-61284-372-8 265. https://en.wikipedia.org/wiki/S2CID_(identifier) 266. https://api.semanticscholar.org/CorpusID:1419921 267. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-15 268. https://epubs.siam.org/doi/10.1137/16M1067196 269. https://en.wikipedia.org/wiki/ArXiv_(identifier) 270. https://arxiv.org/abs/1502.04588 271. https://en.wikipedia.org/wiki/Doi_(identifier) 272. https://doi.org/10.1137/16M1067196 273. https://en.wikipedia.org/wiki/ISSN_(identifier) 274. https://search.worldcat.org/issn/0097-5397 275. https://en.wikipedia.org/wiki/S2CID_(identifier) 276. https://api.semanticscholar.org/CorpusID:11339698 277. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-16 278. https://drops.dagstuhl.de/opus/volltexte/2019/11465 279. https://en.wikipedia.org/wiki/Doi_(identifier) 280. https://doi.org/10.4230/LIPIcs.IPEC.2019.4 281. https://en.wikipedia.org/wiki/ISBN_(identifier) 282. https://en.wikipedia.org/wiki/Special:BookSources/978-3-95977-129-0 283. https://en.wikipedia.org/wiki/S2CID_(identifier) 284. https://api.semanticscholar.org/CorpusID:166228480 285. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-17 286. https://en.wikipedia.org/wiki/Doi_(identifier) 287. https://doi.org/10.4230/LIPIcs.IPEC.2022.5 288. https://en.wikipedia.org/wiki/ISBN_(identifier) 289. https://en.wikipedia.org/wiki/Special:BookSources/978-3-95977-260-0 290. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-Abraham2010_18-0 291. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-Abraham2010_18-1 292. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-Abraham2010_18-2 293. https://www.microsoft.com/en-us/research/wp-content/uploads/2010/01/soda10.pdf 294. https://en.wikipedia.org/wiki/Doi_(identifier) 295. https://doi.org/10.1137/1.9781611973075.64 296. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-ReferenceA_19-0 297. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-ReferenceA_19-1 298. https://en.wikipedia.org/wiki/ArXiv_(identifier) 299. https://arxiv.org/abs/1402.0402 300. https://en.wikipedia.org/wiki/Doi_(identifier) 301. https://doi.org/10.1145/2886843 302. https://en.wikipedia.org/wiki/S2CID_(identifier) 303. https://api.semanticscholar.org/CorpusID:5247950 304. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-ReferenceB_20-0 305. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-ReferenceB_20-1 306. https://en.wikipedia.org/wiki/ArXiv_(identifier) 307. https://arxiv.org/abs/1504.03812 308. https://en.wikipedia.org/wiki/Doi_(identifier) 309. https://doi.org/10.1145/3173045 310. https://en.wikipedia.org/wiki/S2CID_(identifier) 311. https://api.semanticscholar.org/CorpusID:3395784 312. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-Funke2015_21-0 313. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-Funke2015_21-1 314. https://en.wikipedia.org/wiki/Doi_(identifier) 315. https://doi.org/10.1007/978-3-662-48971-0_41 316. https://en.wikipedia.org/wiki/ISBN_(identifier) 317. https://en.wikipedia.org/wiki/Special:BookSources/978-3-662-48971-0 318. https://en.wikipedia.org/wiki/Contraction_hierarchies#cite_ref-22 319. https://www.fmi.uni-stuttgart.de/documents/aaai2018.pdf 320. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=12 321. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&action=edit§ion=13 322. https://www.graphhopper.com/ 323. https://github.com/ifsttar/Tempus 324. https://github.com/RoutingKit/RoutingKit 325. http://project-osrm.org/ 326. http://www.opentripplanner.org/ 327. https://en.wikipedia.org/w/index.php?title=Contraction_hierarchies&oldid=1282016643 328. https://en.wikipedia.org/wiki/Help:Category 329. https://en.wikipedia.org/wiki/Category:Graph_algorithms 330. https://en.wikipedia.org/wiki/Category:Search_algorithms 331. https://en.wikipedia.org/wiki/Category:Routing_algorithms 332. https://en.wikipedia.org/wiki/Category:Articles_with_short_description 333. https://en.wikipedia.org/wiki/Category:Short_description_is_different_from_Wikidata 334. https://en.wikipedia.org/wiki/Wikipedia:Text_of_the_Creative_Commons_Attribution-ShareAlike_4.0_International_License 335. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Terms_of_Use 336. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy 337. https://wikimediafoundation.org/ 338. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy 339. https://en.wikipedia.org/wiki/Wikipedia:About 340. https://en.wikipedia.org/wiki/Wikipedia:General_disclaimer 341. https://en.wikipedia.org/wiki/Wikipedia:Contact_us 342. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct 343. https://developer.wikimedia.org/ 344. https://stats.wikimedia.org/#/en.wikipedia.org 345. https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement 346. https://en.m.wikipedia.org/w/index.php?title=Contraction_hierarchies&mobileaction=toggle_view_mobile 347. https://www.wikimedia.org/ 348. https://www.mediawiki.org/ 349. https://en.wikipedia.org/wiki/Contraction_hierarchies

Hidden links: 351. https://en.wikipedia.org/wiki/File:Shortcut_in_a_shortest_path.svg 352. https://en.wikipedia.org/wiki/File:Iterated_contractions_on_line_graph.gif 353. https://en.wikipedia.org/wiki/File:Search_space_of_CH.svg 354. https://en.wikipedia.org/wiki/Contraction_hierarchies 355. https://en.wikipedia.org/wiki/Contraction_hierarchies 356. https://en.wikipedia.org/wiki/Contraction_hierarchies 357. https://en.wikipedia.org/wiki/Contraction_hierarchies 358. https://en.wikipedia.org/wiki/Contraction_hierarchies 359. https://en.wikipedia.org/wiki/Contraction_hierarchies 360. https://en.wikipedia.org/wiki/Contraction_hierarchies