2026-09-11

从最短路到路径构建：图是怎么被定义出来的

三个词不是并列关系

最短路径、寻路、路径构建，看起来是同一类话题的三个说法。实际上它们是同一个问题在三层抽象上的展开，而这三层的难度和成熟度差异极大：

这个分层有一个很重要的推论：绝大多数路径规划项目的瓶颈从来不是最短路算法，而是图怎么定义。

选 Dijkstra 还是 A*，通常只影响 10% 的运行时间；而节点、边、边权的定义方式，直接决定整个系统的上限。下面逐层展开。

一、最短路：算法选择由约束唯一决定

先把算法家族摆清楚。真正决定用哪个算法的不是"哪个更快"，而是三个约束：边权的符号、图的结构、查询的频率。

反直觉点一：堆优化不是永远更快

通常的叙述是"Dijkstra 用堆优化到 O((V+E)logV)"，好像堆优化是标配。但在稠密图（E ≈ V²）上，朴素的 O(V²) 线性扫描实现反而更快——堆的 log 因子白白付出，还带来额外的常数开销和缓存不友好。

结论：图密度决定实现方式，而不是"堆优化就是好的"。

反直觉点二：DAG 上不需要 Dijkstra

如果图是有向无环的，拓扑序一遍扫描就能算出所有单源最短路，而且是线性的，并且天然支持负权。

所以在动手之前，先问一句"我的图有环吗"，往往比问"该用哪个算法"价值大得多。很多真实问题的图结构其实自带很强的约束（依赖关系、流水线阶段、时间展开），这些约束直接消掉了大部分算法选择。

工业界真正的答案：预处理，而不是更快的搜索

一个常被忽略的事实：高德、Google Maps 这类导航系统每天要处理几十亿次路径查询。每次跑一遍 Dijkstra 是完全不可想象的。

它们用的是「预处理 + 极快查询」的路线：

• Contraction Hierarchies（CH）：按"重要性"给节点排序，依次把不重要的节点"收缩"掉，并为被绕过的路径补上捷径边。查询时只在剩下的高层图上搜索，再展开捷径还原成真实路径。
• Hub Labeling：预计算每个节点到一组 hub 的距离标签，查询时只做标签交集。
• CRP（Customizable Route Planning）：把预处理拆成"拓扑预处理"和"权重定制"两阶段，从而支持路况实时更新。

这些方法在大陆级路网上能把查询从秒级压到毫秒乃至微秒级，三到五个数量级的加速。

背后的结构性先验非常朴素：几乎所有的长距离出行都是「先上主干道或高速，到接近目的地时再下来」。把这个先验预计算进索引，搜索空间就从百万节点掉到几百节点。

这里的关键洞察是：最短路的真正瓶颈是「重复查询」，而不是「单次查询」。 只查一次，Dijkstra 就够；要查十亿次，预处理才划得来。这是一个典型的"用空间和预处理换查询时间"的工程权衡，而不是算法理论问题。

二、寻路：当图不可知或巨大

A* 的骨架是 f(n) = g(n) + h(n)：已走代价加上对剩余距离的估计。真正有讨论价值的是 h 从哪来：

• 几何启发式：欧氏距离、曼哈顿距离。简单，但在有障碍物时很松。
• 地标法（ALT）：预先挑若干 landmark 节点，利用三角不等式 |d(A,L) − d(L,B)| ≤ d(A,B) 构造下界。这是"用预处理换启发式强度"的又一例。
• 学出来的启发式：Neural A*、用 GNN 直接从图结构预测 h。近年的研究热点。

反直觉点三：h 不是越准越好

这是我觉得最值得反复咀嚼的一点。

• h 高估真实距离 → 不再 admissible → 失去最优性保证。搜索会变快，但可能返回次优解。
• h 过强 → 退化成纯贪心。搜索变得近视，"看起来近"的节点被优先展开，全局结构被忽略。

你要的其实是：刚好乐观。宁可低估，不可高估。这个"乐观性"约束是 A* 正确性的全部来源。

与之配套的另一个概念是 consistency（一致性）：满足 h(n) ≤ c(n,n') + h(n')。一致性比可采纳性更强，它保证节点不需要被重新打开。可采纳性保证最优，一致性保证效率——两者容易混淆，但作用完全不同。

网格地图上的两个必要技巧

• JPS（Jump Point Search）：网格上存在大量对称路径，JPS 利用这一点，一次跳跃掠过整段直线，把搜索规模砍掉一个数量级。
• **Theta***：允许任意角度的路径段，避免路径被网格"咬"成锯齿。这类方法统称 any-angle path planning。

连续空间：干脆不建图

机器人领域的大量问题（机械臂、无人机、自动驾驶的局部规划）根本没有离散图。做法是采样：

• **RRT / RRT***：从起点长一棵随机树，向采样点扩展，RRT* 额外做重连优化。
• PRM（概率路线图）：预先在自由空间撒点连边，建成一张稀疏图，之后在其上反复查询。

关键共同点：从不构建全局图，只在需要的地方生成局部结构。

环境会变：增量修复而非重算

D* Lite 是这一类问题的代表：当环境发生变化（新障碍物出现），它不重新规划，而是增量修复受影响的局部子图。火星车、仓储机器人用的就是这一族算法。

三、图构建：真正的难点在这里

前面两层都有成熟解法。到了这一层，问题变成"图从哪来"，而这几乎总是项目成败的分水岭。

3.1 定义节点和边，本身就是建模决策

节点选什么？

• 路口图（node = 交叉路口）：最直观，但转向代价无处安放。左转和直行在图上都是"两条边的连接"，可实际代价能差十倍。要塞进转向代价，就只能给每条边挂上入口边的信息，或者给每个转向建一个节点——图迅速膨胀。
• 路段图（node = 路段）：转向代价变成节点代价，干净利落，代价是节点数上升。
• 线图（line graph）：把原图的边提升为节点，是处理转向代价的标准做法。

这几种选择没有绝对优劣，只有"你的代价模型是什么"。

边权是什么？

距离？时间？拥堵概率？能耗？景观？一旦涉及多个目标，**"最短路"这个概念本身就不存在了**——剩下的只有 Pareto 前沿：在所有目标上都不被支配的解集合。

更麻烦的是时变图 w(e, t)，见下一节。

3.2 图从数据里长出来

最后一行值得特别强调：从人的实际选择反推边权，会得到一个和"理论最短路"很不一样的图。这是第四节最后一条的伏笔。

3.3 隐式图：不构建，按需展开

这是我最想推荐的一个技巧。

有些状态空间根本不可能存下来：

• 八数码：约 1.8×10⁵ 个可达状态，勉强能存，但已经不小
• 魔方：4.3×10¹⁹ 个状态——无论用什么硬件都存不下。人类最终的解法是双向 BFS 配合模式数据库，用几十年时间算出了"上帝之数 = 20"（任意状态 20 步内可解）

但注意：这些问题的图在数学上真实存在，在程序里从不落地。你只需要提供一个生成函数：

def neighbors(state):
    """返回从 state 一步可达的所有后继状态"""
    ...

搜索算法只和这个函数打交道。整张图是"按需展开"的。

这个技巧在处理 agent 问题时是刚需，因为 agent 的状态空间同样是组合爆炸且无法枚举的。

3.4 图是"构造"出来的，不是"发现"的

"构建"二字真正的重量在这里。

层次图：先建骨架层（高速、主干），再挂细节层。CH 本质上就是把层次结构预计算出来。这类"分而治之 + 层次抽象"的思想在几乎所有大规模图问题上都会重现。

图嵌入：node2vec、DeepWalk 把节点映射到向量空间，让"相似"变成"距离"。这一步把建图问题转化成了表示学习问题——边不再需要显式定义，而是在嵌入空间里隐式存在。

超图（hypergraph）：普通图的边只能连两个点。但"三位作者合写一篇论文"是一个三元关系，用普通图表示就必须拆成三条两两的边，信息就失真了。超图允许一条边连任意多个节点。

AND-OR 图：化学逆合成路径的典型结构。一步反应需要多个前体同时满足，是乘法关系而不是加法关系。这意味着最优子结构不成立——"到达某个中间产物的最优代价"无法独立定义，标准最短路算法直接失效。

多层图 / 时序图：边带类型（地铁、公交、步行可换乘）或带时间戳。城市多模态出行规划就是典型的多层图问题。

四、跳出"路"这个框架

"路径构建"是一个比道路导航宽得多的抽象。以下五个领域共享几乎完全相同的底层结构。

4.1 Agent 的工具调用 = 图上的一条路

把 agent 的决策过程形式化：

• 节点 = (当前状态, 已调用的工具集合)
• 边 = 一次工具调用
• 最短路 = 以最少步数 / 最低代价完成任务

这与 A* 严格同构：f = 已花代价 + h(离完成的距离估计)。

而所有难点都落在图构建上：

• 状态空间组合爆炸 → 是隐式图，必须提供生成函数而不是显式图
• 边权是动态的：工具成功率、token 成本、延迟、是否触发人工审批
• 节点不可逆：有副作用的操作不能"回退"，图是有向的但带"毒"——走错一步的代价不是重新搜索，而是造成了真实世界的改变

这也解释了为什么工具编排（skill chain、工作流组合）本质上是在技能图上找路；而对这类系统做故障注入（mutation testing），本质上是给这张图注入边故障——两者研究的是同一个对象的两面。

4.2 LLM 推理 = 隐式图上的启发式搜索

这个类比我认为是本节最有价值的一条：

如果接受这个映射，那么一个有意思的结论自然浮现：

"幻觉"在搜索的语言里，就是 h 不可采纳——模型高估了"当前推理到正确答案"的距离。

于是"模型过度自信"和"启发式过强"变成了同一个失效模式：h 骗过了搜索，把它导向一条看起来短、实际不存在或通向错误终点的路。这个统一视角在讨论推理可靠性时相当有用，因为它把"模型能力问题"翻译成了"搜索正确性问题"，而后者有几十年的理论工具可用。

4.3 肉鸽的通路：未知图 + 预算约束

Roguelike / 集成战略这类玩法，把路径问题的难度直接拉满：

• 节点 = 房间 / 事件，边 = 可选路线，但图和代价都藏在战争迷雾里
• 这是未知图上的在线搜索，天然包含 explore / exploit 权衡
• 资源上限（希望、源石锭）构成预算约束 → 属于 Resource Constrained Shortest Path，NP-hard
• 更根本的是：因为路线本身不确定，目标函数不是"路径最短"，而是"期望收益最大" → 问题从最短路退化成 MDP 求策略

这是一个很好的例子，说明一旦引入不确定性，最短路框架就不够用了，必须升级到决策过程。

4.4 GPU 计算图

在编译器和 kernel 优化里：

• 算子融合 = 在数据流图上找"合并收益最大"的路径
• 融合的约束（显存占用、寄存器压力、shape 对齐）就是图上不可行的边
• 代价函数高度非线性，可加性不成立（融合两个算子的收益不是各自收益之和）

所以这不是最短路问题，而是带约束的图划分 / 图重写问题。把它当成最短路来做会直接跑偏。

4.5 制度与审批流

一个组织里，一份文件过哪些环节，本质上是一条路径，边权 = 时效 / 权限 / 风险。

但这里有个关键差异：当规则本身可以在运行时改变时，图是动态的。制度即插件的系统里，节点和边都会在运行过程中增删——静态最短路算法需要升级为动态图上的增量维护。

而且这里想要的根本不是"最短路"：真正的目标是"最合法、最不容易被驳回、最经得起追溯的路径"——天然多目标。

五、几个反复出现的"怪物"

以下六个坑我倾向于反复提醒自己：

1. 时变图破坏 FIFO 假设

如果边权随时间变化，且不满足 FIFO（早出发一定不晚到），Dijkstra 的正确性直接崩塌。而现实中这恰恰很常见：高峰期出发反而更慢、某条路的拥堵随时间演化、班次表本身就是时变的。

理论上很干净，实践上非常脏。这是几乎所有真实导航系统都要专门处理的坑。

2. AND-OR 结构：最优子结构不成立

一旦某个"步骤"需要多个前提同时满足，代价结构就从加法变成乘法或更复杂的组合，"到达某个中间状态的最优代价"这个中间量根本无法独立定义。动态规划的地基被抽掉了。

3. 资源受限最短路是 NP-hard

既要求路径代价最优，又要求资源（时间、油量、预算）不超限，属于 Resource Constrained Shortest Path，NP-hard。在实际工程中，近似算法和解的"够好性"比精确最优重要得多。

4. 脏数据才是主要矛盾

路径规划项目真实的成本结构大致是：90% 的时间在清理和校验数据，10% 的时间在跑算法。

拓扑错误、坐标漂移、属性缺失、口径不一致——这些才是让项目失败的东西。算法选型错误几乎从来不是。

5. 用户要的不是最短

人的实际选路系统性偏离最短路假设。人们偏好熟悉的路、少转向的路、景观好的路、不容易走错的路。

于是导航系统有时会故意推荐次优路径，因为用户"觉得"它更快，或者因为它更容易被理解和跟随。

一条可解释的次优路，往往胜过一次不可解释的最优路。

6. 图的定义比图的算法重要

这是贯穿全文的主线。当你发现某个路径规划效果不好时，先别急着换算法——回去看看节点是怎么定义的、边权代表什么、哪些真实约束没有被编码进去。

六、如果动手，建议的顺序

按"手感 → 震撼 → 理论 → 迁移"四步走：

第一步（约半天）：建立图长什么样的手感

用 OSMnx 拉一个真实城市的路网，转成 NetworkX 图，跑一遍 Dijkstra 和 A*。重点不是学会 API，而是观察真实路网的度数分布、边权分布、连通性——真实图和数据结构的课本图相差很远。

第二步（约 2~3 天）：亲手实现一次 CH，感受结构化先验的价值

自己写一遍节点收缩和捷径添加，然后对比查询耗时。当你看到几万倍加速时，会对"预处理换查询"这件事产生完全不同的直觉——这是全文最值钱的一课。

第三步（约 1 天）：八数码，理解隐式图与启发式强度

用同一份 neighbors() 生成函数，分别跑 BFS、A*（弱 h）、A*（强 h）、IDA*，对比展开节点数和结果质量。亲手体会一次"h 太强会破坏最优性"，比读十遍定义管用。

第四步：迁移到 agent 场景

把一次 agent 执行的工具调用日志构造成图（节点 = 状态，边 = 调用），跑最短路问"理论上最少几步能完成"，再和实际路径对比。实际的冗余步数就是优化空间，而偏离最优的位置就是编排逻辑的薄弱点。

结语

最短路径、寻路、路径构建这三个词，本质上描述的是同一件事在不同抽象层上的样子。往下走到最短路，问题已经在 1959 年被解决，剩下的只是工程优化；往上走到路径构建，问题变成"什么才是一个节点"——而这从来不是算法问题，是建模问题。

同一套结构在导航、机器人、LLM 推理、agent 编排、GPU 编译、组织流程中反复出现，而且每次都是图的定义方式决定上限，算法选择只影响常数。

所以下次面对一个"找路"问题时，值得先问的不是"该用什么算法"，而是：

我的节点是什么？我的边是什么？我漏掉了哪些真实约束？