Gems of Combinatorial Optimization and Graph Algorithms by Andreas S. Schulz Martin Skutella Sebastian Stiller & Dorothea Wagner

Author:Andreas S. Schulz, Martin Skutella, Sebastian Stiller & Dorothea Wagner
Language: eng
Format: epub
Publisher: Springer International Publishing, Cham

Remarkably, the correctness of the CH query is still guaranteed if additional “unnecessary” edges are added during the preprocessing phase, as long as the weight of such an edge (y, z) is assigned the length of a shortest yz-path.

2.2 Implementing Contraction Hierarchies

Determining whether yxz is a shortest yz-path is called witness search. The straight-forward approach consists of running Dijkstra’s algorithm on to find a shortest yz-path in . However, this can be too slow to work on huge graphs. One idea is to abort the witness search at some point and insert the shortcut (y, z) anyway, independently of whether yxz is a shortest yz-path or not. This might result in adding unnecessary shortcuts which make the query phase slower, but fortunately not incorrect.

A heuristic approach to come up with a “good” contraction hierarchy consists in ordering the vertices by ascending “importance.” Unfortunately, there is no universal definition for importance of a vertex in a graph. In road graphs “importance” is usually based on the intuition that a vertex on a highway is important whereas a dead-end of a street in a rural area is unimportant.

A contraction ordering may be computed by exploring all possible vertex contractions and greedily picking the vertex that results in the fewest shortcuts and assigning it a low “importance,” i.e., we iteratively try to identify dead-end-like structures. This strategy can be refined with further heuristics that try to assure that G is contracted uniformly. A different top-down heuristic consists in iteratively assigning a high “importance” to a vertex that covers many shortest paths, i.e., vertex x that covers as many paths as possible gets highest importance and next the vertex y that covers as many paths as possible not already covered by x is determined, and so on. The idea is that many shortest paths traverse highways. For references, see Sect. 5. Note that these strategies and the quality of the resulting CH depend on the weight function of G. An ordering that leads to a “good” contraction hierarchy for a weight function can lead to a huge number of shortcuts when used with another weight function on the same graph G. Even correlated weights such as travel-time and travel-distance in road graphs are not interchangeable in practice.

The next two sections are devoted to these two aspects: How can we determine a contraction ordering for which we can give a guarantee for the size of the search space? How can we construct a weight-independent contraction ordering and design a three-phase shortest path algorithm?

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.