最短路径

最短路径（shortest path）是在一张图中，寻找从起点到终点总权重最小的路线。边的权重可以表示路程、时间或费用；一条路线的权重等于所经各边权重之和。

“最短”取决于比较的量。经过站数最少的路线未必耗时最少，图上画得较短的线也未必代表较短路程。先给每条边明确的权重，路线之间才有统一的比较标准。

从五个地点开始

下图有五个地点，边可以双向通行，旁边数字表示通行费用。要求从 A 到 E 花费最少。

从A到E的加权图，AB、AC、BD、CD、DE的费用分别是二五二一三，金色显示ABDE — 金色路线 A—B—D—E 的总费用为 7。

沿图中上方的金色边走，得到 $A - B - D - E$ ，费用为 $2 + 2 + 3 = 7$ ；沿下方走 $A - C - D - E$ ，费用为 $5 + 1 + 3 = 9$ 。E 只有一个邻点 D，因此无论怎样走，最后都要经过 DE。问题可以先归为：怎样以最低费用到达 D？

本图很小，逐条查看即可。图变大后，所有路线可能非常多，还可能绕圈；算法需要保存已经知道的信息，逐步排除不可能更好的选择。

距离标签与松弛

给每个顶点 v 记录一个数 $d (v)$ ，称为距离标签。它表示目前找到的从 A 到 v 的最低费用。开始时，A 到自己费用为 0；其他地方尚未找到路线，用 $\infty$ 表示： $d (A) = 0, d (B) = d (C) = d (D) = d (E) = \infty .$

从 A 看出去，AB 费用为 2，AC 费用为 5，于是将 B、C 的标签改为 2、5。接着若已经知道到 B 的费用为 2，又看到 BD 费用为 2，就找到一条到 D 费用为 4 的路线。

一般地，沿边 $u \to v$ 尝试更新： $d (v) \leftarrow min {d (v), d (u) + w (u, v)},$ 其中 $w (u, v)$ 是这条边的权重。这一步叫松弛：比较当前记录与新路线，保留较小者。只有 d(u) 有限时才执行，未发现的路线不能作为出发依据。

每次标签严格变小时，同时记录 v 是从哪一个顶点 u 更新而来，这个 u 称为前驱。最后沿终点的前驱反向走，可以恢复所找到的路线。若费用相同，保留已有前驱即可。

Dijkstra 算法怎样选择下一步

边权全为非负时，可以每次从尚未确定距离的顶点中，选标签最小的一个，正式确定它，再松弛它的邻边。这就是Dijkstra 算法。

本例中，处理 A 后 B 的标签 2 小于 C 的 5，因此先确定 B。经过 B 得到 D 的标签 4，又小于 C 的 5，于是下一步先确定 D。整个过程如下：

本轮确定	d(B)	d(C)	d(D)	d(E)	发生的更新
A	2	5	∞	∞	找到 AB 与 AC
B	2	5	4	∞	经 B 找到 D
D	2	5	4	7	经 D 找到 E；到 C 的候选值也为 5
C	2	5	4	7	没有更便宜路线
E	2	5	4	7	终点距离确定

下图截取表格的前三轮。顶点下方是距离标签，金色边框表示距离已经确定，青色表示仍待选择。中图 D 的标签从无穷降到 4，小于 C 的 5，因此右图轮到确定 D，并把 E 更新为 7。

三个并排的五点图显示确定A后B二C五，确定B后D四，确定D后E七；金色顶点已确定，青色仍待处理 — 三轮距离更新：先 A，再 B，再 D；选择依据是当前最小标签。

这里 D 在 C 之前处理，依据是当前费用，而不是字母顺序或图中的位置。前驱记录为 E 来自 D、D 来自 B、B 来自 A。逆向读出 $E - D - B - A$ ，再反向得到最短路线，费用为 7。

若只求一个终点，在它被正式确定时就可以停止。第一次给它有限标签只是发现一条路线，后面仍可能发现更便宜的路线；确定步骤才给出最优性保证。

最小标签为什么可以确定

每个有限标签都来自某条实际路线，因此不可能低于真实最短费用。已经确定的顶点，则希望保证标签恰好等于最短费用。起点 A 的标签为 0，在非负权下绕行不会更便宜，首先满足这个条件。

现在选出标签最小的未确定顶点 u。假设有一条到 u 的路线，比 d(u) 还便宜。沿这条路线，从起点走到第一次离开已确定顶点集合的位置，设跨越的边为 $x \to y$ 。x 已确定，所以它的标签不超过这条路线到 x 的前段费用；处理 x 时，边 xy 已经被松弛，故 d(y) 不超过到 y 的前段费用。

从 y 到 u 的后半段权重非负，因此到 y 的前段费用不会超过整条路线费用。于是 d(y) 比 d(u) 更小。但 y 也是未确定顶点，这与“u 的标签最小”矛盾。因此不存在更便宜的路线，u 可以安全确定。

证明允许零权边和标签并列，因为后半段只需要非负，不需要严格为正。并列时可以任选一个最小标签顶点。

一条负边怎样破坏这个理由

考虑三条有向边：S→A 费用 2，S→B 费用 5，B→A 费用 −4。从 S 出发先得到 A 的标签 2、B 的标签 5，Dijkstra 会先确定 A。但经 B 再去 A 的费用是 $5 - 4 = 1,$ 比 2 更小。这里后半段能把总费用降低，所以前面的确定步骤不再可靠。

这个图没有负权回路，最短路线完全存在。若边权可能为负，需要换一种算法，而不是把“存在负边”直接等同于“问题无解”。

也不能给每条边都加一个固定数就沿用原答案。假设一条单边路线费用为 3，另一条两边路线总费用为 2，原来后者更便宜。每边加 2 后，两者分别变成 5 和 6，顺序反转，因为它们经过的边数不同。

Bellman–Ford：允许的步数逐轮增加

另一种方法是先只看一步能到哪，再看两步、三步……。设 $d_{k} (v)$ 表示从 S 到 v、最多使用 k 条边的最低费用。零步时只有 S 可达。对于 $k \geq 1$ ，一条最多 k 步的路线，要么已经不超过 k−1 步，要么最后沿某条 $u \to v$ 到达。因此 $d_{k} (v) = min {d_{k - 1} (v), min_{(u, v) \in E} (d_{k - 1} (u) + w (u, v))} .$ 右侧统一使用上一轮的标签，这叫同步更新。公式中的两类选择恰好覆盖所有至多 k 步的路线。

在负边的三点例子中，第一轮只找到 S→A 与 S→B，所以 $d_{1} (A) = 2$ 、 $d_{1} (B) = 5$ ；第二轮允许经 B 到 A，得到 $d_{2} (A) = 1$ 。这次 A 没有被过早锁定。

如果从 S 可达的区域没有负权回路，路线中的回路都可以删除而不增加费用，因此总能选到一条不重复顶点的最短路径。若有 n 个顶点，这种路径最多含 n−1 条边，所以 n−1 轮已经足够。

Bellman–Ford 算法逐轮扫描全部边并松弛。实际实现也常原地更新，一轮内可能传播超过一步；但每轮至少能保证最短路径上的下一个顶点得到正确距离，所以没有可达负圈时，n−1 轮仍足够。若一整轮没有任何更新，所有边的松弛都已稳定，可以提前结束。

再多检查一轮，若某条从可达顶点出发的边仍能改善标签，就说明存在从起点可达的负权回路。最短路径边数已用尽后还能不断改善，正是负圈导致的现象。完整证明与伪代码可见 MIT 6.006 第 17 讲。

负权回路影响哪些终点

在最短路算法中，允许重复顶点和边的路线称为游走，不重复顶点的称为简单路径。若所有边权非负，删除游走中的圈不会使费用增加，所以总能选简单路径作为最优解。负权回路会改变这一点。

例如有向图有 S→A 权 1、A→B 权 1、B→A 权 −3、S→T 权 5，另有孤立点 U。沿 A→B→A 每绕一圈，费用减少 2。可以绕任意多次，所以到 A、B 的游走费用没有有限最小值，距离下确界记为 $- \infty$ 。

但是负圈无法通向 T，故 S 到 T 的最短费用仍为 5；U 从 S 不可达，记为 $+ \infty$ 。若再加边 B→T 权 1，就能绕负圈后再去 T，此时 T 也受影响，最低费用不再是一个有限数。

因此目标没有有限最短游走的条件是：负圈从起点可达，并且还能继续到达目标。检测负圈后，从受进一步松弛影响的顶点向前搜索，就能标出所有受影响的目标。无关区域的负圈不改变当前目标的答案。

若强行要求路线不能重复顶点，有限图仍只有有限条简单路径，有负圈时也可能选出其中最小者；这是另一个问题，不能直接沿用允许绕圈的最短游走算法。无向图中的一条负边若可以来回使用，来回一次就形成负费用闭合游走，相关可达性条件同样适用。

不重跑算法，怎样检查答案

对于从 S 到 T 的有限最短路，可以给出两部分证据：一条实际路线，以及任何路线都不可能低于的费用下界。

先考虑相关区域 R，即从 S 可达、并且能继续到 T 的顶点。假定 T 可达，任何 S 到 T 的路线都完全处在 R 中。给 R 中每个顶点标一个有限数 $π (v)$ ，满足 $π (S) = 0$ ，并且每条区域内的边都满足 $π (v) \leq π (u) + w (u, v) .$ 这等价于 $w (u, v) \geq π (v) - π (u)$ 。沿任意一条 S 到 T 的路线把这些不等式相加，中间顶点的标签正负抵消，得到 $路线总费用 \geq π (T) - π (S) = π (T) .$ 所以 $π (T)$ 是全部候选路线的下界。如果再找出一条费用恰为这个数的路线，它就必然最短。

在五点图中，取 $(π (A), π (B), π (C), π (D), π (E)) = (0, 2, 5, 4, 7)$ 。无向边需要检查两个方向，等价于两端标签之差的绝对值不超过边权。AB、AC、BD、CD、DE 的标签差分别为 2、5、2、1、3，全部符合。金色路线又恰好花费 7，因而达到下界，最优性得证。

把标签限制在 R 是有原因的：前面的负圈例子里，T 的答案为 5，但整个起点可达区域含有负圈，不可能用有限标签满足所有边不等式。去掉不能通向 T 的部分后，仍保留所有候选路线，才得到适合该目标的证书。若 T 不可达，可以改为列出从 S 可达的顶点，并核验没有边从这个集合走向外部，以证明 T 确实被隔开。

算法成本与实现细节

Bellman–Ford 最多进行 n−1 轮全边扫描，再加一轮负圈检查。记顶点数为 $| V |$ 、边数为 $| E |$ ，时间量级为 $O (| V | | E |)$ ，距离及前驱数组占 $O (| V |)$ 的额外空间。同步更新保存两轮数组，仍是同一空间量级。

Dijkstra 用优先队列快速找最小标签。若用支持减小键值的二叉堆及邻接表，时间界为 $O ((| V | + | E |) \log | V |)$ 。另一种实现是每次改善就把新标签重复入堆，取出时跳过过期条目，其直接界为 $O (| V | + | E | \log (| E | + 1))$ ；简单图中可化为常见的顶点数对数形式，多重图则应保留实际边数。

若每条边费用相同且非负，可直接使用广度优先搜索，时间为 $O (| V | + | E |)$ 。有向图若没有任何有向圈，则可以按照使每条边都从前指向后的顶点次序松弛；即使有负边，也不会出现回路反复改善的问题。

实现还需保证数值遵守证明中的运算规则。未到达状态不参与普通加法，有限整数相加应避免溢出；任意精度整数的加法、比较成本也会随位数增长。等长候选不必反复更改前驱，否则零权圈可能造成前驱循环。输出有限路线时，应核验每条边存在、前驱链能回到起点，以及总费用与最终标签相符。

历史与路由模型

Dijkstra 的论文《A Note on Two Problems in Connexion with Graphs》发表于 1959 年。作者回顾记述，他在 1956 年为 ARMAC 计算机准备演示，用简化的荷兰铁路网络回答两地之间的最短路线。论文还讨论最小生成树，即连接所有顶点并使总树长最小的另一类问题。

实际导航中，边权是否真能独立相加取决于模型。若转弯需要额外时间，仅记录“当前路口”可能不够，还要记录从哪条道路进入；若拥堵随时间变化，就可能需要把到达时刻纳入计算。图中的权重和状态一旦确定，算法回答的便是这个具体模型的最短路问题。

参考资料

MIT 6.006，Lecture 17: Bellman–Ford：负权、松弛与正确性。
MIT 6.006 第 15–18 讲讲义：单源最短路、Dijkstra 与 Bellman–Ford。
E. W. Dijkstra：关于图算法论文的作者回顾，UT Austin 档案。
Oscar Levin：图的定义。
相关条目：图论、优化、线性规划、矩阵。