Customizable Contraction Hierarchies
Customizable Contraction Hierarchies
复制标题
DOI：
10.1145/2886843
复制
发表时间：
2014-02
期刊：
影响因子：
--
通讯作者：
Julian Dibbelt;Ben Strasser;D. Wagner
中科院分区：
文献类型：
--
作者：
Julian Dibbelt;Ben Strasser;D. Wagner
我们考虑了快速计算加权图中最短路径的问题。通常，这是在两个阶段中实现的：（1）在昂贵的预处理阶段得出辅助数据，（2）使用此辅助数据来加快查询阶段。通过添加快速的重量量化阶段，我们扩展了收缩层次结构以支持三相工作流。昂贵的预处理被分为一个相位，仅将图形的未加权拓扑和轻巧的相位调整为特定重量的轻量级阶段。我们通过将可自定义的收缩层次结构（CCH）基于嵌套解剖令来实现。我们在大道路和游戏地图上提供了深入的实验分析，表明CCH是一个非常可行的解决方案，在边缘权重经常变化的情况下。
We consider the problem of quickly computing shortest paths in weighted graphs. Often, this is achieved in two phases: (1) derive auxiliary data in an expensive preprocessing phase, and (2) use this auxiliary data to speed up the query phase. By adding a fast weight-customization phase, we extend Contraction Hierarchies to support a three-phase workflow. The expensive preprocessing is split into a phase exploiting solely the unweighted topology of the graph and a lightweight phase that adapts the auxiliary data to a specific weight. We achieve this by basing our Customizable Contraction Hierarchies (CCHs) on nested dissection orders. We provide an in-depth experimental analysis on large road and game maps showing that CCHs are a very practicable solution in scenarios where edge weights often change.