Contraction Hierarchies

Contraction Hierarchies 通过「收缩不重要节点、添加快捷边」对路网进行预处理，将查询时的双向搜索空间从亿级压缩到数千节点，单次查询 < 1ms，是 OSRM、GraphHopper 等工业导航引擎的核心算法。

相关文章：双向搜索 · Hub Labeling · Customizable Contraction Hierarchies

目录

核心思想

Dijkstra 和 A* 在亿级路网上仍然太慢，根本原因是搜索空间太大。CH 的突破在于：

把路网分成「重要性层级」，查询时只走高速公路层级，自动跳过小路细节。

类比：从北京开车到上海，你不会考虑胡同，只关心高速公路。CH 将这个直觉形式化：

预处理（离线，一次性）：
  按重要性从低到高，逐步"收缩"不重要节点
  → 每次收缩添加快捷边，保证路径长度不变
  → 形成多层级叠加的增强图

查询（在线，< 1ms）：
  双向搜索，但只允许向更高层级节点扩展
  → 搜索空间从亿级压缩到数千节点

预处理：节点收缩

收缩一个节点

收缩节点 v 的步骤：

1. 枚举所有以 v 为中间节点的路径：u → v → w
2. 检查是否有其他绕过 v 的最短路 u ↝ w（witness path）
3. 若无更短绕路：添加快捷边 u → w，权重 = dist(u,v) + dist(v,w)
4. 从图中删除 v 及其关联边

快捷边的语义：u → w (cost=5) 表示「原图中 u 到 w 的最短路经过已收缩节点，代价为 5」。

Witness Path 搜索

添加快捷边前，用局部 Dijkstra 搜索绕过 v 的最短路：

// 从 u 出发，不经过 v，能否找到 u→w 代价 ≤ dist(u,v)+dist(v,w)？
// 搜索深度限制（hop_limit）避免搜索过深
boolean hasWitness(int u, int v, int w, double maxDist, int hopLimit) {
    // 局部 Dijkstra，排除节点 v，限制跳数
    ...
}

优化：hop_limit 通常设为 5，在收缩速度和快捷边数量之间取平衡。

收缩顺序决定质量

节点的收缩顺序直接影响快捷边数量和查询性能。使用优先队列按重要性从低到高收缩：

priority(v) = w₁·EdgeDifference(v) + w₂·DeletedNeighbors(v) + w₃·Depth(v)

每次收缩后，受影响邻居节点的优先级需要重新计算（lazy update 近似）。

查询：双向层级搜索

层级约束

预处理后，每个节点都有一个层级编号（order）。查询时：

前向搜索（从 S 出发）：只沿 order[v] > order[u] 的边扩展
后向搜索（从 G 出发）：只沿 order[v] > order[u] 的边扩展（在反向图上）

这保证两个搜索前沿都只"向上爬"，最终在层级最高的节点附近相遇。

查询流程

初始化：distF[S]=0, distB[G]=0
双向优先队列交替展开：

  前向取出 u（distF 最小）：
    for 每条正向边 u→v（包括快捷边）：
      if order[v] > order[u]:       ← 只向上扩展
        松弛 distF[v]

  后向取出 u（distB 最小）：
    for 每条反向边 u→v（包括快捷边）：
      if order[v] > order[u]:
        松弛 distB[v]

  当两个队首之和 ≥ best 时停止（同双向 Dijkstra 终止条件）

路径解压

CH 返回的路径经过快捷边，需要递归解压还原为原始节点序列：

void unpack(int u, int w, List<Integer> path) {
    if (!isShortcut(u, w)) {
        path.add(w);
        return;
    }
    int mid = shortcutMidpoint(u, w);  // 快捷边跳过的中间节点
    unpack(u, mid, path);
    unpack(mid, w, path);
}

节点重要性指标

典型权重配比示例：EdgeDifference × 190 + DeletedNeighbors × 120 + Depth × 10（各实现权重不同，此为教学版参考值；实际系统通常用 lazy update 动态重计算优先级而非固定系数）。

性能数据

以西欧道路网络（约 1800 万节点，来自 Geisberger 2008 原论文基准）为参考：

CH 是预处理时间 / 查询速度权衡的最佳甜点：预处理一次，查询百亿次。

实际应用

OSRM（Open Source Routing Machine）

• 采用 CH 作为核心路由引擎
• 预处理完整 OSM 世界路网约需 20 分钟（64GB 内存服务器）
• 查询延迟 < 1ms，支持每秒数万次并发查询
• Mapbox 早期导航服务基于 OSRM

GraphHopper

• 支持 CH 和 Landmark（ALT）两种加速结构
• CH 适合高速点对点查询
• 支持实时路况（通过周期性重新预处理）

高德 / 百度地图

• 均基于 CH 变体 + 自研层次路网
• 结合浮动车实时路况（触发权重更新）
• 大规模集群分布式预处理

局限与演进

CH 的核心局限：快捷边在预处理时固化了边权。

若道路权重变化（拥堵、限速调整），必须重新预处理整张图，耗时数分钟——无法支持实时路况的秒级更新。

演进方向：

CH（静态权重，< 1ms 查询）
  ↓ 需要支持实时路况
Customizable CH (CCH)
  ↓ 将图结构与边权分离
  预处理：只处理图结构（一次性，数分钟）
  定制化：路况变化时只更新边权层（毫秒级）
  查询：同 CH（< 1ms）

详见 Customizable Contraction Hierarchies。

参考资料

参考资料

• Geisberger et al., Contraction Hierarchies: Faster and Simpler Hierarchical Routing in Road Networks (WEA 2008) — CH 原论文
• 双向搜索（CH 查询阶段的内核机制）
• Hub Labeling（查询更快但内存更重的方案）
• Customizable Contraction Hierarchies（支持实时路况的 CH 演进）