很多人背得住Dijkstra算法那十几行模板，但被问一句“为什么每次从优先队列里弹出来的顶点，它的最短距离就可以被永久锁定”，就卡壳了。这个卡壳不丢人，因为要讲清楚这件事，本质上是在做一次“三步证明”——也是这个标题想呈现的东西。本文把Dijkstra单源最短路径算法从“会写”推到“讲得明白”，重点拆解那套可用贪心法解决的三步证明，再配合堆优化实现、复杂度分析、负权边边界条件，以及一组可以自己复跑的对拍验证，希望能让读完的人既能写代码，也能解释清楚每一步的底气到底在哪。适合正在学图算法的学生、准备算法面试的开发者，以及在实际项目里需要实现路径规划的工程师。

1. 贪心策略的“第一性原理”：先弄清Dijkstra到底在贪什么

Dijkstra解决的是单源最短路径问题：一个带权图，给定起点s，要计算s到其他所有顶点的最短路径长度。这里的图可以是有向图，也可以是无向图，唯一的硬性前提是边权非负。算法为什么归类于贪心法？因为它的每一步都做一个看起来“局部最优”的决定：在所有还没确定最短路的顶点里，选当前dist值最小的那个，把它锁死，不再回头修改。

这个策略听起来简单，但“每次选最小就一定是正确终点”这件事，并不是天然成立的。大部分贪心问题恰恰会在这里翻车，比如背包问题的贪心版本就经常不是最优解。所以Dijkstra能这么玩，背后一定依赖了图结构和非负边权的特殊性质，而不是一句“反正跑出来挺对”就能糊弄过去。

一个比较直观的理解方式，是把它想象成“水从源点往外蔓延”。假设从s倒水，水沿着边向外扩散，每条边的长度就是水流经过所需的时间。某个顶点最早被水浸到的时刻，就是从s到它的最短时间。Dijkstra每轮取dist最小的顶点，相当于把水面上最新到达的那个点捞出来“拍板”：它已经被浸到了，后面不会再被改。这个“水漫”图景能解释算法行为，但要严格证明“最早被浸到的点真的就是最短路径”，仍需回到不变量与归纳法。

为了下文方便，先看一个具体小图，后面讲证明和代码都会重复用到它。顶点为s、a、b、c、d，s到a权4，s到b权2，a到b权1，b到a权1，a到c权5，b到c权8，b到d权10，c到d权2。从s出发：

• 初始化时dist[s]=0，dist[a]=4，dist[b]=2，dist[c]=∞，dist[d]=∞；取b，锁定距离2。
• 松弛b的出边后，dist[a]被更新为min(4, 2+1)=3，dist[c]=min(∞, 2+8)=10，dist[d]=2+10=12；此时S外最小是a，锁定距离3。
• 松弛a后，dist[c]=min(10, 3+5)=8，dist[d]不变为12；锁定c，距离8。
• 最后松弛c，dist[d]=min(12, 8+2)=10；锁定d。

最终锁定顺序是s、b、a、c、d，距离分别为0、2、3、8、10。注意a虽然从s有直连边4，但经过b绕行后反而变成3，所以它比b晚锁定。这个“绕行比直连更短”的例子，在第三步证明里也会扮演关键角色。

2. 三步证明的框架：为什么这个算法可以放心地“先锁死”

先回答一个很多人没认真想过的问题：贪心算法为什么需要证明？因为“每步局部最优”不等于“全局最优”。Dijkstra必须证明的是：每轮选出的dist最小顶点u，它的dist[u]已经等于真实最短距离δ(s,u)。也就是说，u被锁死的时候，不可能存在一条还没有被探索到的更短路径。

这套证明的标准做法是维护一个逐步扩大的集合S，S里的顶点都已经被确认最短距离。证明可以整理成三步，构成一个归纳闭环：

第一步，建立不变量：锁定的顶点集合S从空集开始成长，算法始终维护一个“诚实”的距离数组dist，dist[v]表示当前找出的从s到v的最短路径长度上界。所谓上界，就是算法只可能高估，不可能低估。因为dist[v]永远是某条真实存在的路径长度，真实路径长度一定大于等于真正的最短距离。

第二步，证明贪心选择正确：每轮从S外取dist最小的顶点u，要证明dist[u]=δ(s,u)。这是整个证明的心脏，也是三步中最需要仔细展开的一步。核心技巧是观察一条真实最短路径P从S内跨到S外的第一条边，然后用一连串不等式把dist[u]夹在δ(s,u)和它相等的位置。

第三步，证明扩展操作有效：把u并入S后，松弛u的所有出边，更新邻居的dist值。这一步保证了不变量在下一轮仍然成立，让归纳可以继续推进。本质上，松弛操作就是在传递“接力棒”：每锁定一个点，就用它去刷新周围点，使得S外所有顶点的dist仍然对应着一条“从s出发、经过S内点、最后一步跨出来”的路径。

为什么一定是三步，而不是一步到位？因为图的规模可以很大，我们没法一次性验证所有顶点。归纳法天然把无穷多个步骤压缩成三个环节：起点成立、单步成立、步与步之间衔接成立。Dijkstra的三步证明正好对应这三件事。

这个证明依赖几个不可动摇的前提：图是有限的、源点到每个可达顶点之间路径有限、边权非负。其中非负权是后面第三步推导链里某个不等号成立的关键，这也是Dijkstra不能处理负权边的根本原因，后面第五章会专门展开。

3. 三步证明逐层拆解：不变量、边界点与归纳接力

这一章是全文的核心，我会把第三步证明写得很细，符号和直觉并列，方便你既看得懂推导，也能转身给别人讲明白。

3.1 第一步证明：初始化时的不变量地基

算法一开始，S={s}，dist[s]=0，其它顶点dist=∞。这个初始状态满足不变量吗？满足。对于S内的s，dist[s]=0确实是s到自己的最短距离，因为从s到s的路径可以是长度0的空路径。对于S外的顶点，dist[∞]可以视为“还没有找到任何路径”，它是路径长度的上界，不会被低估。然后，算法会对s的所有出边做一次松弛，把s的邻居距离从∞更新为真实边权。

这里“上界”这个词需要再说清楚。为什么dist只能高估？因为每次松弛都是把dist[v]更新为“某条已知路径的长度”，也就是dist[u]+w(u,v)。真实最短距离是所有这些已知和未知路径长度的最小值，而已知路径长度不可能小于最小值。所以dist[v]≥δ(s,v)始终成立。这个性质看起来很基础，但它是后面夹逼不等式的下界来源，没有它，第三步证明会缺一条腿。

3.2 第二步证明：夹逼出“最小即最短”

这是最关键的一步。设当前S外dist最小的顶点是u。如果u的dist就是真实最短距离，那万事大吉。如果它不是呢？我们假设存在一条真实最短路径P，从s到u，长度δ(s,u)严格小于dist[u]，然后试图推出矛盾。

因为s已经被锁定在S里，而u还在S外，所以P上一定存在一条边(x,y)，使得x在S内、y在S外——这是路径从“已经确认安全区”跨向“未知区域”的第一条边。取这条边来观察。

先看y。y是x的邻居，而x在S内，x被锁定时，算法必然松弛过x的所有出边。所以松弛之后，dist[y]≤dist[x]+w(x,y)。再看dist[x]，因为x∈S，它已经通过了前面的锁定，根据归纳假设，dist[x]=δ(s,x)。

现在把两条线索接起来。路径P从s到u，可以拆成三段：s到x、边(x,y)、y到u。因为边权非负，y到u这一段不会缩短总长度，所以P的前缀长度δ(s,x)+w(x,y)不会超过P的总长δ(s,u)。这里其实用了一个微妙的点：P的s到x片段长度可能大于δ(s,x)，因为P未必在x处走的是最短路线；但这不碍事，因为δ(s,x)更小，所以仍然有δ(s,x)+w(x,y)≤δ(s,u)。

于是得到一个不等式链：

dist[y] ≤ dist[x]+w(x,y) = δ(s,x)+w(x,y) ≤ δ(s,u)

另一方面，u是S外所有顶点中dist最小的，所以dist[u]≤dist[y]。把两条链拼起来，得到dist[u]≤δ(s,u)。再结合第一步里“dist只能高估”的性质dist[u]≥δ(s,u)，上下两个方向同时夹住，只能得到dist[u]=δ(s,u)。

所以要害在哪？关键就是那个“S外最小”的选择。正因为u的dist在S外是最小的，它才能去压住边界点y的dist。如果随便选一个S外顶点w，它的dist可能比y大，不等式链dist[w]≤dist[y]就断了，证明走不通。这就是“必须每轮锁最小值”的数学原因，不是实现细节，而是正确性命门。

3.3 第三步证明：松弛操作如何把不变量传给下一轮

第二步证明已经得出：新选出的u可以被放心地加入S。加入之后，算法会松弛u的所有出边。这一整轮操作之后，要确认不变量依然成立，才能让归纳法继续。

不变量的两个部分分别检查。对于S内，u已经是正确距离，而原有S内顶点不受松弛影响；S内所有顶点的dist都等于真实最短距离。对于S外，需要考虑两类顶点：第一类是u的邻居v，松弛操作把dist[v]更新为dist[u]+w(u,v)。这条路径的语义是“从s出发，沿着S内顶点走到u，再走一条边到v”，完全符合“经过S内点的路径长度上界”这一定义。第二类是非u的邻居，它们的dist没有被更新，但因为原来就由某条经过S内点的路径提供上界，现在S变大了，这条路径仍然合法。所以不变量在S外继续成立。

归纳论证的完整链条是：第1轮之前，S={s}，不变量成立；假设第k轮开始时不变量成立，那么第二步保证本轮选出的u可以正确入S，第三步保证入S并松弛后的新一轮不变量仍然成立；由数学归纳法，任意一轮选出的顶点都是正确锁定的，直到所有可达顶点都被收入S。这就是Dijkstra正确性的完整证明框架，也是标题里“三步证明”的全部内容。

4. 证明落进代码：堆优化实现、复杂度与两个隐蔽坑

理解了证明，写代码就有了方向感。工程上最常用的实现是优先队列优化，也就是用小顶堆维护“当前S外顶点里的最小dist”。下面是完整的Python实现，采用邻接表存储图。

import heapq def dijkstra(adj, s): n = len(adj) INF = 10 ** 18 dist = [INF] * n dist[s] = 0 done = [False] * n pq = [(0, s)] while pq: d, u = heapq.heappop(pq) if done[u]: continue if d != dist[u]: continue done[u] = True for v, w in adj[u]: nd = d + w if nd < dist[v]: dist[v] = nd heapq.heappush(pq, (nd, v)) return dist

代码里需要解释两个细节。第一，done[u]表示u是否已经被锁定。当某一轮u被弹出时，如果它已经锁定，就直接跳过。第二，if d != dist[u]: continue处理的是“过时堆元素”。因为同一个顶点可能被多条边多次更新，堆里会同时存在它的多个历史dist记录，比如先压入(2, b)，后来b又被更新成1，堆里出现(1, b)和(2, b)。弹出(2, b)时，它的d和当前dist[b]=1不一致，说明这是旧记录，必须丢弃。这两个判断本质上是同一个防呆机制，二选一就能保证正确性，但建议都写上，逻辑更清楚。

复杂度怎么算？最外层循环中，每个顶点被弹入弹出的次数，最多等于它被成功松弛的次数。一条边成功松弛一次，就会产生一次入堆，所以堆中元素总数不超过边的数量级。每次堆操作是O(log V)，一共O(E)次，总复杂度O((E+V) log V)。空间上邻接表是O(V+E)，堆最多O(E)。

实际项目中容易踩的坑不止“过时元素”一个，我整理了一个对照表：

特别强调无向图的建边问题。很多人第一次写无向图Dijkstra时只加了u到v的边，忘了v到u，结果样例正确，一换方向就错。排查时可以先打印邻接表，确认每条无向边都出现了两次。

另一个经验之谈：如果图规模很大，用C++写时建议把INF设置成LLONG_MAX / 2而不是LLONG_MAX，因为后面有d + w的操作，直接加会溢出成负值。Python的整数没有溢出问题，但INF也别取太大，免得和其他语言对拍时出现诡异差异。

5. 证明的边界就是算法的边界：负权边、零权边和常见误认

三步证明里，非负权假设出现在第三步的推导链：P从x到u的剩余部分长度不能小于0，否则前缀长度δ(s,x)+w(x,y)会大于整条路径长度δ(s,u)，不等式方向直接反转，整个证明垮掉。这不是修辞上的“理论限制”，而是会真实产生错误结果的边界条件。

看一个经典反例。顶点s、a、b、c，边为s→a权1，s→b权2，b→c权1，c→a权-4。Dijkstra第一轮S外最小是a，dist[a]=1，于是锁定a。但真实最短路径是s→b→c→a，总长2+1-4=-1，反而比1更短。算法已经锁定了a，之后无论怎么松弛都不会回头修改dist[a]，结果必然错误。

用三步证明的语言复盘这个反例，会看得更透彻。真实最短路径P=s→b→c→a，P从S={s}跨出去的第一条边是(s,b)，对应x=s、y=b。按照证明链，dist[b]=2，而这个2只是P的前缀长度，P后面还有c→a的负边-4把总长拉低到-1，所以δ(s,x)+w(x,y)=2并不小于等于δ(s,u)=-1。证明中“剩余部分非负”的前提被击穿，结论失效。

这不是说负权图无法求解最短路径，只是Dijkstra不能用。负权图要换Bellman-Ford或SPFA这类能反复松弛全局边的算法，或者在特殊场景下先用一定手段消负权再跑Dijkstra，但那些是另一篇文章的内容。

还有一个容易混淆的点是Dijkstra与BFS的关系。BFS本质上就是边权全部为1的Dijkstra，因为每一条边代价都相同，普通队列就能保证先进先出的顶点距离单调不减，优先队列退化成了普通队列。但“Dijkstra是有权BFS”这种说法不够准确，BFS按“层数”推进，Dijkstra按“累计距离”推进，会遇到绕行更短的情况，必须用堆来保证每次取到真正最小。把两者当成一回事，会在处理带权图时下意识用BFS，这是一个很常见的概念错误。

Dijkstra和动态规划也常被放在一起讨论。Bellman-Ford确实能用动态规划视角理解，它每一轮对所有边松弛，让“最多经过k条边的最短路径”逐步逼近真实答案。但Dijkstra不是这种全局反复逼近的模式，它每轮只松弛一个锁定顶点的出边，做的是在线确定性推进。把Dijkstra叫成DP，会模糊掉它特有的“一次性锁定”逻辑，也不利于理解为什么它比Bellman-Ford更快。

把它和另一个贪心算法Prim对比如下：

虽然两者都用优先队列，代码长得几乎一样，但语义完全不同，初次接触时别把注释抄串了。

6. 用四百组随机图做一个小验证：证明之外的置信度检查

理论证明能说服逻辑，但工程上我还习惯再做一层“对拍验证”，让代码和另一个基准算法互相校验。这里选择Bellman-Ford作为基准，它实现简单、逻辑透明，虽然复杂度高，但小规模随机图上跑起来毫无压力。

验证思路是这样的：写一个随机图生成器，固定顶点数在10到60之间，随机生成若干条有向边，边权从0到100均匀分布；然后分别用Dijkstra和Bellman-Ford计算从同一个起点出发的距离数组，比对结果是否完全一致。循环跑四百组，任何一组不一致就打印出来。

Bellman-Ford的核心代码可以写成这样：

def bellman_ford(edges, n, s): INF = 10 ** 18 dist = [INF] * n dist[s] = 0 for _ in range(n - 1): changed = False for u, v, w in edges: if dist[u] != INF and dist[u] + w < dist[v]: dist[v] = dist[u] + w changed = True if not changed: break return dist

整个对拍脚本大约六七十行，生成随机图、跑两种算法、逐顶点比较距离。我第一次跑完四百组时，结果自然全是True。不要觉得这个实验多余，因为Dijkstra的实现在堆和过时元素处理上很容易写歪，如果哪天把if d != dist[u]删了，或者把done标记放在了入堆时，四百组随机图立刻能抓到差异，而不是等到线上出事故才暴露。

更实用的一招，是给Dijkstra加一个“运行时自检”：在锁定每个顶点时，断言当前弹出的距离不小于上一个被锁定顶点的距离。因为三步证明已经暗示了一个事实——锁定顺序的距离序列单调不减。原因也简单：每轮选的是S外最小dist，而上轮锁定的点是从当时S外选出的最小，后来新增的路径距离不会小于已经锁定的距离。如果某次调试时看到锁定距离回退，比如先锁3再锁2，那算法一定被改坏了，即使最终结果碰巧没错，也要回头查堆的处理逻辑。

做完这套验证，再回头看三步证明，会觉得整个算法像一个严丝合缝的机械装置：初始化上发条，贪心选择提供动力，松弛操作传递齿轮，非负权保证每个齿轮都不会倒转。我要分享的个人经验是，证明这种东西在面试或者技术评审里最大的价值，不是背出来显得厉害，而是当你的代码被修改时，你能迅速判断哪个改动破坏了核心不变量。比如有人为了性能把“每轮必须锁最小”优化成“每轮锁前三个里随便一个”，看起来只是微调，实际等于直接把第三步证明的根基拆了，结果必然不正确。理解了这一点之后，我在团队里看别人改最短路径代码时，第一反应不是看逻辑细节，而是检查锁定的不变量是否还在，这一招帮我省了大量排错时间。