Light Contraction Hierarchies: Hierarchical Search Without Shortcuts

Authors

  • Claudius Proissl Universit├Ąt Stuttgart

Keywords:

Time, Memory, And Solution Quality Trade-offs, Real-life Applications, Real-time Search, Search In Goal-directed Problem Solving

Abstract

Hierarchical search such as Contraction Hierarchies is a popular and successful branch of optimization techniques for shortest path computation. Existing hierarchical techniques have one component in common: they add edges to the graph, so called shortcuts. This component usually causes a considerable space overhead but is mandatory in order to preserve correctness. In this work we show a hierarchical method that requires to store only one additional number per node and no shortcuts at all. We prove the correctness of our method and experimentally show that it improves query times by one order of magnitude compared to Dijkstra's bidirectional algorithm.

Downloads

Published

2022-07-17