Customizable Contraction Hierarchies

2014/02/03 by Dibbelt, Julian, Strasser, Ben, Wagner, Dorothea · 1 citation
#Artificial Intelligence (cs.AI) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences

paper · doi:10.48550/arxiv.1402.0402

Abstract

We consider the problem of quickly computing shortest paths in weighted graphs given auxiliary data derived in an expensive preprocessing phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies by Geisberger et al to support the three-phase workflow introduced by Delling et al. Our Customizable Contraction Hierarchies use nested dissection orders as suggested by Bauer et al. We provide an in-depth experimental analysis on large road and game maps that clearly shows that Customizable Contraction Hierarchies are a very practicable solution in scenarios where edge weights often change.

Cited by

• Parallel Point-to-Point Shortest Paths and Batch Queries

Related

• Combining the Connection Scan Algorithm with Contraction Hierarchies
• Time Dependent Contraction Hierarchies -- Basic Algorithmic Ideas
• Customizable Contraction Hierarchies -- A Survey
• Heuristic Contraction Hierarchies with Approximation Guarantee
• Doing More for Less -- Cache-Aware Parallel Contraction Hierarchies Preprocessing