最短路径：修订间差异

2026年9月20日 (日) 07:18的最新版本

最短路径（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：图的定义。
相关条目：图论、优化、线性规划、矩阵。

@@ 第1行： / 第1行： @@
-最短路径问题在带权图中寻找从起点到终点总边权最小的路线。权重可以表示距离、时间或费用，不必等于图上画出的线段长度。算法能否正确求解，取决于图是否有方向、边权能否为负，以及是否存在可达的负权回路。
+'''最短路径'''（shortest path）是在一张图中，寻找从起点到终点总权重最小的路线。边的权重可以表示路程、时间或费用；一条路线的权重等于所经各边权重之和。
-英文名称：Shortest paths。
+“最短”取决于比较的量。经过站数最少的路线未必耗时最少，图上画得较短的线也未必代表较短路程。先给每条边明确的权重，路线之间才有统一的比较标准。
-== English overview ==
+== 从五个地点开始 ==
-<div lang="en" class="math-english-summary">
+下图有五个地点，边可以双向通行，旁边数字表示通行费用。要求从 A 到 E 花费最少。
-A shortest-path problem asks for a route with minimum total edge weight. The graph specifies allowed transitions, while weights specify their costs. The distinction between a simple path and a walk matters when negative cycles are possible. A target is unreachable if no route exists; a reachable target may have no finite minimum walk cost if a reachable negative cycle can also reach it.
-This article works through a small network using distance labels and predecessor pointers. Breadth-first search handles equal-cost edges, Dijkstra's algorithm settles vertices safely when all relevant edge weights are nonnegative, and Bellman–Ford uses repeated relaxation to accommodate negative edges. We prove the key invariant behind Dijkstra's greedy choice and construct a counterexample showing why a negative edge breaks it. A second example traces Bellman–Ford updates and explains why a negative-cycle warning is relevant only to targets reachable from that cycle. Distance labels can be checked independently through edge inequalities and an actual route attaining the bound. Historical notes refer to Dijkstra's 1959 publication and the development of algorithmic routing. Real networks may require richer models for turn penalties, time-dependent travel, capacities, or competing users; these features cannot be added merely by renaming an edge weight.
+[[File:Gezhi-graph-path-theme.svg|frame|center|alt=从A到E的加权图，AB、AC、BD、CD、DE的费用分别是二五二一三，金色显示ABDE|金色路线 A—B—D—E 的总费用为 7。]]
-</div>
+沿图中上方的金色边走，得到 <math>A-B-D-E</math>，费用为 <math>2+2+3=7</math>；沿下方走 <math>A-C-D-E</math>，费用为 <math>5+1+3=9</math>。E 只有一个邻点 D，因此无论怎样走，最后都要经过 DE。问题可以先归为：怎样以最低费用到达 D？
-== 问题的对象与符号 ==
+本图很小，逐条查看即可。图变大后，所有路线可能非常多，还可能绕圈；算法需要保存已经知道的信息，逐步排除不可能更好的选择。
-设有限图 <math>G=(V,E)</math> 的每条边 e 带权 w(e)。一条路线的权重定义为所经边权之和。在本条算法讨论中，游走允许重复顶点和边，简单路径不重复顶点。若所有边权非负，从游走中删除一个圈不会增加成本，因此只要目标可达，总可以选到一条不更差的简单路径；零权圈可能造成多条同值游走，但不妨碍简单最优路径的存在。
-有负权时，两种问题必须分开。若某负权圈从起点可达并且还能通向目标，可以绕圈任意多次，使到目标的游走成本任意低，所以没有有限最短游走。若强行禁止重复顶点，简单路径集合有限，问题变成另一个组合优化任务，不能再把通常最短路算法的结论原封不动套上去。
+== 距离标签与松弛 ==
+给每个顶点 v 记录一个数 <math>d(v)</math>，称为距离标签。它表示目前找到的从 A 到 v 的最低费用。开始时，A 到自己费用为 0；其他地方尚未找到路线，用 <math>\infty</math> 表示：
+<math display="block">d(A)=0,\qquad d(B)=d(C)=d(D)=d(E)=\infty.</math>
-图无方向意味着每条边可以双向使用；图有方向则只能按箭头行走。若把一条负权无向边按两个相反方向来走，来回一次已经是负成本闭合游走，因此无向负边会立即引出这一障碍。在有向图中，单独一条负边不一定形成回路，也不一定让问题无解。
+从 A 看出去，AB 费用为 2，AC 费用为 5，于是将 B、C 的标签改为 2、5。接着若已经知道到 B 的费用为 2，又看到 BD 费用为 2，就找到一条到 D 费用为 4 的路线。
-== 一个可以逐步核对的网络 ==
+一般地，沿边 <math>u\to v</math> 尝试更新：
-采用[[图论]]中的五点无向图：AB 权重二、AC 权重五、BD 权重二、CD 权重一、DE 权重三。要求从 A 到 E 的最小总成本。一条路线 A—B—D—E 的总权重为七，另一条 A—C—D—E 的总权重为九。画图时线段长短不表示权重，判断必须使用标注的数字。
+<math display="block">d(v)\leftarrow\min\{d(v),\,d(u)+w(u,v)\},</math>
+其中 <math>w(u,v)</math> 是这条边的权重。这一步叫'''松弛'''：比较当前记录与新路线，保留较小者。只有 d(u) 有限时才执行，未发现的路线不能作为出发依据。
-[[File:Gezhi-graph-path.svg|frame|center|alt=五点加权图中从A经B和D到E的三条边被突出显示，总权重七|最少边数和最小权重是两种问题；本例突出路线的权重为 2+2+3=7。]]
+每次标签严格变小时，同时记录 v 是从哪一个顶点 u 更新而来，这个 u 称为前驱。最后沿终点的前驱反向走，可以恢复所找到的路线。若费用相同，保留已有前驱即可。
-算法维护一个距离标签 d(v)，表示目前已经发现的从起点到 v 的最佳成本，并保存前驱以恢复路线。初始 d(A)=0，其他点为无穷大，表示尚未发现路线，不能把无穷大理解为一条实际路径的长度。沿边 u→v 的松弛操作是
+== Dijkstra 算法怎样选择下一步 ==
-<math display="block">d(v)\leftarrow\min\{d(v),d(u)+w(u,v)\}.</math>
+边权全为非负时，可以每次从尚未确定距离的顶点中，选标签最小的一个，正式确定它，再松弛它的邻边。这就是'''Dijkstra 算法'''。
-只有当 d(u) 有限时才尝试这次更新。标签缩小时同时把 v 的前驱设为 u；若两条路线成本相同，可以按约定保留任意一条，除非任务要求列出全部最短路线。
-== Dijkstra 算法的完整过程 ==
+本例中，处理 A 后 B 的标签 2 小于 C 的 5，因此先确定 B。经过 B 得到 D 的标签 4，又小于 C 的 5，于是下一步先确定 D。整个过程如下：
-Dijkstra 每次从尚未确定的顶点中选取标签最小者，把其距离确定下来，再松弛它发出的边。对本例，过程如下；表中“确定”指从待处理集合中取出，后续正确性依赖非负权条件。
+<div class="math-table-scroll" role="region" aria-label="五点图中Dijkstra算法的距离更新" tabindex="0">
-<div class="math-table-scroll" role="region" aria-label="最短路径迭代表格" tabindex="0">
 {| class="wikitable"
-! 本轮确定 !! d(A) !! d(B) !! d(C) !! d(D) !! d(E) !! 新发现的信息
+! 本轮确定 !! d(A) !! d(B) !! d(C) !! d(D) !! d(E) !! 发生的更新
 |-
-| A || 0 || 2 || 5 || ∞ || ∞ || B、C 的前驱为 A
+| A || 0 || 2 || 5 || ∞ || ∞ || 找到 AB 与 AC
 |-
-| B || 0 || 2 || 5 || 4 || ∞ || D 的前驱为 B
+| B || 0 || 2 || 5 || 4 || ∞ || 经 B 找到 D
 |-
-| D || 0 || 2 || 5 || 4 || 7 || E 的前驱为 D；经 D 到 C 也为 5
+| D || 0 || 2 || 5 || 4 || 7 || 经 D 找到 E；到 C 的候选值也为 5
 |-
-| C || 0 || 2 || 5 || 4 || 7 || 没有更小标签
+| C || 0 || 2 || 5 || 4 || 7 || 没有更便宜路线
 |-
 | E || 0 || 2 || 5 || 4 || 7 || 终点距离确定
 |}
 </div>
-从 E 沿前驱回溯得到 E、D、B、A，逆序即所求路线。注意 D 虽然在图的字母顺序中排在 C 后面，却先被确定，因为四小于五。只求某个终点时，可以在它被正式确定后停止，不能在第一次给它赋有限标签时就停止。
+下图截取表格的前三轮。顶点下方是距离标签，金色边框表示距离已经确定，青色表示仍待选择。中图 D 的标签从无穷降到 4，小于 C 的 5，因此右图轮到确定 D，并把 E 更新为 7。
+[[File:Gezhi-teaching-foundation-shortest-dijkstra.svg|frame|center|alt=三个并排的五点图显示确定A后B二C五，确定B后D四，确定D后E七；金色顶点已确定，青色仍待处理|三轮距离更新：先 A，再 B，再 D；选择依据是当前最小标签。]]
+这里 D 在 C 之前处理，依据是当前费用，而不是字母顺序或图中的位置。前驱记录为 E 来自 D、D 来自 B、B 来自 A。逆向读出 <math>E-D-B-A</math>，再反向得到最短路线，费用为 7。
+若只求一个终点，在它被正式确定时就可以停止。第一次给它有限标签只是发现一条路线，后面仍可能发现更便宜的路线；确定步骤才给出最优性保证。
+=== 最小标签为什么可以确定 ===
+每个有限标签都来自某条实际路线，因此不可能低于真实最短费用。已经确定的顶点，则希望保证标签恰好等于最短费用。起点 A 的标签为 0，在非负权下绕行不会更便宜，首先满足这个条件。
+现在选出标签最小的未确定顶点 u。假设有一条到 u 的路线，比 d(u) 还便宜。沿这条路线，从起点走到第一次离开已确定顶点集合的位置，设跨越的边为 <math>x\to y</math>。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 的费用是
+<math display="block">5-4=1,</math>
+比 2 更小。这里后半段能把总费用降低，所以前面的确定步骤不再可靠。
-实现中常用优先队列保存候选标签。若采用重复插入新标签的简便方式，弹出旧条目时需检查它是否已过期，否则可能反复处理无效记录。用支持减小键值的二叉堆和邻接表，标准时间界为 <math>O((|V|+|E|)\log|V|)</math>。采用重复入堆、跳过过期项的实现时，更直接的界为 <math>O(|V|+|E|\log(|E|+1))</math>；在简单图中可化到常用的顶点数对数形式。多重图可能有大量平行边，应保留与实际边数相配的界。小规模稠密图直接线性扫描候选点也可能更简洁。
+这个图没有负权回路，最短路线完全存在。若边权可能为负，需要换一种算法，而不是把“存在负边”直接等同于“问题无解”。
-== 为什么最小标签可以安全确定 ==
+也不能给每条边都加一个固定数就沿用原答案。假设一条单边路线费用为 3，另一条两边路线总费用为 2，原来后者更便宜。每边加 2 后，两者分别变成 5 和 6，顺序反转，因为它们经过的边数不同。
-证明抓住一个不变量：已经确定的顶点标签等于真实最短距离，而未确定顶点的有限标签总来自某条实际路线，所以不会低于真实最短距离。初始起点距离为零，在非负权下不会被任何绕行降低。
-现在取标签最小的未确定顶点 u，假设存在比 d(u) 更短的起点到 u 路线。在这条路线从已确定集合首次走向未确定集合的边上，设前一点为 x、后一点为 y。x 已经有正确距离，处理 x 时已松弛到 y，所以 y 的标签不超过该路线到 y 的前段成本。由于剩下从 y 到 u 的边权都非负，前段成本不超过整条路线成本，因而 d(y)<d(u)，与 u 是最小候选标签矛盾。
+== Bellman–Ford：允许的步数逐轮增加 ==
+另一种方法是先只看一步能到哪，再看两步、三步……。设 <math>d_k(v)</math> 表示从 S 到 v、最多使用 k 条边的最低费用。零步时只有 S 可达。对于 <math>k\ge1</math>，一条最多 k 步的路线，要么已经不超过 k−1 步，要么最后沿某条 <math>u\to v</math> 到达。因此
+<math display="block">d_k(v)=\min\left\{d_{k-1}(v),
+\min_{(u,v)\in E}\bigl(d_{k-1}(u)+w(u,v)\bigr)\right\}.</math>
+右侧统一使用上一轮的标签，这叫同步更新。公式中的两类选择恰好覆盖所有至多 k 步的路线。
-这个证明显示非负性究竟用在哪里：保证后半段不能通过负成本把路线总值降低。并不要求每条边严格为正，零权边也允许；距离并列时任选一个最小标签点同样正确。证明的是成本正确，若有多条最短路，算法输出的具体路线则取决于并列处理规则。
+在负边的三点例子中，第一轮只找到 S→A 与 S→B，所以 <math>d_1(A)=2</math>、<math>d_1(B)=5</math>；第二轮允许经 B 到 A，得到 <math>d_2(A)=1</math>。这次 A 没有被过早锁定。
-== 一个负边反例 ==
+如果从 S 可达的区域没有负权回路，路线中的回路都可以删除而不增加费用，因此总能选到一条不重复顶点的最短路径。若有 n 个顶点，这种路径最多含 n−1 条边，所以 n−1 轮已经足够。
-有向图只有三条边：S→A 权重二、S→B 权重五、B→A 权重负四。从 S 出发先得到 A 标签二、B 标签五，按 Dijkstra 会先确定 A；但真实最短路线 S→B→A 的成本是一。这里没有负权回路，最短路完全存在，只是贪心确定步骤失去正确性。
-不能因为某个带负边例子恰好算对，就认为算法仍有一般保证。也不能随意给每条边都加同一常数来消除负数：不同路线经过的边数可能不同，加常数会改变路线之间的成本排序。例如一条单边成本三与一条两边总成本二，原来后者更短；每边加二后，前者成本五，后者成本六，排序反转。
+'''Bellman–Ford 算法'''逐轮扫描全部边并松弛。实际实现也常原地更新，一轮内可能传播超过一步；但每轮至少能保证最短路径上的下一个顶点得到正确距离，所以没有可达负圈时，n−1 轮仍足够。若一整轮没有任何更新，所有边的松弛都已稳定，可以提前结束。
-== Bellman–Ford：逐轮扩大允许的边数 ==
+再多检查一轮，若某条从可达顶点出发的边仍能改善标签，就说明存在从起点可达的负权回路。最短路径边数已用尽后还能不断改善，正是负圈导致的现象。完整证明与伪代码可见 [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-17-bellman-ford/ MIT 6.006 第 17 讲]。
-若允许负边，可从另一种思路出发。令 <math>d_k(v)</math> 表示从 S 到 v、最多使用 k 条边的最小游走成本；初始 d₀(S)=0，其他无穷大。同步更新公式是
-<math display="block">d_k(v)=\min\left\{d_{k-1}(v),\ \min_{(u,v)\in E}\bigl(d_{k-1}(u)+w(u,v)\bigr)\right\}.</math>
-它按最后一条边分类：要么最优路线已经不超过 k−1 条边，要么末边为 u→v，之前最多 k−1 条。公式中的右侧都使用上一轮值，便于严格说明每一轮的含义；实际原地松弛实现可以在一轮中传播更远，但正确性与停止条件仍需按对应实现分析。
-在上面的三点负边例子中，第一轮 A=2、B=5，第二轮经 B 更新 A=1。若从起点可达的区域没有负权回路，可以删去非负圈而不增加成本，最短简单路径至多含 |V|−1 条边，所以这么多轮足够。额外再检查一轮仍能改善某个可达标签，便说明有起点可达的负权回路影响相关区域。
+== 负权回路影响哪些终点 ==
+在最短路算法中，允许重复顶点和边的路线称为'''游走'''，不重复顶点的称为简单路径。若所有边权非负，删除游走中的圈不会使费用增加，所以总能选简单路径作为最优解。负权回路会改变这一点。
-若只关心特定终点，还要从受影响顶点检查能否到达目标。图中某个遥远、与起点不连通的负权圈，不影响当前起点问题；起点可达却无法通向目标的负权圈，也不意味着这个目标的最短成本不存在。这些可达性限定使“检测到负环”与“所有终点都无答案”明显不同。
+例如有向图有 S→A 权 1、A→B 权 1、B→A 权 −3、S→T 权 5，另有孤立点 U。沿 A→B→A 每绕一圈，费用减少 2。可以绕任意多次，所以到 A、B 的游走费用没有有限最小值，距离下确界记为 <math>-\infty</math>。
-== 负权回路只影响能从它继续到达的目标 ==
+但是负圈无法通向 T，故 S 到 T 的最短费用仍为 5；U 从 S 不可达，记为 <math>+\infty</math>。若再加边 B→T 权 1，就能绕负圈后再去 T，此时 T 也受影响，最低费用不再是一个有限数。
-一个具体例子能区分三种距离状态。设有向边 S→A 权一、A→B 权一、B→A 权负三、S→T 权五，并令 U 与其余顶点不连通。A—B—A 每绕一圈成本减少二，因此 A、B 的距离下确界为负无穷；T 的最短距离仍是五，因为从负圈没有边通向 T；U 则不可达，距离记为正无穷。三个状态不能只用一个“失败”标记代替。
-若再添加 B→T 权一，就可以先在负圈绕任意多次再去 T，此时 T 也没有有限最短游走。程序在检测到可达负圈以后，应从受到进一步松弛影响的顶点向前搜索，把能够继续到达的顶点标为负无穷；没有受到影响且可达的点仍有有限答案。只对一个目标查询时，也可先反向搜索出能通向该目标的顶点，再与起点可达集合取交。
+因此目标没有有限最短游走的条件是：负圈从起点可达，并且还能继续到达目标。检测负圈后，从受进一步松弛影响的顶点向前搜索，就能标出所有受影响的目标。无关区域的负圈不改变当前目标的答案。
-这一区分也影响最短路证书。若起点可达的某处有负圈，但它无法通向目标，那么在整个起点可达区域上未必存在一组有限势函数标签满足全部边不等式；这并不妨碍目标有有限最短路。将证书限制在“起点可达且可以到达目标”的相关区域，才准确匹配这次查询。任何起点到目标的路线都完全位于这个区域，所以不会漏掉候选路线。
+若强行要求路线不能重复顶点，有限图仍只有有限条简单路径，有负圈时也可能选出其中最小者；这是另一个问题，不能直接沿用允许绕圈的最短游走算法。无向图中的一条负边若可以来回使用，来回一次就形成负费用闭合游走，相关可达性条件同样适用。
-== 复杂度与实现中会破坏证明的细节 ==
+== 不重跑算法，怎样检查答案 ==
-Bellman–Ford 的标准实现至多进行顶点数减一轮松弛，每轮扫描全部边，再进行一次负圈检查，时间为 <math>O(|V||E|)</math>，距离与前驱数组使用线性于顶点数的额外空间。同步版本需要保留上一轮数组，仍是同一空间量级；若一整轮没有任何更新，可以提前停止，因为全部边不等式已经稳定。
+对于从 S 到 T 的有限最短路，可以给出两部分证据：一条实际路线，以及任何路线都不可能低于的费用下界。
-这些界通常把一次加法和比较视为常数时间。如果权重是任意精度整数，还须计入位数造成的算术成本；若使用有限范围整数，距离相加前需要避免溢出，否则一个巨大正数可能变成负数，直接破坏松弛不变量。无穷大应当作为未到达状态处理，不能拿最大的机器整数随意参与加法。
+先考虑相关区域 R，即从 S 可达、并且能继续到 T 的顶点。假定 T 可达，任何 S 到 T 的路线都完全处在 R 中。给 R 中每个顶点标一个有限数 <math>\pi(v)</math>，满足 <math>\pi(S)=0</math>，并且每条区域内的边都满足
+<math display="block">\pi(v)\le\pi(u)+w(u,v).</math>
+这等价于 <math>w(u,v)\ge\pi(v)-\pi(u)</math>。沿任意一条 S 到 T 的路线把这些不等式相加，中间顶点的标签正负抵消，得到
+<math display="block">\text{路线总费用}\ge\pi(T)-\pi(S)=\pi(T).</math>
+所以 <math>\pi(T)</math> 是全部候选路线的下界。如果再找出一条费用恰为这个数的路线，它就必然最短。
-前驱恢复同样需要检查。每次严格改善标签时记录产生该标签的实际边；等长候选不必反复改前驱，否则零权圈可能使一组“成本相等”的前驱指针形成循环。输出有限最短路线时，应从终点沿前驱在有限步内回到起点，并核对每条边与总成本。若算法已判断该目标受负圈影响，就不能把当前有限前驱链当成最终最短路线交付。
+在五点图中，取 <math>(\pi(A),\pi(B),\pi(C),\pi(D),\pi(E))=(0,2,5,4,7)</math>。无向边需要检查两个方向，等价于两端标签之差的绝对值不超过边权。AB、AC、BD、CD、DE 的标签差分别为 2、5、2、1、3，全部符合。金色路线又恰好花费 7，因而达到下界，最优性得证。
-== 如何独立检查输出距离 ==
+把标签限制在 R 是有原因的：前面的负圈例子里，T 的答案为 5，但整个起点可达区域含有负圈，不可能用有限标签满足所有边不等式。去掉不能通向 T 的部分后，仍保留所有候选路线，才得到适合该目标的证书。若 T 不可达，可以改为列出从 S 可达的顶点，并核验没有边从这个集合走向外部，以证明 T 确实被隔开。
-先取起点可达且能够通向目标的相关区域，并假定目标可达。设这个区域上的有限候选标签函数 π 满足 π(S)=0，且对区域内每条边 u→v 有 <math>\pi(v)\le\pi(u)+w(u,v)</math>。沿任意 S 到 T 的路线逐项相加，中间标签抵消，得到 <math>\pi(T)\le\text{路线总权重}</math>。若另外找到一条实际路线恰好达到 π(T)，便证明它最短。这是下界加可行路线构成的证书，与[[线性规划]]中的对偶思想相通。
-在五点图中取 π=(0,2,5,4,7)，可逐边验证双向不等式：例如 C、D 的差为一，恰好等于边权一；D、E 的差为三，等于边权三。路线 A—B—D—E 的总成本等于 π(E)=7，因此无需重新运行算法也能核验结果。若目标不可达，应另外给出可达集合及其没有向外出边的证明，而不对无穷大做普通实数相减。无关区域的负圈不应混入这个目标的有限证书。
+== 算法成本与实现细节 ==
+Bellman–Ford 最多进行 n−1 轮全边扫描，再加一轮负圈检查。记顶点数为 <math>|V|</math>、边数为 <math>|E|</math>，时间量级为 <math>O(|V||E|)</math>，距离及前驱数组占 <math>O(|V|)</math> 的额外空间。同步更新保存两轮数组，仍是同一空间量级。
-无权图也可把每条边权统一看作一，广度优先搜索按距离层展开。它使用队列而不需要一般优先队列，时间为 <math>O(|V|+|E|)</math>。有向无环图则可以按拓扑顺序松弛，即使存在负边也能求解，因为不存在有向回路。选择算法应先看结构条件，而不是只看算法名称的知名度。
+Dijkstra 用优先队列快速找最小标签。若用支持减小键值的二叉堆及邻接表，时间界为 <math>O((|V|+|E|)\log|V|)</math>。另一种实现是每次改善就把新标签重复入堆，取出时跳过过期条目，其直接界为 <math>O(|V|+|E|\log(|E|+1))</math>；简单图中可化为常见的顶点数对数形式，多重图则应保留实际边数。
-== 历史、应用与模型边界 ==
+若每条边费用相同且非负，可直接使用[[图论|广度优先搜索]]，时间为 <math>O(|V|+|E|)</math>。有向图若没有任何有向圈，则可以按照使每条边都从前指向后的顶点次序松弛；即使有负边，也不会出现回路反复改善的问题。
-Dijkstra 的最短路论文《A Note on Two Problems in Connexion with Graphs》发表于 1959 年；[https://www.cs.utexas.edu/~EWD/ewd08xx/EWD841a.PDF 得克萨斯大学保存的作者回顾]讨论了这篇短文及其背景。作者回忆，他在 1956 年为 ARMAC 计算机准备面对普通观众的演示，以简化的荷兰铁路网络回答两地之间的最短路线；这种可以清楚提问、可以直接显示结果的具体任务，推动了算法的形成。后来发表的论文还讨论了最小生成树，它要求连接全部顶点、使树的总长度最小，与指定起终点的最短路径是另一种目标。最短路思想还与其他研究者提出的动态规划和网络算法并行发展，不能把所有路由方法都称为 Dijkstra 算法。
-交通导航若存在转弯惩罚，状态可能需要记录“从哪条路进入当前路口”，仅以路口作顶点、静态路段作边权就会丢失信息。时间依赖交通、充电续航与容量限制也可能需要扩充状态或改变算法。单车最短路线与全体车辆的最优分配是不同目标；后者还要考虑彼此影响与拥堵。
+实现还需保证数值遵守证明中的运算规则。未到达状态不参与普通加法，有限整数相加应避免溢出；任意精度整数的加法、比较成本也会随位数增长。等长候选不必反复更改前驱，否则零权圈可能造成前驱循环。输出有限路线时，应核验每条边存在、前驱链能回到起点，以及总费用与最终标签相符。
-== 修改边权后的核验 ==
+== 历史与路由模型 ==
-在五点图中，若 DE 权重从三改为十，可以直接核验新答案。E 只有邻点 D，任何路线都必须经过最后这条边；到 D 的最小成本仍为四，所以答案十四。这个分解既利用图结构，也避免重新枚举所有游走。
+Dijkstra 的论文《A Note on Two Problems in Connexion with Graphs》发表于 1959 年。[https://www.cs.utexas.edu/~EWD/ewd08xx/EWD841a.PDF 作者回顾]记述，他在 1956 年为 ARMAC 计算机准备演示，用简化的荷兰铁路网络回答两地之间的最短路线。论文还讨论最小生成树，即连接所有顶点并使总树长最小的另一类问题。
-== 编者评注（AI 辅助） ==
+实际导航中，边权是否真能独立相加取决于模型。若转弯需要额外时间，仅记录“当前路口”可能不够，还要记录从哪条道路进入；若拥堵随时间变化，就可能需要把到达时刻纳入计算。图中的权重和状态一旦确定，算法回答的便是这个具体模型的最短路问题。
-<div class="math-editorial-note"> 最短路很适合练习“算法为什么能停下来相信一个数”。建议手工记录标签、前驱和已确定集合，并在每次更新旁写出对应实际路线。掌握非负权证明后，再看负边反例与逐轮动态规划，能理解算法条件从何而来。现实路由则应先明确成本是否真能逐边相加；状态设计错误时，再快的算法也只能精确回答错误的问题。</div>
-== 参考来源与延伸阅读 ==
+== 参考资料 ==
-* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-17-bellman-ford/ MIT 6.006，Lecture 17: Bellman–Ford]：负权、松弛与算法正确性，授课教师 Srini Devadas。
+* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/resources/lecture-17-bellman-ford/ MIT 6.006，Lecture 17: Bellman–Ford]：负权、松弛与正确性。
-* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/pages/lecture-notes/ MIT 6.006，2011 年秋季课程讲义第 15–18 讲]：单源最短路、Dijkstra 与 Bellman–Ford 的假设及复杂度。
+* [https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-fall-2011/pages/lecture-notes/ MIT 6.006 第 15–18 讲讲义]：单源最短路、Dijkstra 与 Bellman–Ford。
-* [https://www.cs.utexas.edu/~EWD/ewd08xx/EWD841a.PDF E. W. Dijkstra：关于 1959 年图算法论文的作者回顾]，UT Austin 档案。
+* [https://www.cs.utexas.edu/~EWD/ewd08xx/EWD841a.PDF E. W. Dijkstra：关于图算法论文的作者回顾]，UT Austin 档案。
-* [https://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html Oscar Levin：图的定义]，先修图结构。
+* [https://discrete.openmathbooks.org/dmoi3/sec_gt-intro.html Oscar Levin：图的定义]。
-* [[图论]] · [[优化]] · [[线性规划]] · [[矩阵]]。
+* 相关条目：[[图论]]、[[优化]]、[[线性规划]]、[[矩阵]]。
 [[分类:优化与运筹]]
 [[分类:离散数学]]