shortest-path · 最短路径

最短路径：拆解 Dijkstra

从一个点出发，到图里每个 vertex 的 shortest path 如何计算？先理解 relaxation 这个唯一的内核动作——不断用「经某点中转是否更近」把 distance estimate 向真实值收紧；再单步运行 Dijkstra 的 greedy：每次 extract-min 当前未 settle 的 vertex、将它 settle、relax 它的所有出边。随后看几种 case:有 cycle 不影响正确性，而一条 negative-weight edge 就能让「取出即 settle」的 greedy 误锁一个次优值——这正是 Dijkstra 的适用边界。最后为它加上「方向感」：把排序键从 g 换成 f = g + h 即得到 A*。每节都能选源点、单步运行，观察 dist[] / prev[] 表与 priority queue 的实时变化。底层的 priority queue 与「乐观界」分别由 binary heap 和分支限界两个系列展开，可作为延伸阅读。

五节：relaxation 与 greedy → 动手跑 Dijkstra → 各种 case → A* 搜索 → 真实应用。

1 · 核心动作：relaxation 与 greedy 为何成立

整个 shortest path 算法，内核只有一个动作——relaxation。理解它之后，Dijkstra、Bellman-Ford 都只是「按什么顺序、relax 多少次」的不同包装。

给每个 vertex 维护一个 dist[v]——「目前已知的、从源到 v 的 shortest path distance」。它始终是真实 shortest path distance 的一个 estimate 上界：一开始除源点为 0 外全是 ∞，随着我们发现更短的走法而单调下降，最终收敛到真实值。

relax 一条 edge $u\to v$ (weight w)就是问一句：「先到 u 再走这条 edge，会不会比现在已知的到 v 更近？」

即：若 dist[u] + w < dist[v]，就更新 dist[v] = dist[u] + w，并记 prev[v] = u（记住这一步是从 u 过来的，便于回溯整条路径）。

下面这张小图从 A 出发。点「relax 下一条 edge」会按一个固定顺序逐条尝试 relax（顺序见下方说明），观察 dist[] 如何从 ∞ 逐步收紧。有的 relaxation 会更新，有的不会（中转并不更近）；留意 D 会被收紧两次（先 6 再 4）——这正体现了「estimate 单调下降、逐步逼近真实值」。

本节 relax 顺序 = 按 Dijkstra「settle 顺序」 $A \to C \to B \to D$ 依次处理每个 vertex 的出边（一个 vertex settle 后才 relax 它的出边）。按这个恰当的顺序，每条 edge 各 relax 一遍就够了。

1.1 · 为什么 Dijkstra 的 greedy 是对的？（前提：非负 weight）

relaxation 本身不挑顺序；但若按某个恰当的顺序来，每个 vertex 只需被 settle 一次。Dijkstra 的顺序是：每次在所有未 settle 的 vertex 里，extract-min dist 当前最小的那个，断言它的 dist 已经是真实 shortest path 值，从此 settle。

归纳论证（直觉版）：设此刻 extract-min 得到的未 settle vertex 是 u，它的 dist[u] 在所有未 settle vertex 里最小。任何「还没走到 u」的其他路径，都得先经过另一个未 settle 的 vertex x 才能拐到 u；而到 x 的距离 ≥ dist[u]（因为 u 是当前最小），再加上后续非负的 edge weight，只会更大，不可能比 dist[u] 还小。所以没有更短的路了——u 的 dist 已确定，可 settle。

「非负」是前提条件。上面那句「后续 edge weight 只会让路更长」，一旦出现 negative-weight edge 就不再成立：绕远路、再走一条 negative edge，反而可能更短。于是「当前最小就一定是最终最短」的断言失效——这正是各种 case 一节 negative weight 反例的根源。

2 · 动手跑 Dijkstra:extract-min · settle · relax 出边

Dijkstra 就是「按 dist 从小到大的顺序 settle 每个 vertex」。一条主循环，反复做到没有可 settle 的 vertex 为止：

其一，从 priority queue（所有未 settle 且可达的 vertex）里 extract-min dist 最小的那个 u。

其二，把 u 标记为 settled——断言 dist[u] 就是真实 shortest path 值，从此不再改。

其三，relax u 的所有出边：对每条 u→v，若 dist[u]+w < dist[v] 就更新 v（并记 prev[v]=u）。

其四，回到第一步。

下面用一个含 cycle 图（A→B→C→D→A 是一个有向 cycle）。选源点，点「下一步」逐次 settle 一个 vertex。注意：settled vertex（绿）被 cycle 上的回边指到时，relaxation 会被直接跳过——这就是有 cycle 也不出错的原因（各种 case 一节详谈）。可选一个目标点，结束时高亮整条 shortest path。

**结束条件：**priority queue 空了（没有「未 settle 且可达」的 vertex）。此时每个可达 vertex 的 dist 都已 settled, prev[] 连起来就是一棵 shortest path tree——从任意 vertex 沿 prev 回溯到源，就是它的 shortest path。仍是 ∞ 的 vertex 表示从源不可达。

3 · 各种 case：有 cycle 仍正确，negative weight 失效

把 Dijkstra 的适用边界讲清楚：什么会让它出错，什么不会。核心是同一句话——「取出即 settle，从此不再改」这个 greedy，在非负 weight 下是定理，遇上 negative weight 就不再成立。

3.1 · 有 cycle 图：仍然正确

很多人担心「图里有 cycle, Dijkstra 会不会沿着 cycle 绕圈圈、死循环或重复更新？」——不会。关键就在「settled vertex 不再被更新」：一个 vertex 一旦被 extract-min 并 settle，后面任何沿 cycle 回头指向它的 edge，在 relax 时都会被直接跳过。每个 vertex 只会被 settle 一次，主循环最多跑 V 次。

下面是动手跑 Dijkstra 那节那张含 cycle 图（A→B→C→D→A 形成 cycle）。点单步跑完，留意 verdict 里 D→A 这条回边在 relax 时如何被「A 已 settled，跳过」挡掉——cycle 没有造成任何麻烦。

**结论：**有 cycle（只要 weight 非负）对 Dijkstra 毫无影响。cycle 上的回边要么 relax 不动（更远），要么指向一个 settled vertex 而被跳过。正确性、复杂度都不变。

3.2 · negative-weight edge:greedy 失效的反例

现在换一张带 negative-weight edge 的小图： $S\to U=2$ 、 $S\to V=5$ 、 $V\to U=-4$ 。直接观察：到 U 有两条路——直接 $S\to U$ 花 2，或者经 $S\to V\to U$ 花 5 + (-4) = 1。绕路反而更近，可 Dijkstra 会给出 2。

点「单步」运行 Dijkstra，观察它如何在第一步之后就把 U 以 dist=2 settle；等轮到 V extract-min、想用 $V\to U=-4$ 把 U 收紧到 1 时，U 已经 settled——更新被跳过。右边是 Bellman-Ford 算出的真实 shortest path，作为对照。

失效的根因：Dijkstra extract-min U 时，它的 dist=2 是当时未 settle vertex 里最小的，于是断言「不可能更短」并 settle。这个断言依赖「后续的 edge weight 都非负、只会让路更长」。可 negative-weight edge $V\to U=-4$ 恰恰让「先到更远的 V (5)、再走一条 negative edge」总代价更小 (1)。前提被打破，断言失效，U 就被过早锁定在次优值 2。

那 negative weight 图怎么算？更换算法：Bellman-Ford（把所有 edge 反复 relax V−1 轮，不挑顺序、不「settle」，因此 negative edge 也能逐步传播开），或针对 negative weight 的 SPFA / Johnson 等。代价是更慢 (Bellman-Ford 是 O(V·E))。另外：若图里有可达的 negative cycle,shortest path 无下界（沿 cycle 绕圈无限变小），此时根本无解——Bellman-Ford 能检测到这种情况。

3.3 · Bellman-Ford 是怎么算的

上面只用了 Bellman-Ford 的结果，这里把它的运行过程也展开。它的思路比 Dijkstra 更朴素：不挑顺序、不 settle 任何 vertex，只是把每一条 edge 都 relax 一遍，如此重复 V−1 轮。为什么 V−1 轮就够？任何 shortest path 最多 V−1 条 edge；每跑一轮，至少能让最短路上「再往前一跳」正确地确定下来，所以 V−1 轮后所有 dist 必然收敛。最后再多跑一轮做检测：若还有 edge 能把某点 relax 得更小，说明存在可达 negative cycle（沿它绕圈 dist 无限变小，shortest path 无下界）。

为什么恰好是 V−1 轮？

**shortest path 最多 V−1 条 edge。**没有 negative cycle 时，任何 shortest path 一定是 simple path（不重复经过 vertex）——因为重复经过就夹了一个 cycle，而非负 cycle 删掉只会让路不变长。简单路径最多经过 V 个 vertex，所以最多 V−1 条 edge。这就是 V−1 的来源。

**每跑一轮，正确值至少沿最短路往前推进一跳。**一轮 = 把所有 edge 各 relax 一遍。可归纳证明：第 k 轮结束后，凡是「最短路 ≤ k 跳」的 vertex,dist 必已正确。归纳步：到 v 的 (k+1) 跳最短路 $s\to \dots \to u\to v$ ，其前缀 $s\to \dots \to u$ 是到 u 的 k 跳最短路（最短路的前缀也是最短路），由假设 u 在第 k 轮后已对；第 k+1 轮 relax 到 $u\to v$ 时就把 v 定对。

一轮内的 edge 顺序无所谓。上面只用到「u 在上一轮末已正确」，与本轮内谁先 relax 无关。顺序走运能一轮推进好几跳（提前收敛），最差也保证推进一跳。所以 V−1 轮是不依赖顺序的最坏情况保证。

**V−1 是「紧」的，省不掉。**把图摆成一条链 $s\to a\to b\to \dots$ （V 个点排成一线），若每轮恰好按 edge 逆序 relax，每轮只推进一跳，到链尾就得跑满 V−1 轮。

**第 V 轮只为检测 negative cycle。**V−1 轮后必收敛；再多跑一轮若还能 relax 得更小，说明存在「需 ≥V 跳才更短」的走法——≥V 跳必重复 vertex 即绕了负 cycle。**对到本节例子：**3 个 vertex → V−1 = 2；到 U 的真实最短路 $S\to V\to U$ 恰好 2 条 edge，顶满上界，所以非跑满 2 轮不可。

用的还是上面那张 negative weight 图（源 = S）。点「下一步」逐条 edge 观察 relax——重点关注 $V\to U=-4$ ：它会在某一轮把 dist[U] 从 2 收紧到 1。因为 Bellman-Ford 不 settle,U 的值之后仍可继续被改小，这正是它能处理 negative weight、而 Dijkstra 不能的根本区别。

对比： Dijkstra 靠「按 dist 从小到大 extract-min、取出即 settle」省下重复计算，代价是假设 edge weight 非负;Bellman-Ford 放弃这个假设，改用「把每条 edge 反复 relax V−1 轮」换取对 negative weight 的正确性，代价是 O(V·E) 更慢。

4 · 给 Dijkstra 装上「方向感」：A* 搜索

Dijkstra 没有「目标」概念——它从源点向四周均匀扩展，把每个点都按 dist 逐一 settle，哪怕目标就在正右方，它也会先把左边、上下方一大片都扩展完。A* 只改一处：extract-min 时排序的键，从 g（已走代价）换成 f = g + h——加上一个对「还差多远到目标」的乐观估计 h。于是搜索被朝目标方向牵引，扩展的格子骤减。

同一份代码，只差一个 h。

g(n) = 从源到 n 已经走的真实代价（和 Dijkstra 的 dist 一样）。
h(n) = 从 n 到目标还要走多远的估计（这里用曼哈顿距离，网格四向移动下永不高估）。
f(n) = g(n) + h(n) =「经过 n 的整条路」总代价的乐观估计——优先队列就按它排。

把 $h \equiv 0$ 代入，f = g,A* 退化成 Dijkstra。下面那个下拉就是在这两者之间切。

格子里：中间大字 = f，左上 = g，右上 = h。蓝框 = 源，红框 = 目标。点空格子可加/拆墙，实时重算。

4.1 · 为什么 A* 仍然给出最短路？（前提：`h` admissible）

A* 不是「贪心直奔目标」那种可能得到次优解的启发式搜索——它保证找到的就是最短路，只要 h 满足一个条件：

**admissible（可采纳）：h(n) 永不高估到目标的真实剩余代价。**曼哈顿距离在四向网格上恰好是「没有墙时的最短步数」，有墙只会让真实代价更大——所以它永不高估，合格。

直觉：因为 h 不高估，f = g + h 也就不会高估「经过 n 的整条路」。当目标第一次从 open 里 extract-min 出队时，它的 f（此刻 = g，因为 h(goal)=0）是队里最小的；任何还在 open 里的点，其乐观估计 f 都 ≥ 它，绕过去只会更长——所以这条就是最短的。

h 越准越省，但高估就会出错。 $h \equiv 0$ (Dijkstra)永不高估、最稳健，但没有方向感、扩展最多；h = 真实剩余代价时 A* 沿直线直达目标、不浪费扩展（但此值通常算不出）。若把 h 放大、刻意高估，搜索更快但可能得到次优路径——这就是 weighted A* 的取舍：以一定最优性换取速度。

这与「优先队列」相关联：A 和 Dijkstra 底层那个「每次取 f 最小」的容器，就是一个 binary heap。换个角度看，A 也是分支限界(best-first branch & bound)的一个特例——f = g + h 就是「经过 n 的整条路代价」的那个乐观界(bound)**。

5 · 应用实例：导航为什么会「重新规划路线」

地图导航的内核就是最短路：边权 = 路段通行时间,Dijkstra 找从起点到终点最快的那条路。真正实用的一步是动态重路由——前方一堵车（某段耗时飙升），最短路立刻换一条绕行路线。选起点 / 终点，再点任意路段切换「拥堵」（耗时 ×3），看蓝色路线和 ETA 实时改变。

每条路段标着通行分钟数;蓝色是当前最快路线，底部显示 ETA（总分钟）。点一条路段把它标红 = 拥堵（耗时 ×3）。若它在当前路线上，Dijkstra 往往会绕开它另选一条——这正是高德 / Google Maps 实时避堵的简化版。

5.1 · 同样的方法，还应用在这些场景

「在带权图上求代价最低的一条路」这件事，远不止地图导航：

游戏 / 机器人寻路 →

NPC、AGV、扫地机的路径几乎都是 A*（网格 + 启发式）——Dijkstra 装上「朝目标的方向感」，少扩展大量格子。

网络路由协议

OSPF / IS-IS 这类链路状态协议在每台路由器上跑 Dijkstra，按链路开销算最短转发路径；RIP 用 Bellman-Ford。

负权环 = 套利机会

把汇率取对数当边权，Bellman-Ford 找到的负权环就是一圈换下来「钱变多」的外汇套利路径。

依赖与关系链

社交「最短认识链」(BFS / Dijkstra)、构建系统的最短编译顺序、技能树 / 任务图的最低成本通关路线。

重路由的原理很直接：每次路况改变，就重跑一遍 Dijkstra。可回到动手跑 Dijkstra 看它如何 extract-min / settle / relax，或去 A* 看如何加速。

**底层关联：A / Dijkstra 每次「取 f 最小」依赖 binary heap；而把 f = g + h 看成「整条路代价的乐观界」，A 即是分支限界(branch & bound)的一个特例。

6 · 🔗 相关链接

**它真实跑在哪里。*地图导航：高德 / Google Maps 的路径规划，地基是 Dijkstra（工程上叠加 Contraction Hierarchies / A 把全国路网查询压到毫秒级）。

网络路由协议:OSPF、IS-IS 这类链路状态协议在每台路由器上跑 Dijkstra 算最短转发路径；RIP 用 Bellman-Ford。

游戏与机器人:NPC 寻路、机械臂 / AGV 路径几乎都是 A*（网格 + 启发式）。

其他：社交网络的最短关系链、构建系统的依赖 / 编译顺序、外汇套利检测（Bellman-Ford 找负权环）。