地图导航算法 #04：Hub Labeling

Hub Labeling 为每个节点预计算一个「标签集」（到一批关键 Hub 节点的距离），查询时只需对两个标签集做交集运算，无需任何图遍历，查询延迟约 0.1ms，是 Google Maps 和 Apple Maps 主干路网的核心算法。

相关文章：Contraction Hierarchies · Customizable Contraction Hierarchies

目录

核心思想

Cover Property

Hub Labeling 建立在一个关键性质上：

对图中任意两点 S 和 G，S→G 的最短路上至少有一个节点 h，同时出现在 L(S) 和 L(G) 中。

只要满足这个性质，查询时遍历两个标签集的交集，取 dist(S,h) + dist(G,h) 的最小值，就能得到正确答案——不需要在图上做任何搜索。

标签集定义

每个节点 v 维护两个标签集：

查询 dist(S, G)：

answer = min over h in L_fwd(S) ∩ L_bwd(G) of:
           dist_fwd(S, h) + dist_bwd(G, h)

预处理：标签集构建

Pruned Hub Labeling（PHL）

朴素方案（全量标签）：令所有节点都是 Hub，每个节点存到所有节点的距离。这等同于 All-Pairs Shortest Path，O(N²) 存储，不可行。

PHL 的关键：只保留必要的标签，剪掉冗余的。

基于 CH 节点顺序（order）构建：

for 每个 Hub h（按 order 从高到低）：
  从 h 出发做 Dijkstra：
    for 每个到达节点 v（dist = d）：
      if 当前 L_bwd(v) 已能通过已有标签推导出 dist(h, v)：
        剪枝（pruning），不加入 L_bwd(v)
      else：
        L_bwd(v).add(h, d)
  对称地处理 L_fwd

剪枝条件：在处理 Hub h 时，若已处理的更高层级 Hub 集合已能给出 v→h 的正确距离，则 h 不需要再加入 L(v)。

这保证每个标签集只保留「不可被其他标签推导出」的条目，使标签集大小最小化。

预处理复杂度

查询：标签集交集

查询算法

double query(int S, int G) {
    double best = Double.MAX_VALUE;
    // 两个有序列表归并求交集（类似 merge sort）
    int i = 0, j = 0;
    while (i < fwdLabel[S].size() && j < bwdLabel[G].size()) {
        long hi = fwdLabel[S].getHub(i);
        long hj = bwdLabel[G].getHub(j);
        if (hi == hj) {
            double candidate = fwdLabel[S].getDist(i) + bwdLabel[G].getDist(j);
            best = Math.min(best, candidate);
            i++; j++;
        } else if (hi < hj) {
            i++;
        } else {
            j++;
        }
    }
    return best;
}

关键优化：标签集按 Hub ID 排序存储，交集操作退化为双指针归并，时间复杂度 O(|L_fwd(S)| + |L_bwd(G)|)。

查询复杂度

路径重建

查询只返回距离。若需要完整路径：

1. 找到最优 Hub h*
2. 展开 S → h*：从 fwdLabel[S] 中找到通向 h* 的中间节点，递归展开
3. 展开 h* → G：从 bwdLabel[G] 中递归展开
4. 拼接两段路径

路径重建需要额外存储父节点信息，使标签集体积增加约 50%。

存储与内存开销

标签集大小

对道路网络（二维平面图），每个节点的平均标签集大小约为：

|L| ≈ O(√N · log N)

实测（德国路网，2000 万节点）：

Hub Labeling 的代价是巨大的内存：全球路网约需 100GB+ RAM，这是它只用于主干路网的原因。

压缩策略

• 分级存储：主干路网（高速公路）用 Hub Labeling，局部路网用 CH
• 标签压缩：相邻节点标签集差异较小，可做差分编码
• 只存距离，按需重建路径：减少 50% 内存，路径查询时多做一次 BFS

与 CH 对比

选型原则：内存充足、查询极高频（> 百万次/秒）→ Hub Labeling；通用场景 → CH；支持实时路况 → CCH。

实际应用

Google Maps

Google Maps 的路由实现细节未公开，但其性能特征与 Hub Labeling 高度一致。公开信息显示：

• 主干高速公路层级（全球约 1000 万节点）内存可控，适合 HL 的高内存换极速查询模式
• 查询极快，支持每秒数千万次路由请求
• 局部路网（城市街道）节点密集，通常采用 CH 而非 HL

注：2012 年收购的 ITA Software 提供的是航班票价搜索引擎（QPX），与道路路由算法无直接关联。

Apple Maps

Apple Maps 路由实现细节未公开。苹果 2013 年收购 Coherent Navigation 是为了 GNSS 精度增强技术（基于 LEO 卫星的 GPS 修正），与路由算法无关。头部地图服务普遍在主干路网采用 HL 架构，Apple Maps 极可能也不例外，但无公开资料证实具体算法选型。

RoutingKit

RoutingKit（开源，KIT 大学）是 Hub Labeling 最优秀的开源实现：

• 提供完整的 CH + HL 工具链
• 在 64 核服务器上预处理欧洲路网约 2 小时
• 查询延迟 < 0.2ms

参考资料

参考资料

• Abraham et al., Hub Label Compression (ACM SODA 2012) — PHL 奠基论文
• Contraction Hierarchies（HL 预处理依赖 CH 的节点 order）
• Customizable Contraction Hierarchies（支持实时路况的演进方向）