> A 是在 Dijkstra 的基础上引入启发函数 h(n) 的最短路径算法，用「到终点的估计代价」引导搜索方向，大幅减少无效节点的探索，是地图导航、游戏寻路的基础算法。 相关文章：双向搜索 · Contraction Hierarchies !astar search 目录 | 章节 …
2026-06-08
> 双向搜索同时从起点和终点向中间展开，两个搜索前沿相遇时即可合并路径；理论上将搜索空间从半径 r 的球体压缩为两个半径 r/2 的球体，节点展开量减少约 50%，是 Contraction Hierarchies 查询阶段的核心机制。 相关文章：A 算法 · Contraction Hierarchies !bidi…
2026-06-08
> Contraction Hierarchies 通过「收缩不重要节点、添加快捷边」对路网进行预处理，将查询时的双向搜索空间从亿级压缩到数千节点，单次查询 < 1ms，是 OSRM、GraphHopper 等工业导航引擎的核心算法。 相关文章：双向搜索 · Hub Labeling · Customizable Co…
2026-06-08
> Hub Labeling 为每个节点预计算一个「标签集」（到一批关键 Hub 节点的距离），查询时只需对两个标签集做交集运算，无需任何图遍历，查询延迟约 0.1ms，是 Google Maps 和 Apple Maps 主干路网的核心算法。 相关文章：Contraction Hierarchies · Custom…
2026-06-08
> Customizable Contraction Hierarchies（CCH）将 CH 的「图结构预处理」与「边权定制化」分离为两个独立阶段，图骨架一次性离线计算，路况变化时只需毫秒级重算权重层，从而同时兼顾 CH 的极速查询（< 1ms）和实时路况支持，是 Mapbox、必应地图的核心导航算法。 相关文章：C…
2026-06-08