最短路径

最短路径问题在带权图中寻找从起点到终点总边权最小的路线。权重可以表示距离、时间或费用，不必等于图上画出的线段长度。算法能否正确求解，取决于图是否有方向、边权能否为负，以及是否存在可达的负权回路。

英文名称：Shortest paths。

English overview

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.

问题的对象与符号

设有限图 $G = (V, E)$ 的每条边 e 带权 w(e)。一条路线的权重定义为所经边权之和。在本条算法讨论中，游走允许重复顶点和边，简单路径不重复顶点。若所有边权非负，从游走中删除一个圈不会增加成本，因此只要目标可达，总可以选到一条不更差的简单路径；零权圈可能造成多条同值游走，但不妨碍简单最优路径的存在。

有负权时，两种问题必须分开。若某负权圈从起点可达并且还能通向目标，可以绕圈任意多次，使到目标的游走成本任意低，所以没有有限最短游走。若强行禁止重复顶点，简单路径集合有限，问题变成另一个组合优化任务，不能再把通常最短路算法的结论原封不动套上去。

图无方向意味着每条边可以双向使用；图有方向则只能按箭头行走。若把一条负权无向边按两个相反方向来走，来回一次已经是负成本闭合游走，因此无向负边会立即引出这一障碍。在有向图中，单独一条负边不一定形成回路，也不一定让问题无解。

一个可以逐步核对的网络

采用图论中的五点无向图：AB 权重二、AC 权重五、BD 权重二、CD 权重一、DE 权重三。要求从 A 到 E 的最小总成本。一条路线 A—B—D—E 的总权重为七，另一条 A—C—D—E 的总权重为九。画图时线段长短不表示权重，判断必须使用标注的数字。

五点加权图中从A经B和D到E的三条边被突出显示，总权重七 — 最少边数和最小权重是两种问题；本例突出路线的权重为 2+2+3=7。

算法维护一个距离标签 d(v)，表示目前已经发现的从起点到 v 的最佳成本，并保存前驱以恢复路线。初始 d(A)=0，其他点为无穷大，表示尚未发现路线，不能把无穷大理解为一条实际路径的长度。沿边 u→v 的松弛操作是 $d (v) \leftarrow min {d (v), d (u) + w (u, v)} .$ 只有当 d(u) 有限时才尝试这次更新。标签缩小时同时把 v 的前驱设为 u；若两条路线成本相同，可以按约定保留任意一条，除非任务要求列出全部最短路线。

Dijkstra 算法的完整过程

Dijkstra 每次从尚未确定的顶点中选取标签最小者，把其距离确定下来，再松弛它发出的边。对本例，过程如下；表中“确定”指从待处理集合中取出，后续正确性依赖非负权条件。

本轮确定	d(B)	d(C)	d(D)	d(E)	新发现的信息
A	2	5	∞	∞	B、C 的前驱为 A
B	2	5	4	∞	D 的前驱为 B
D	2	5	4	7	E 的前驱为 D；经 D 到 C 也为 5
C	2	5	4	7	没有更小标签
E	2	5	4	7	终点距离确定

从 E 沿前驱回溯得到 E、D、B、A，逆序即所求路线。注意 D 虽然在图的字母顺序中排在 C 后面，却先被确定，因为四小于五。只求某个终点时，可以在它被正式确定后停止，不能在第一次给它赋有限标签时就停止。

实现中常用优先队列保存候选标签。若采用重复插入新标签的简便方式，弹出旧条目时需检查它是否已过期，否则可能反复处理无效记录。用支持减小键值的二叉堆和邻接表，标准时间界为 $O ((| V | + | E |) \log | V |)$ 。采用重复入堆、跳过过期项的实现时，更直接的界为 $O (| V | + | E | \log (| E | + 1))$ ；在简单图中可化到常用的顶点数对数形式。多重图可能有大量平行边，应保留与实际边数相配的界。小规模稠密图直接线性扫描候选点也可能更简洁。

为什么最小标签可以安全确定

证明抓住一个不变量：已经确定的顶点标签等于真实最短距离，而未确定顶点的有限标签总来自某条实际路线，所以不会低于真实最短距离。初始起点距离为零，在非负权下不会被任何绕行降低。

现在取标签最小的未确定顶点 u，假设存在比 d(u) 更短的起点到 u 路线。在这条路线从已确定集合首次走向未确定集合的边上，设前一点为 x、后一点为 y。x 已经有正确距离，处理 x 时已松弛到 y，所以 y 的标签不超过该路线到 y 的前段成本。由于剩下从 y 到 u 的边权都非负，前段成本不超过整条路线成本，因而 d(y)<d(u)，与 u 是最小候选标签矛盾。

这个证明显示非负性究竟用在哪里：保证后半段不能通过负成本把路线总值降低。并不要求每条边严格为正，零权边也允许；距离并列时任选一个最小标签点同样正确。证明的是成本正确，若有多条最短路，算法输出的具体路线则取决于并列处理规则。

一个负边反例

有向图只有三条边：S→A 权重二、S→B 权重五、B→A 权重负四。从 S 出发先得到 A 标签二、B 标签五，按 Dijkstra 会先确定 A；但真实最短路线 S→B→A 的成本是一。这里没有负权回路，最短路完全存在，只是贪心确定步骤失去正确性。

不能因为某个带负边例子恰好算对，就认为算法仍有一般保证。也不能随意给每条边都加同一常数来消除负数：不同路线经过的边数可能不同，加常数会改变路线之间的成本排序。例如一条单边成本三与一条两边总成本二，原来后者更短；每边加二后，前者成本五，后者成本六，排序反转。

Bellman–Ford：逐轮扩大允许的边数

若允许负边，可从另一种思路出发。令 $d_{k} (v)$ 表示从 S 到 v、最多使用 k 条边的最小游走成本；初始 d₀(S)=0，其他无穷大。同步更新公式是 $d_{k} (v) = min {d_{k - 1} (v), min_{(u, v) \in E} (d_{k - 1} (u) + w (u, v))} .$ 它按最后一条边分类：要么最优路线已经不超过 k−1 条边，要么末边为 u→v，之前最多 k−1 条。公式中的右侧都使用上一轮值，便于严格说明每一轮的含义；实际原地松弛实现可以在一轮中传播更远，但正确性与停止条件仍需按对应实现分析。

在上面的三点负边例子中，第一轮 A=2、B=5，第二轮经 B 更新 A=1。若从起点可达的区域没有负权回路，可以删去非负圈而不增加成本，最短简单路径至多含 |V|−1 条边，所以这么多轮足够。额外再检查一轮仍能改善某个可达标签，便说明有起点可达的负权回路影响相关区域。

若只关心特定终点，还要从受影响顶点检查能否到达目标。图中某个遥远、与起点不连通的负权圈，不影响当前起点问题；起点可达却无法通向目标的负权圈，也不意味着这个目标的最短成本不存在。这些可达性限定使“检测到负环”与“所有终点都无答案”明显不同。

负权回路只影响能从它继续到达的目标

一个具体例子能区分三种距离状态。设有向边 S→A 权一、A→B 权一、B→A 权负三、S→T 权五，并令 U 与其余顶点不连通。A—B—A 每绕一圈成本减少二，因此 A、B 的距离下确界为负无穷；T 的最短距离仍是五，因为从负圈没有边通向 T；U 则不可达，距离记为正无穷。三个状态不能只用一个“失败”标记代替。

若再添加 B→T 权一，就可以先在负圈绕任意多次再去 T，此时 T 也没有有限最短游走。程序在检测到可达负圈以后，应从受到进一步松弛影响的顶点向前搜索，把能够继续到达的顶点标为负无穷；没有受到影响且可达的点仍有有限答案。只对一个目标查询时，也可先反向搜索出能通向该目标的顶点，再与起点可达集合取交。

这一区分也影响最短路证书。若起点可达的某处有负圈，但它无法通向目标，那么在整个起点可达区域上未必存在一组有限势函数标签满足全部边不等式；这并不妨碍目标有有限最短路。将证书限制在“起点可达且可以到达目标”的相关区域，才准确匹配这次查询。任何起点到目标的路线都完全位于这个区域，所以不会漏掉候选路线。

复杂度与实现中会破坏证明的细节

Bellman–Ford 的标准实现至多进行顶点数减一轮松弛，每轮扫描全部边，再进行一次负圈检查，时间为 $O (| V | | E |)$ ，距离与前驱数组使用线性于顶点数的额外空间。同步版本需要保留上一轮数组，仍是同一空间量级；若一整轮没有任何更新，可以提前停止，因为全部边不等式已经稳定。

这些界通常把一次加法和比较视为常数时间。如果权重是任意精度整数，还须计入位数造成的算术成本；若使用有限范围整数，距离相加前需要避免溢出，否则一个巨大正数可能变成负数，直接破坏松弛不变量。无穷大应当作为未到达状态处理，不能拿最大的机器整数随意参与加法。

前驱恢复同样需要检查。每次严格改善标签时记录产生该标签的实际边；等长候选不必反复改前驱，否则零权圈可能使一组“成本相等”的前驱指针形成循环。输出有限最短路线时，应从终点沿前驱在有限步内回到起点，并核对每条边与总成本。若算法已判断该目标受负圈影响，就不能把当前有限前驱链当成最终最短路线交付。

如何独立检查输出距离

先取起点可达且能够通向目标的相关区域，并假定目标可达。设这个区域上的有限候选标签函数 π 满足 π(S)=0，且对区域内每条边 u→v 有 $π (v) \leq π (u) + w (u, v)$ 。沿任意 S 到 T 的路线逐项相加，中间标签抵消，得到 $π (T) \leq 路线总权重$ 。若另外找到一条实际路线恰好达到 π(T)，便证明它最短。这是下界加可行路线构成的证书，与线性规划中的对偶思想相通。

在五点图中取 π=(0,2,5,4,7)，可逐边验证双向不等式：例如 C、D 的差为一，恰好等于边权一；D、E 的差为三，等于边权三。路线 A—B—D—E 的总成本等于 π(E)=7，因此无需重新运行算法也能核验结果。若目标不可达，应另外给出可达集合及其没有向外出边的证明，而不对无穷大做普通实数相减。无关区域的负圈不应混入这个目标的有限证书。

无权图也可把每条边权统一看作一，广度优先搜索按距离层展开。它使用队列而不需要一般优先队列，时间为 $O (| V | + | E |)$ 。有向无环图则可以按拓扑顺序松弛，即使存在负边也能求解，因为不存在有向回路。选择算法应先看结构条件，而不是只看算法名称的知名度。

历史、应用与模型边界

Dijkstra 的最短路论文《A Note on Two Problems in Connexion with Graphs》发表于 1959 年；得克萨斯大学保存的作者回顾讨论了这篇短文及其背景。作者回忆，他在 1956 年为 ARMAC 计算机准备面对普通观众的演示，以简化的荷兰铁路网络回答两地之间的最短路线；这种可以清楚提问、可以直接显示结果的具体任务，推动了算法的形成。后来发表的论文还讨论了最小生成树，它要求连接全部顶点、使树的总长度最小，与指定起终点的最短路径是另一种目标。最短路思想还与其他研究者提出的动态规划和网络算法并行发展，不能把所有路由方法都称为 Dijkstra 算法。

交通导航若存在转弯惩罚，状态可能需要记录“从哪条路进入当前路口”，仅以路口作顶点、静态路段作边权就会丢失信息。时间依赖交通、充电续航与容量限制也可能需要扩充状态或改变算法。单车最短路线与全体车辆的最优分配是不同目标；后者还要考虑彼此影响与拥堵。

修改边权后的核验

在五点图中，若 DE 权重从三改为十，可以直接核验新答案。E 只有邻点 D，任何路线都必须经过最后这条边；到 D 的最小成本仍为四，所以答案十四。这个分解既利用图结构，也避免重新枚举所有游走。

编者评注（AI 辅助）

最短路很适合练习“算法为什么能停下来相信一个数”。建议手工记录标签、前驱和已确定集合，并在每次更新旁写出对应实际路线。掌握非负权证明后，再看负边反例与逐轮动态规划，能理解算法条件从何而来。现实路由则应先明确成本是否真能逐边相加；状态设计错误时，再快的算法也只能精确回答错误的问题。

参考来源与延伸阅读

MIT 6.006，Lecture 17: Bellman–Ford：负权、松弛与算法正确性，授课教师 Srini Devadas。
MIT 6.006，2011 年秋季课程讲义第 15–18 讲：单源最短路、Dijkstra 与 Bellman–Ford 的假设及复杂度。
E. W. Dijkstra：关于 1959 年图算法论文的作者回顾，UT Austin 档案。
Oscar Levin：图的定义，先修图结构。
图论 · 优化 · 线性规划 · 矩阵。