图系列第 8 篇：最短路径——从 BFS 到 Dijkstra

嘿，朋友，欢迎回到图系列。今天这篇是第 8 篇，主题是图论里最实用、最出名的算法之一——最短路径。我们要一起回答一个问题：给定一张带权图，怎么从起点出发，找到一条总权重最小的路径？这个问题听起来平平无奇，但它的背后站着 Dijkstra 这样一位大佬，还牵连着导航软件、互联网路由、航班中转、游戏寻路等等一大堆真实场景。在正式动手之前，我们先把前几篇攒下的装备清点一下，因为今天的内容就是站在它们肩上搭起来的。

第 3 篇《图的存储》里，我们学会了邻接矩阵和邻接表。今天的算法需要反复做两件事：拿到某个顶点的所有邻居，以及知道每条边的权重。邻接表把这两件事都做到了 O(1) 起步的方便程度——每个顶点挂一条链表或数组，里面装着它指向的邻居和边权；所以今天所有代码和手算，都默认用邻接表。第 4 篇《广度优先搜索 BFS》更是今天的直接前传：BFS 能在无权图里求出最短步数，它的”逐层扩散”思想漂亮极了；但一旦边有了各不相同的权重，BFS 就会失灵，而失灵的原因恰好是引出 Dijkstra 的最佳入口。树系列第 16 篇《堆》则为我们准备了另一件关键装备——优先队列：Dijkstra 的工程版实现要用它来快速取出”当前距离最小”的顶点，如果你忘了堆的插入、删除和上浮下沉，建议先花十分钟翻回去复习，再回来读今天的第 6 章。

先给本篇画一张路线图：第 1 章，我们通过地图导航和网络路由两个真实场景，把”最短路径”抽象成带权图上的数学问题，并回顾 BFS 为什么只在无权图里成立；第 2 章，用一个”直达贵、绕路便宜”的反例，彻底拆穿”层数少 = 代价小”这个错觉；第 3 章，建立 Dijkstra 的贪心直觉，说清楚”为什么每次挑当前距离最小的顶点就是安全的”；第 4 章，给出算法步骤和伪代码；第 5 章，用一张 7 个节点的图从头到尾手算，把每一轮 dist 表的变化都摊开来看；第 6 章，给出朴素实现和优先队列优化两种版本的代码，逐行解释；第 7 章，讨论负权边为什么会让 Dijkstra 崩盘，并预告第 10 篇的 Bellman-Ford；第 8 章，看看它在导航、OSPF 路由、单词阶梯里的应用，顺带用一句话把 Dijkstra 和 A* 连起来；最后一章是速查表、自测题和下一篇预告。

好，系好安全带，我们出发。

1 问题：地图导航与网络路由，都在求最短路径

1.1 打开手机地图：你每天都在用最短路径

想象一个再普通不过的早晨。你打开手机地图，输入家和公司的地址，地图在零点几秒内给你画出一条推荐路线，附带预计到达时间：左转、直行、上高架、下匝道，清清楚楚。你很少去想，这条路线是怎么算出来的——但只要你稍微较真一下，就会发现事情并不简单：城市里的道路何止成千上万条，为什么软件能这么快挑出一条”合适”的路线？它凭什么知道这条路比那条路快？如果中间有一条路因为早高峰堵车而变慢，它又是怎么重新规划的呢？

把地图抽象成图，一切就有了答案。每个路口是一个顶点，每条道路是一条边；顶点之间并不真的关心道路的直线长度，我们更关心的是通行代价——可以是距离、可以是时间、可以是油费，甚至可以是三者加权后的综合评分。于是”找一条最快的上班路线”就变成了一个非常干净的数学问题：在带权图里，从起点顶点到终点顶点，找一条总权重最小的路径。这条路叫最短路径，那个总权重叫最短距离。注意，“最短”在数学里只是一个名字，它不一定指物理距离最短——当权重是时间时，它指的是最快；当权重是票价时，它指的是最便宜。这个抽象能力极其重要，希望你现在就记住：权重是什么，最短路径就是什么。

下面这张图把”家 → 公司”的地图抽象成了带权无向图。家、地铁站、超市、公司是顶点，路上的数字是通行时间（分钟）：

graph LR
    A["家"] -- "8 分钟" --> B["地铁站"]
    A -- "3 分钟" --> C["超市"]
    B -- "2 分钟" --> D["公司"]
    C -- "6 分钟" --> D
    C -- "1 分钟" --> B

请你先用眼睛扫一遍：从家到公司，直达要 8 + 2 = 10 分钟（家 → 地铁站 → 公司）；如果先到超市再绕到地铁站，再坐一站到公司，要 3 + 1 + 2 = 6 分钟；如果先到超市再去公司，要 3 + 6 = 9 分钟。所以最优路线是家 → 超市 → 地铁站 → 公司，总耗时 6 分钟，比”看起来最近”的直达路线还快 4 分钟。这一个小小的例子已经预告了今天的核心矛盾：路径上顶点越少，不代表总代价越小。我们后面会反复碰到这句话。

1.2 网络路由：数据包也要找最短路径

地图不是唯一用到最短路径的地方。互联网的本质是一张巨大的图：路由器是顶点，路由器之间的链路是边，链路的”代价”可以是延迟、可以是带宽换算出的数字、也可以是运维人员手工配置的权重。当一个数据包要从你的电脑发往千里之外的服务器，它并不真的有”一条固定的路”——它要在沿途的每一台路由器上决定”下一个交给谁”。这个决定依据的，正是路由器里存储的一张”到各个目的地的最短路表”。

举个例子。假设办公室的三台路由器 R1、R2、R3 连成一条链，R1 连着你的电脑，R3 连着公司服务器。如果 R1 到 R2 的链路延迟是 5 毫秒，R2 到 R3 的链路延迟是 20 毫秒，那么从电脑到服务器的总延迟就是 25 毫秒。但如果 R1 和 R3 之间还有一条直连光纤，延迟只有 15 毫秒，路由协议很可能就会选择直连——尽管它绕过了 R2，“路”看起来更短，但延迟更小。这里的”权重”是延迟，我们要求的仍然是一条总权重最小的路径。

真实的互联网比这个例子复杂一万倍：链路会断、延迟会变、流量会拥塞，路由器之间还要靠协议互相交换”我看到了谁”的信息。但无论协议怎么设计，底层求解的都是最短路径。今天学的 Dijkstra，正是很多路由协议（比如后面第 8 章要讲的 OSPF）的核心引擎。所以请别把最短路径当成面试题库里的一朵浮云——你手机里的导航和整个互联网，都在用它。

1.3 把问题正式写下来

把上面两个场景的共性抽出来，我们得到一个正式的问题描述：

给定一张带权图 G = (V, E)，每条边 e = (u, v) 有一个权重 w(u, v) ≥ 0，以及一个起点 s。对图中每个顶点 v，求从 s 到 v 的最短路径长度 dist[v]，即所有从 s 到 v 的路径中，边权之和的最小值。如果 v 不可达，记 dist[v] = ∞。

注意我特意写了 w(u, v) ≥ 0。为什么权重要非负？这可不是多此一举，而是 Dijkstra 的命门，第 7 章会专门用一个反例来说明：一旦允许负权边，整个算法就会崩塌。现在先把这个前提记在脑子里。

另一个值得强调的点是：我们求的是一张表，而不是一条路径。很多初学者以为最短路径问题就是”从 A 到 B 找一条路”，但 Dijkstra 的常规形态是从一个起点出发，一次性算出到所有顶点的最短距离。这听起来更费劲，实际上反而更划算——因为算法在寻找某个目标的过程中，本来就会顺路把其他顶点的距离也算出来。至于”只要 A 到 B 一条路”，可以在算出距离表后从 B 沿着前驱指针一路回溯，或者中途提前终止，这些都是工程上的小优化，不影响算法骨架。

1.4 回顾 BFS：为什么它能在无权图里找到最短路径

在进入带权图之前，先回到我们熟悉的舒适区：无权图。所谓无权图，可以理解成每条边的权重都是 1，也可以理解成”每条边的代价相同”。第 4 篇我们证明过一个结论：在无权图里，BFS 从起点出发，第一次发现某个顶点时记录的距离，就是它到起点的最短距离。当时我们用的比喻是水波：把石头扔进池塘，涟漪一圈一圈往外扩，第 k 圈碰到的顶点，到起点的最短步数就是 k。

为什么这个结论成立？关键在于一个隐蔽的前提：每一步的代价一样大。因为每条边都值 1，所以”走了多少条边”和”花了多少代价”是同一件事；路径越长，代价越大，路径越短，代价越小。BFS 一层一层向外推进，先扫完所有”1 条边能到”的顶点，再扫”2 条边能到”的，天然保证了”第一个发现顶点 v 的时刻，就是边数最少的路径到达 v 的时刻”。换句话说，在无权图里，BFS 的”层号”就是代价，层号最小就是代价最小。

下面这张图复习一下 BFS 的分层视角。A 是起点，B、C 在第 1 层，D 在第 2 层：

graph LR
    subgraph L0["第 0 层：累计代价 0"]
        A["A"]
    end
    subgraph L1["第 1 层：累计代价 1"]
        B["B"]
        C["C"]
    end
    subgraph L2["第 2 层：累计代价 2"]
        D["D"]
    end
    A --- B
    A --- C
    B --- D

在无权图里，A 到 D 的路径 A → B → D 走了 2 条边，代价是 2；BFS 在第 2 层第一次碰到 D，于是 dist[D] = 2。不会有任何路径用 1 条边到达 D，因为那意味着 D 和 A 直接相连，它就该出现在第 1 层。这个推理朴素、干净，且严格成立。

1.5 BFS 的舒适区，在带权图里轰然倒塌

现在把边权从”统统是 1”改成”各不相同”，问题立刻来了：BFS 的层号还是”边数”，但代价不再是边数了。一条路径可能绕了 4 个弯却只花了 5 块钱，另一条路径直来直去 1 条边却要收 100 块钱。BFS 只关心”先碰到谁”，它不关心”碰到你时花了多少钱”——于是它给出的答案，很可能只是”边数最少”，而不是”代价最小”。

更麻烦的是，BFS 还有一个致命的行为：它在第一次发现顶点时就把距离定下来了，以后再也不更新。这在无权图里是对的，因为第一次发现一定对应最短边数；但在带权图里，“第一次发现”和”代价最小”之间没有任何必然联系。你完全可能在一条又贵又近的路上先碰到某个顶点，而一条便宜但绕远的路还没来得及走到它。如果算法把第一次碰到的距离当成最终答案，那就错了。

用一个更生活的场景来感受它。你去超市，BFS 式的策略是”先问哪个柜台离门口最近”，而真实目标可能是”哪个柜台结账最快”。门口最近的那个柜台可能排着 50 人的长队，绕到超市最里面那个柜台反而 5 分钟就结完账。“离门口最近”和”结账最快”是两套不同的度量，BFS 解决的是前者，带权最短路要解决的是后者。第 2 章我们就用一个严格的反例，把这件事钉死。

1.6 本篇真正要解决的问题

把 1.1 到 1.5 串起来，本篇的核心问题浮出水面：

给定带权图（权重非负）和起点 s，如何高效且正确地求出 s 到每个顶点的最短路径？

答案是今天的主角 Dijkstra 算法。它保留了 BFS”从近到远逐层扩展”的优雅气质，但把”层”重新定义成了累计代价，而不是经过的边数。为了实现这个”按累计代价从近到远”的顺序，它需要一个新的工具——优先队列。这就是为什么我们把树系列第 16 篇的堆请来当嘉宾：堆负责快速找到”当前已知距离最小的顶点”，Dijkstra 负责判断”这个顶点现在可以定案了”。

接下来，我们先用一个反例把 BFS 的失败看得明明白白，再顺势推出 Dijkstra 的救赎方案。

2 一个反例：层数少，不等于代价小

2.1 直达很贵，绕路很便宜

请看下面这张图。起点是 A，终点是 B。A 和 B 之间有一条直达边，权重 100；同时 A 先到中转站 M（权重 1），再从 M 到 B（权重 1）。为了直观，我们把权重当成”票价”来读：直达票 100 元，绕路票全程只要 2 元：

graph TD
    S["A（起点）"] -- "直达：票价 100 元，边数 1" --> T["B（终点）"]
    S -- "票价 1 元" --> M["M（中转站）"]
    M -- "票价 1 元" --> T

这张图小得不能再小，却精确地踩中了 BFS 的软肋。从 A 到 B，一共有两条路径：

第一条：A → B，边数 1，总票价 100 元。

第二条：A → M → B，边数 2，总票价 1 + 1 = 2 元。

谁是最短路径？按总票价算，显然是第二条，2 元完胜 100 元。但 BFS 会怎么回答？BFS 只数边数：A → B 只有 1 条边，A → M → B 有 2 条边。在 BFS 的分层里，B 在第一层就被发现了——A 的邻居里有 B 嘛——于是 BFS 立刻宣布”B 的最短距离是 1 条边”，并把它定案。它根本不会等到第二层才碰到 B，更不会去比较两条路径谁便宜。结论：BFS 给出的答案是”边数最少”，而这道题要的是”票价最小”，两者不是一回事。

你可能会说：“这个例子太刻意了，谁会把直达修得比绕路贵这么多？“别急着反驳，现实里这种事天天发生。高铁直达票 553 元、用时 4 小时，而”高铁 + 大巴”的换乘方案只要 200 元、用时 5 小时——如果你在乎的是钱，绕路才是最短路径；飞机直飞 2 小时，转机要 6 小时，如果你在乎的是时间，直飞又赢了。权重一变，胜负就变；而 BFS 的层数永远只认”边数”这一本账，所以它天然无法回答”按权重计的最短路径”。

2.2 BFS 在这个反例里到底怎么走

我们把 BFS 的执行过程逐帧放慢，看看它错在哪里。起点 A 入队，dist[A] = 0。出队 A，扫描 A 的邻居：发现 M 和 B。按入队顺序，假设先入队 M、再入队 B，于是 M 的 dist 记为 1，B 的 dist 记为 1。注意，此刻 B 已经被”发现”了，它的距离被钉在 1——在 BFS 的标准实现里，这个顶点已经打上 visited 标记，以后永远不会再被更新。

然后出队 M，扫描 M 的邻居，发现 B。B 已经访问过了，BFS 直接跳过，连”从 M 再到 B 是不是更短”这个问题都不会问。队列清空，算法结束，输出 dist[B] = 1。全程没有一处逻辑错误——按照 BFS 自己的规则，它走得完全正确；只是它的规则（数边数）和题目要求（数票价）不匹配。这不是 BFS 写错了，而是拿错了尺子。

下面这张图用分层视角展示 BFS 眼中的世界。在 BFS 看来，B 属于第 1 层、M 属于第 1 层，而”经过 M 再到 B”的路径属于第 2 层，已经太晚了：

graph LR
    subgraph L0["第 0 层：A（代价 0）"]
        A["A"]
    end
    subgraph L1["第 1 层：BFS 认为到这里只要 1"]
        B["B"]
        M["M"]
    end
    subgraph L2["第 2 层：BFS 认为永远轮不到它"]
        T["A→M→B（真实票价 2 元，却被无视）"]
    end
    A --- B
    A --- M
    M --- T

如果把权重写成”经过的边数”，BFS 是对的：A → B 的边数是 1，确实小于 A → M → B 的边数 2。问题是权重是票价，1 + 1 = 2 小于 100，绕路反而便宜。BFS 之所以在第 1 层看到 B 就放心定案，是因为它默认”后面的层只会更贵”；在无权图里这个默认成立，在带权图里，一条边权重 100 的”第一层路径”，完全可能比两条边权重各 1 的”第二层路径”贵 50 倍。

2.3 把两种”距离”分开命名

为了不再混淆，我们给两个概念各起一个名字：

边数距离：一条路径经过的边数。BFS 优化的就是它。

权重距离（本篇的主角）：一条路径上所有边权之和。Dijkstra 优化的就是它。

一张小表把反例里的两个距离并排放好：

路径	边数	总权重（票价）	边数距离	权重距离
A → B	1	100	1（BFS 选的）	100
A → M → B	2	2	2	2（正确答案）

看这行加粗的对比就明白了：边数距离短的路径，权重距离可能很长；边数距离长的路径，权重距离可能很短。两者之间没有任何单调关系，除非我们额外规定”每条边权重相同”。这就是”BFS 不能直接用于带权图”的全部理由——它优化错了目标函数。

2.4 换个角度：如果把”权重”摊成”子步骤”呢

这里有个特别好的思想实验，能帮你把”代价”这个概念彻底想通。假如所有边权都是正整数，我们能不能把一条权重为 5 的边，拆成 5 条权重为 1 的小边，中间插入 4 个虚拟顶点？比如 A —5—> B，拆成 A —1—> X1 —1—> X2 —1—> X3 —1—> X4 —1—> B。拆完之后，整张图变成了无权图！此时 BFS 不是又能用了吗？

理论上完全正确，而且这个视角很深刻：BFS 不是只能处理”没权”的图，而是只能处理”每一步代价相同”的图。把大权重拆成若干等代价的小步，图的物理结构变了，但”最短路径”的答案不变。可惜这个做法在工程上不可行：如果一条边权重是一百万，就要插入一百万个虚拟顶点，内存直接爆炸。但”把代价拆成均匀小步”这个直觉，恰好揭示了 Dijkstra 的底层哲学——它不真的拆边，而是在脑子里模拟了”按累计代价从小到大逐层扩展”的过程。Dijkstra 的”层”，不再以边数为单位，而是以累计权重为单位。

2.5 从反例里捞出的三句话

在进入第 3 章之前，请把这三句话刻进脑子里，它们是全文的支点：

第一，BFS 的”层号”等于边数，只在每步代价相同时才等于代价。

第二，带权图的最短路径，目标函数是”总权重最小”，与边数无关。

第三，Dijkstra 要做的，就是把 BFS”按层扩展”的次序，改造成”按累计代价扩展”的次序。

第三条说起来轻松，做起来却有一个天大的难题：BFS 的层号是整数、是已知的——扫完第 k 层自然进入第 k+1 层；而带权图的累计代价是连续的、未知的——我们怎么知道”下一个该轮到谁”？答案藏在第 3 章的贪心直觉里。

3 贪心直觉：先确定”当前已知距离最小”的顶点

3.1 从一个朴素的问题开始

假设我们已经对图做了一些探索，手里有一张”目前已知的距离表”dist，其中 dist[s] = 0，其余顶点是 ∞ 或者某个”暂时够到的数值”。注意”已知”这个词：它只是一个上界，意思是”我至少找到了一条路，代价是这么多；也许将来能找到更便宜的，也许不能”。在算法运行的中途，dist[v] 并不一定是 v 的最终答案——这一点和第 2 章 BFS 的”一锤定音”截然不同。

现在问题来了：这么多顶点都顶着未知数，我们能不能找出某一个顶点，拍胸脯保证”它的 dist 已经不会再变小了，可以定案”？如果能，我们就把它从”未确定”划到”已确定”，然后把这个好消息传递给它的邻居——邻居们可能因为”借道”这个已确定的顶点而获得更小的 dist。

直觉给出的候选是：所有未确定顶点里，dist 值最小的那一个。为什么是它？因为它是所有”还有机会变好”的顶点里，目前已知距离最近的。任何想让它变得更小的路径，都必须先经过某个”别的未确定顶点”——可那些顶点的已知距离都比它大，再加一段非负的边权，只会更贵。这话有点绕，我们马上用图把它讲清楚。

3.2 松弛：Dijkstra 唯一的”动作”

先介绍 Dijkstra 世界里唯一的一个动作，它有个专门的名字叫松弛（relax）。松弛做的事只有一件：假设当前在顶点 u，发现一条边 u → v 权重为 w，那么从起点经过 u 再到 v 的总代价是 dist[u] + w。如果这个值比 dist[v] 现在记的值小，就更新 dist[v] = dist[u] + w，同时记录 v 的前驱是 u；如果这个值比现在记的值大或相等，什么都不做。

为什么叫”松弛”？可以想象成一根绷紧的绳子：dist[v] 是绳子的张力上限，当发现一条更省的路时，绳子被放松了一点，张力上限下降。松弛是 Dijkstra 每次扩展时对邻居做的动作，它保证 dist 表永远记录着”到目前为止发现的最好结果”。松弛本身没有任何贪心成分——它就是忠实地记录信息；真正的贪心选择，发生在”该对哪个顶点做松弛”上。

下面这张图展示一次松弛的前后对比。左半部分是松弛前：dist[A] = 0，dist[C] = 1，B 的 dist 还是 ∞；右半部分是松弛后：通过 A → C → B，B 被更新为 3，同时它的前驱指向 C：

graph LR
    subgraph BEFORE["松弛前"]
        A1["A: 0"] -- "1" --> C1["C: 1"]
        C1 -- "2" --> B1["B: ∞"]
    end
    subgraph AFTER["松弛后"]
        A2["A: 0"] -- "1" --> C2["C: 1"]
        C2 -- "2" --> B2["B: 3（前驱 C）"]
    end

注意，松弛只能让 dist 变小，永远不能让 dist 变大。这一点在直觉上无懈可击：我们记录的是”已知的最好结果”，发现更好的才更新，发现更差的当然无视。这个”只降不升”的性质，是后面所有证明的地基。

3.3 关键抉择：什么时候可以给一个顶点定案

松弛本身不产生任何决策——它是被动的、老实的。真正需要动脑子的是：每轮该选哪个顶点来松弛它的邻居？ 选错了，算法就可能给出错误答案（比如 BFS 在带权图里就是”选错了顺序”）；选对了，算法就能保证每个顶点只被确定一次，效率与正确性兼得。

Dijkstra 的答案是：每一轮，从尚未确定的顶点里，挑出 dist 最小的那个，把它定为”已确定”，然后松弛它的所有邻居。选它、定它、松弛邻居，三个动作循环往复，直到所有可达顶点都被确定。

为什么偏偏是”最小”的？我们来做一个思想实验。假设当前未确定顶点里有 u 和 v，dist[u] = 5，dist[v] = 100，而且 u 是那个最小的（至少比 v 小）。现在设想有一条”更好的路”能到达 u，让 dist[u] 从 5 变成 2。这条路不可能直接从起点一路”免费”冲过来——它要经过一连串边，每一条边权都是非负的。在这条路到达 u 之前的最后一个未确定顶点，记作 x。那么这条新路的总代价 = 到 x 的代价 + x 到 u 的边权 ≥ 到 x 的代价。而 x 既然是未确定的，它的 dist 至少是当前未确定集合里的最小值，也就是至少 ≥ dist[u] = 5（别忘了 u 是最小的）。于是这条新路的总代价 ≥ 5。哪怕它最后一段边权是 0，它也省不出比 5 更小的数——想用 2 到达 u，必须经过一个已知距离 ≥ 5 的中间顶点，再加一段非负边权，这在算术上不可能。

这个推理就是 Dijkstra 贪心选择的安全性直觉：一个非负权重图上，当前已知距离最小的未确定顶点，它的 dist 已经不可能再变小了，可以定案。注意这个直觉用到了两个条件，缺一不可：第一，所有边权非负；第二，u 是未确定集合里 dist 最小的。如果边权允许负数，最后那段”再加一段非负边权”就不成立了，整个推理当场崩掉——这正是第 7 章要讲的灾难。

3.4 用一张图看清”已确定”和”未确定”

为了把抽象推理变成画面，我们把算法运行到某一时刻的图摊开。深色的是已经定案的顶点（灰色背景），浅色的是尚未定案的顶点（白底），边上标着权重：

graph LR
    subgraph DONE["已确定集合：距离不会再变"]
        A["A: 0"]
        C["C: 1"]
    end
    subgraph OPEN["未确定集合：dist 只是当前上界"]
        B["B: 3"]
        D["D: 8"]
    end
    A -- "1" --> C
    C -- "2" --> B
    B -- "5" --> D
    A -- "4" --> B

在这张图里，A 和 C 已经确定：A 的距离是 0（起点），C 的距离是 1，它们永不再变。未确定集合里 B 的 dist 是 3（走 A → C → B），D 的 dist 是 8（走 B → D，而 B 目前也才 3）。按照 Dijkstra 的规则，下一轮应该确定 B，因为 3 < 8。确定 B 之后，再通过 B 松弛 D：3 + 5 = 8，和 D 已有的 8 持平，不更新——D 暂时还是 8，但它的”上界”已经经过两条不同路径验证过了。

请观察一个细节：D 的 8 是”暂定”，而 B 的 3 即将被”转正”。二者地位完全不同。未确定顶点的 dist 只是”目前最好的猜测”，随时可能被一条更绕的路推翻；已确定顶点的 dist 是”板上钉钉的事实”，后续所有松弛都只会建立在它之上，绝不会推翻它。Dijkstra 的全部艺术，就在于精准地判断”谁该转正”。

3.5 为什么”全局最小”这个选择是安全的：一句话版

如果只允许我用一句话向别人解释 Dijkstra，我会说：“因为所有边权都非负，任何想绕路到达 u 的方案，都必然先经过一个已知距离不小于 dist[u] 的顶点，再加上一段非负的路，所以绕不出更便宜的结果。”

再给它配一张”路线图”，把推理链条画成流程：

flowchart TD
    A["未确定顶点 u 的 dist 是当前未确定集合里的最小值"] --> B["假设存在一条更便宜的路径 P 到达 u"]
    B --> C["P 上一定有最后一个'尚未确定'的顶点 x"]
    C --> D["x 的已知距离 ≥ dist[u]（因为 u 是最小的）"]
    D --> E["P 的总代价 = 到 x 的代价 + 后续边权"]
    E --> F["后续边权 ≥ 0，所以总代价 ≥ 到 x 的代价 ≥ dist[u]"]
    F --> G["与'更便宜'矛盾，所以这样的 P 不存在"]
    G --> H["结论：dist[u] 就是最终答案，可以定案"]

这个链条每一步都朴素得像小学算术，但它们合在一起，就是 Dijkstra 正确性的全部直觉。我们故意不在这里写严格的数学归纳证明——那是第 9 篇《Dijkstra 深入》的事，本篇只求把”为什么敢这样贪心”讲到你点头。

3.6 两个容易踩的坑

在动手写代码之前，先把两个最常见的理解偏差掐灭。

坑一：以为 Dijkstra 每轮选的是”全局 dist 最小”，不管它确没确定。 不对，已经确定的顶点不会再次被选中；每轮从”未确定集合”里选最小的。如果你把已确定的顶点也放进候选池，要么白做无用功，要么在带负权场景下产生混乱。更关键的是，“已确定”这个标记不是可有可无的装饰，它是算法正确性的组成部分——它代表”这个顶点的答案已经锁死，不再参与竞争”。

坑二：以为松弛是对”已确定顶点”做的。 也不对。我们总是从刚确定的 u 出发，去松弛它尚未确定的邻居 v。已确定顶点的 dist 已经最优，松弛它没有任何意义；而且理论上它的 dist 只会被更小的值更新，而我们已经证明不可能有更小的值。所以每次松弛的目标，一定是”未确定集合”里的顶点。

有了确定规则、有了松弛动作、有了安全性直觉，算法骨架已经呼之欲出。第 4 章我们把它写成正经的步骤和伪代码。

4 Dijkstra 算法步骤：初始化、取最小、松弛

4.1 三张表 + 一个主循环

Dijkstra 需要维护三类数据，我们把它们叫”三张表”：

第一张是 dist 表：dist[v] 记录”从起点 s 到 v 目前已知的最小代价”。初始化时，dist[s] = 0，其余顶点全部是 ∞。∞ 不是数字，而是一个哨兵，意思是”还没找到任何路径能到达这个顶点”。任何有限值都比 ∞ 小，所以第一轮一定能选到起点。

第二张是 prev（前驱）表：prev[v] 记录”目前已知最优路径上，v 的前一个顶点”。它不参与算法主流程的数学计算，但它是路径还原的关键——等 dist 全部算完，从终点一路沿着 prev 往回跳，就能把整条最短路径倒着打印出来。初始化时 prev 全部为空。

第三张是 done（已确定）表：done[v] 是一个布尔值，标记 v 的 dist 是否已经定案。第 3 章说过，已确定的顶点不会再被选中、也不会被更新。初始化时全部为 false。

有了这三张表，主循环就变得非常短：重复执行”选最小 → 标记确定 → 松弛邻居”三步，直到所有可达顶点都被确定。注意”所有可达顶点”这个措辞——不可达的顶点 dist 永远是 ∞，永远选不中，循环自然会在它们面前停下来；所以我们不需要为”不可达”写任何特殊代码，∞ 本身就是最好的终止信号。

4.2 主循环的每一步在做什么

把主循环拆开，每一轮做三件事：

第一步，取最小：在 done 为 false 的顶点里，找出 dist 值最小的那个，记作 u。这一步是算法的”方向盘”，决定了扩展的顺序。在朴素实现里，我们用一个线性扫描完成它；在优化实现里，用一个优先队列完成它——第 6 章会详细对比。

第二步，标记确定：把 done[u] 置为 true。这个动作的语义是：“u 的最短距离已经找到，就是 dist[u]，以后不再修改。“第 3 章的贪心直觉保证这一步安全：因为 u 是未确定集合里最小的，任何绕路方案都省不出更小的值。

第三步，松弛邻居：遍历 u 的所有出边 (u, v, w)，检查”先到 u、再走这条边”是否比 v 目前记录的 dist 更好。如果 dist[u] + w < dist[v]，就更新 dist[v]，并把 prev[v] 设为 u；否则什么都不做。注意，我们松弛的是 u 的邻居，无论这些邻居是否已经确定——不过在实践中，已经确定的邻居一定不会满足更新条件（否则就推翻了自己的定案，而贪心证明排除了这种可能），所以代码里通常不写这个判断，让它自然失败即可。

这三步的先后顺序能不能换？不能。必须先确定 u，再松弛它的邻居，因为松弛依赖”dist[u] 是最终值”这个事实。如果先松弛后确定，或者确定错了顶点，整个算法就会像带权图里的 BFS 一样给出错误答案。

4.3 伪代码

把上面的话浓缩成伪代码，一共不到二十行：

function dijkstra(graph, s):
    dist = 数组[V]，全部初始化为 ∞
    prev = 数组[V]，全部初始化为 null
    done = 数组[V]，全部初始化为 false
    dist[s] = 0

    for 循环 V 次:
        u = 在 done[u] == false 的顶点中，dist 最小的那个
        if dist[u] == ∞:
            break                    // 剩下的顶点都不可达
        done[u] = true               // 确定 u
        for (v, w) in graph[u]:      // 松弛 u 的每条出边
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                prev[v] = u

    return (dist, prev)

请把这份伪代码和下面的流程图对照着读。流程图画的是同一个算法，只是把”循环条件”画成了显式的判断框：

flowchart TD
    S1["初始化：dist[s]=0，其余 ∞；prev 全空；done 全 false"] --> S2["所有顶点处于未确定状态"]
    S2 --> Q{"未确定集合为空？"}
    Q -- "是" --> END1["结束：返回 dist 与 prev"]
    Q -- "否" --> PICK["在未确定顶点里找 dist 最小的 u"]
    PICK --> CHK{"dist[u] = ∞？"}
    CHK -- "是" --> END1
    CHK -- "否" --> MARK["把 u 标记为已确定"]
    MARK --> RELAX["对 u 的每个邻居 v：若 dist[u]+w 更小，则更新 dist[v] 并记录 prev[v]=u"]
    RELAX --> Q

你可能会疑惑：为什么循环次数写成 V 次，而流程图里又画了”未确定集合为空”的判断？两个视角说的是同一件事：未确定集合最多有 V 个顶点，每轮确定一个，所以最多 V 轮；如果提前遇到 dist[u] = ∞，说明剩下的顶点与起点不连通，后面的轮次全是空转，提前 break 只是省时间。数学上，把循环跑满 V 次也不会出错——每次都会选中一个 ∞ 的顶点，松弛它的出边（全是 ∞ + w，仍然不小于任何有限值，不会有任何更新），然后标记确定，纯属浪费。

4.4 伪代码里容易写错的三个细节

写 Dijkstra 时，九成的 bug 出在下面三个地方，这里先给你打预防针。

第一，∞ 的表示。在伪代码里 ∞ 只是符号；真实代码里常用 Number.MAX_SAFE_INTEGER、非常大的数、或者 null 来表示。比较时要小心：如果你用 null 表示不可达，就必须先判断 v 当前是否为 null 再比较；如果你用一个大数，要确保它大过所有合法答案（比如边权和的上界），否则大数加边权溢出会变成负数，算法瞬间错乱。

第二，取最小必须跳过已确定顶点。有的初学者把”找到 dist 最小的顶点”实现成”直接扫整个数组取最小”，忘了检查 done，结果每一轮都选中起点 s——因为 s 的 dist = 0 永远是数组里最小的。这样的代码会无限循环或反复松弛同一个顶点。正确写法是”在未确定集合里取最小”，写代码时要么用一个显式的 done 判断，要么用集合/堆来天然排除已确定顶点。

第三，更新 dist 时要同步更新 prev。prev 是路径还原的唯一线索，漏掉一行 prev[v] = u，最终 dist 正确但路径打印不出来，或者打印出一条”看起来对不上账”的路径。建议把”更新 dist + 更新 prev”当成一个原子动作来写，养成肌肉记忆。

4.5 “取最小”是 Dijkstra 性能的咽喉

读到这里，你可能已经发现：Dijkstra 的骨架简单到几乎没有自由度——初始化、循环、选最小、松弛。真正的自由度全在”取最小”这一步。线性扫描整个数组要 O(V)，每一轮都扫，总共 O(V²)；用堆来做，每次取最小只要 O(log V)，总共 O(V log V + E log V)。当顶点数从几百变成几百万，这个差距是”毫秒”和”永远跑不完”的区别。

但先别急着上堆。第 5 章我们先用朴素的”线性扫描版”手算一遍完整例子——手算时你不可能真的维护一个堆，线性扫描反而最直观；第 6 章我们再回头把性能账算清楚，并给出优先队列版的完整代码。先正确，再高效，这是学习算法永远的顺序。

4.6 插曲：Dijkstra 与 BFS 其实是同一副骨架

写到这儿，值得停下来做一件特别有教育意义的事：把 Dijkstra 和 BFS 并排放在解剖台上，看看它们的骨架有多像。第 4 篇我们学的 BFS 用队列，今天学的 Dijkstra 用优先队列；BFS 按”层号”排序，Dijkstra 按”累计权重”排序。除此之外，两者的循环结构惊人地一致：

环节	BFS	Dijkstra
初始化	起点入队，dist 全部置 0	起点入堆，dist[s] = 0，其余 ∞
取下一个	从队头取出顶点（先进先出）	从堆顶取出 dist 最小的顶点
第一次访问	标记 visited，距离就此定案	标记 done，距离就此定案
传播信息	把未访问的邻居入队	松弛所有邻居，刷新 dist 并入堆
正确性条件	每条边代价相同	每条边权非负
输出	到各顶点的最少边数	到各顶点的最小总权重

这个对照表藏着整个图算法家族的一个大秘密：很多”看起来完全不同”的算法，共享同一副”扩展骨架”，区别只在’下一个扩展谁’以及’什么时候定案’。BFS 用 FIFO 队列保证”先到先得”，Dijkstra 用优先队列保证”先便宜先得”，A* 用优先队列保证”先有希望先得”，Prim 最小生成树算法甚至和 Dijkstra 长得几乎一模一样——只是把”到起点的距离”换成”到生成树集合的距离”。当你把这个秘密看穿，学新算法就不再是背新模板，而是”换一个排序规则”。

还可以再往前推一步：BFS 其实是 Dijkstra 的特例。如果把一张无权图的每条边都看成权重 1，那么”边数”就是”总权重”，Dijkstra 的排序规则退化成”按层号排序”；在每层内部，用先进先出的队列恰好实现了这个排序（因为同一层的顶点谁也不比谁便宜，谁先来谁先走）。所以我们可以说：Dijkstra 是 BFS 在带权图上的自然推广，BFS 是 Dijkstra 在等权图上的退化形态。有了这个视角，第 1 章那句”从 BFS 到 Dijkstra”就不再只是一个标题，而是同一条进化线的两端。

这个插曲还有一层实际价值：当你被要求”实现 Dijkstra”时，不妨先在脑子里过一遍 BFS 的代码骨架，再问自己三个问题——队列换成什么？“入队”时要不要带上距离？“第一次访问”和”更新距离”的区别是什么？三个问题答完，代码自然就长出来了。

5 完整手算：一张 7 节点带权图，从头走到尾

5.1 主角登场：一张 7 节点的无向带权图

纸上谈兵到此为止，我们来一次完整的实战。下图是一张无向带权图，顶点是 A、B、C、D、E、F、G，共 7 个；每条边上的数字是权重（你可以理解为距离或耗时）。起点是 A：

graph LR
    A["A"] -- "4" --> B["B"]
    A -- "1" --> C["C"]
    C -- "2" --> B
    C -- "8" --> D["D"]
    B -- "5" --> D
    B -- "3" --> E["E"]
    D -- "2" --> E
    D -- "1" --> F["F"]
    E -- "6" --> F
    E -- "7" --> G["G"]
    F -- "2" --> G

先把所有边抄成一张清单，手算时随时查：

边	权重	边	权重
A-B	4	B-E	3
A-C	1	D-E	2
C-B	2	D-F	1
C-D	8	E-F	6
B-D	5	E-G	7
		F-G	2

图有 7 个顶点，所以 Dijkstra 最多跑 7 轮。下面我们一轮一轮走，每轮都记录 dist 表的变化。为了方便追踪，我在表格里用”★“标记这一轮刚被确定的顶点，已经确定的顶点用”●“标出。

5.2 初始化：dist[A] = 0，其余全是 ∞

一开始，三张表长这样：

顶点	A	B	C	D	E	F	G
dist	0	∞	∞	∞	∞	∞	∞
prev	无	无	无	无	无	无	无
done	false	false	false	false	false	false	false

起点 A 的 dist 是 0，其余全部是 ∞。第一轮取最小，毫无疑问选中 A。

5.3 第 1 轮：确定 A（0），松弛 B 和 C

确定 A，done[A] = true。然后松弛 A 的两条出边：

对边 A-B（权重 4）：dist[A] + 4 = 0 + 4 = 4，而 dist[B] 目前是 ∞，4 < ∞，所以 dist[B] = 4，prev[B] = A。

对边 A-C（权重 1）：dist[A] + 1 = 1，dist[C] = 1，prev[C] = A。

第 1 轮结束后的 dist 表：

顶点	A	B	C	D	E	F	G
dist	0●	4	1	∞	∞	∞	∞
prev	无	A	A	无	无	无	无

现在未确定集合是 {B, C, D, E, F, G}，其中 dist 最小的是 C（1）。下一轮轮到 C。

5.4 第 2 轮：确定 C（1），B 被一条绕路刷新

确定 C，done[C] = true。松弛 C 的三条出边：

对边 C-B（权重 2）：dist[C] + 2 = 1 + 2 = 3，而 dist[B] 目前是 4。3 < 4，所以 dist[B] 从 4 降到 3，prev[B] 从 A 改成 C。这就是一次标准的松弛：B 本来觉得”走 A 直达最划算”，现在发现”绕到 C 再过来”反而省 1。

对边 C-D（权重 8）：1 + 8 = 9，dist[D] 从 ∞ 变成 9，prev[D] = C。

对边 C-A（权重 1）：1 + 1 = 2，不小于 dist[A] = 0，忽略。

第 2 轮结束后的 dist 表：

顶点	A	B	C	D	E	F	G
dist	0●	3	1●	9	∞	∞	∞
prev	无	C	A	C	无	无	无

把第 1、2 轮的变化用一张快照图定格下来。A 和 C 已经确定，B 被刷新为 3，D 刚被探到 9：

graph LR
    A["A: 0（已确定）"] -- "4" --> B["B: 3"]
    A -- "1" --> C["C: 1（已确定）"]
    C -- "2" --> B
    C -- "8" --> D["D: 9"]
    B -- "5" --> D

注意 B 顶点上发生的事：一个顶点在定案之前，dist 可以被更新好几次。B 先被 A 直达探到 4，又被 C 绕路刷到 3。每一次更新都代表我们发现了一条更好的路；只要 B 还没定案，它就一直”保留被再次刷新的权利”。这正是 Dijkstra 与 BFS 的重大区别：BFS 的顶点一旦入队就盖棺定论，Dijkstra 的顶点要等到它自己”当选”才定案。

5.5 第 3 轮：确定 B（3），D 和 E 被刷新

现在未确定集合是 {B, D, E, F, G}，dist 最小的是 B（3）。确定 B，done[B] = true。松弛 B 的三条出边：

对边 B-D（权重 5）：3 + 5 = 8，而 dist[D] 目前是 9。8 < 9，所以 dist[D] 从 9 降到 8，prev[D] 从 C 改成 B。

对边 B-E（权重 3）：3 + 3 = 6，dist[E] 从 ∞ 变成 6，prev[E] = B。

对边 B-A 和 B-C（权重 4、2）：4 + 3 = 7 和 2 + 3 = 5，都不小于 A 的 0 和 C 的 1，忽略。

第 3 轮结束后的 dist 表：

顶点	A	B	C	D	E	F	G
dist	0●	3●	1●	8	6	∞	∞
prev	无	C	A	B	B	无	无

下一轮候选是 {D: 8, E: 6, F: ∞, G: ∞}，最小的是 E（6）。E 抢先于 D 当选——尽管 E 在图中离 A 的”直观距离”更远，但累计权重让它的排名更高。

5.6 第 4 轮：确定 E（6），F 和 G 第一次露头

确定 E，done[E] = true。松弛 E 的三条出边：

对边 E-D（权重 2）：6 + 2 = 8，dist[D] 也是 8。8 < 8 不成立，不更新。这里体现了 Dijkstra 的”只降不升”原则：平局不更新，prev[D] 保持 B 不变。从数学上讲，走 B → E → D 和走 B → D 都是 8，两条路并列最优，选哪条当 prev 都行。

对边 E-F（权重 6）：6 + 6 = 12，dist[F] 从 ∞ 变成 12，prev[F] = E。

对边 E-G（权重 7）：6 + 7 = 13，dist[G] 从 ∞ 变成 13，prev[G] = E。

第 4 轮结束后的 dist 表：

顶点	A	B	C	D	E	F	G
dist	0●	3●	1●	8	6●	12	13
prev	无	C	A	B	B	E	E

这是全过程中最精彩的一轮，我们把它画成完整快照。所有顶点都有了有限距离，其中 A、C、B、E 已确定，D、F、G 还在等待命运的裁决：

graph LR
    A["A: 0 ●"] -- "4" --> B["B: 3 ●"]
    A -- "1" --> C["C: 1 ●"]
    C -- "2" --> B
    C -- "8" --> D["D: 8"]
    B -- "5" --> D
    B -- "3" --> E["E: 6 ●"]
    D -- "2" --> E
    E -- "6" --> F["F: 12"]
    D -- "1" --> F
    E -- "7" --> G["G: 13"]
    F -- "2" --> G

请盯着这张图体会 Dijkstra 的”全局观”：F 目前是 12（A → C → B → E → F），G 是 13（A → C → B → E → G）。它们都还只是上界，随时可能被刷新——果然，下一轮 D 会出手改变 F 的命运。

5.7 第 5 轮：确定 D（8），F 被大幅刷新

未确定集合是 {D: 8, F: 12, G: 13}，最小的是 D（8）。确定 D，done[D] = true。松弛 D 的三条出边：

对边 D-F（权重 1）：8 + 1 = 9，而 dist[F] 目前是 12。9 < 12，所以 dist[F] 从 12 降到 9，prev[F] 从 E 改成 D。F 的纪录又一次被刷新——先被 E 探到 12，再被 D 刷到 9。这再次证明：没定案的顶点，谁也不知道它还会不会更好。

对边 D-E 和 D-C、D-B（权重 2、8、5）：8 + 2 = 10 不小于 6，8 + 8 = 16 不小于 1，8 + 5 = 13 不小于 3，全部忽略。

第 5 轮结束后的 dist 表：

顶点	A	B	C	D	E	F	G
dist	0●	3●	1●	8●	6●	9	13
prev	无	C	A	B	B	D	E

现在未确定集合只剩 {F: 9, G: 13}。F 领先，下一轮轮到 F。

5.8 第 6 轮：确定 F（9），G 的最后一次刷新

确定 F，done[F] = true。松弛 F 的两条出边：

对边 F-G（权重 2）：9 + 2 = 11，而 dist[G] 目前是 13。11 < 13，所以 dist[G] 从 13 降到 11，prev[G] 从 E 改成 F。

对边 F-D 和 F-E（权重 1、6）：9 + 1 = 10 不小于 8，9 + 6 = 15 不小于 6，忽略。

第 6 轮结束后的 dist 表：

顶点	A	B	C	D	E	F	G
dist	0●	3●	1●	8●	6●	9●	11
prev	无	C	A	B	B	D	F

5.9 第 7 轮：确定 G（11），收工

未确定集合只剩 {G: 11}，确定 G，done[G] = true。松弛 G 的两条出边：G-F（2）给 13，G-E（7）给 18，都比 G 的邻居们现有的 dist 大，全部忽略。队列清空，算法结束。

最终 dist 表就是 A 到每个顶点的最短距离：

顶点	A	B	C	D	E	F	G
最终 dist	0	3	1	8	6	9	11
prev	无	C	A	B	B	D	F
确定轮次	1	3	2	5	4	6	7

把每一轮的”当选顶点”连起来看，确定顺序是 A → C → B → E → D → F → G。这个顺序本身就是一个很好的自检工具：被确定的顶点，其 dist 一定是非递减的——0、1、3、6、8、9、11，一路不回头。这是 Dijkstra 的重要特征：它按累计代价从小到大”放行”顶点，跟 BFS 按层号从小到大放行如出一辙。

5.10 路径还原：沿着 prev 走回起点

光有距离还不够，我们还想要”路线”。路径还原的规则非常简单：从终点开始，沿着 prev 一直跳到起点，然后反转顺序。比如求 A 到 G 的路径：

G 的 prev 是 F，F 的 prev 是 D，D 的 prev 是 B，B 的 prev 是 C，C 的 prev 是 A。倒过来就是 A → C → B → D → F → G。验算一下总权重：1 + 2 + 5 + 1 + 2 = 11，与 dist[G] 完全吻合。注意 D 的 prev 是 B 而不是 E——因为在第 3 轮 B 刷新 D 到 8 时，prev[D] 被设为 B；第 4 轮 E 带来的 6 + 2 = 8 只是平局，不触发更新。所以这条最短路径是 A → C → B → D → F → G，而另一条并列最短的 A → C → B → E → D → F → G（也是 11）没有被记录。Dijkstra 保证的是”至少能找到一条最短路径”，并列的路径保留哪一条，取决于松弛的先后顺序。

下面这张图把最终的最短路径树画出来。从 A 出发，每个顶点都指向它在最短路径上的前驱，整张图形成一棵以 A 为根的树：

graph LR
    A["A: 0"] -- "1" --> C["C: 1"]
    C -- "2" --> B["B: 3"]
    B -- "3" --> E["E: 6"]
    B -- "5" --> D["D: 8"]
    D -- "1" --> F["F: 9"]
    F -- "2" --> G["G: 11"]

等等，这棵最短路径树和我们刚才还原的路径 A → C → B → D → F → G 不完全一致——树里 B 有两条孩子边（E 和 D），而还原路径走的是 B → D。请仔细看：这是同一棵树的两种画法。树中每条边都对应一个 prev 关系：E 的 prev 是 B，D 的 prev 是 B，F 的 prev 是 D，G 的 prev 是 F。沿着”谁的前驱是谁”走，从 A 到 G 的路径是 A → C → B → D → F → G；E 只是树里的另一根分支，与 G 的路径无关。刚才的图是为了展示”最短路径树包含所有顶点的最短路径”，这里的文字是为了强调”还原单条路径时只沿着 prev 链走”，两者不矛盾。

5.11 手算留给我们的三份礼物

这份手算看起来很长，但它其实只演示了一件事：算法对每个顶点只做一次”定案”，每次定案前可能经历多次刷新。三份礼物分别是：

第一，dist 表的”只降不升”。整场手算中，每个顶点的 dist 要么从 ∞ 变成有限值，要么从较大的有限值变成较小的有限值，从来没有变大过。

第二，确定顺序的单调性。当选顶点的 dist 严格非递减，所以”先确定的顶点”一定不会比”后确定的顶点”更远。

第三，松弛只发生在当选顶点的邻居上。每一轮的信息传播半径只有一条边，但通过七轮接力，信息覆盖了整张图。Dijkstra 不需要”看穿”整张图，它只需要耐心地一跳一跳地传播。

这三份礼物会直接转化第 6 章的两个实现版本，以及第 7 章对负权边的深刻理解。

5.12 一份可复用的手算自检清单

手算 Dijkstra 是最容易被”算错一步”的活动，这里给你一份五分钟自检清单，以后无论是考试、面试还是自己验证代码，都可以按顺序过一遍。

第一，初始化时确认起点 dist 为 0、其余为 ∞，并且 prev 全部留空。

第二，每一轮”取最小”前，先在心里划掉已经确定的顶点，再比较剩下的 dist；千万别把已确定的顶点也算进去。

第三，松弛时逐条检查邻居的旧值：新值更小才更新，相等或更大一律不动；更新 dist 的同时必须同步改写 prev，二者是连体婴。

第四，每轮结束后，确认当选顶点的 dist 不比上一轮当选顶点的小（允许相等），一旦出现”回退”，说明你算错了或者图里有负权边。

第五，全部结束后，选一个终点沿 prev 回溯并验算总权重，看它是否等于 dist 表里的值；对不上，就回头检查是 prev 记错还是 dist 算错。

这套清单的本质，是把算法的三个不变量变成检查动作：dist 只降不升、确定顺序非递减、prev 与 dist 同步更新。跑完一遍清单，你对 Dijkstra 的信任度会从”听老师说的”变成”自己验证过的”。

6 实现：从朴素 O(V²) 到优先队列 O((V+E) log V)

6.1 版本一：朴素实现，线性扫描找最小

第 5 章手算时，我们”取最小”的办法是肉眼扫描整张表。把肉眼看表翻译成代码，就是一遍线性循环：遍历所有顶点，跳过已确定的，留下 dist 最小的那个。这是最忠实的实现，一行技巧都没有，适合作为正确性基准。

下面是一份完整的朴素版 TypeScript 代码。约定：顶点编号为 0 到 n-1；graph 是邻接表，graph[u] 是 u 的所有出边，每条出边是一个 { to, weight } 对象：

type Edge = { to: number; weight: number };

function dijkstraNaive(graph: Edge[][], s: number, n: number) {
  const INF = Number.MAX_SAFE_INTEGER;
  const dist = new Array<number>(n).fill(INF);   // 距离表
  const prev = new Array<number>(n).fill(-1);    // 前驱表，-1 表示还没有前驱
  const done = new Array<boolean>(n).fill(false); // 定案标记

  dist[s] = 0;

  for (let round = 0; round < n; round++) {
    // 第一步：在未确定顶点里找 dist 最小的 u
    let u = -1;
    let best = INF;
    for (let v = 0; v < n; v++) {
      if (!done[v] && dist[v] < best) {
        best = dist[v];
        u = v;
      }
    }

    // 第二步：如果找不到（剩下的都不可达），提前结束
    if (u === -1 || dist[u] === INF) break;
    done[u] = true;

    // 第三步：松弛 u 的所有邻居
    for (const { to, weight } of graph[u]) {
      const nd = dist[u] + weight;
      if (nd < dist[to]) {
        dist[to] = nd;
        prev[to] = u;
      }
    }
  }

  return { dist, prev };
}

逐段解释这份代码：

第一段，初始化。dist 全部填 INF，prev 全部填 -1，done 全部填 false。INF 用 Number.MAX_SAFE_INTEGER，它是 JavaScript 里最大的安全整数，任何合法边权和都不会超过它。起点 s 的 dist 设为 0。这里有个值得注意的细节：new Array<number>(n).fill(INF) 一次填满，比 for 循环赋值更简洁，效果完全相同。

第二段，外层的 for (let round = 0; round < n; round++)。最多 n 轮，每轮确定一个顶点。为什么是 n 而不是”直到找不到”？因为提前 break 的条件写在循环体里；把循环上限设为 n 只是给算法一个安全的边界。

第三段，找最小。u = -1 是一个哨兵：如果整个循环结束后 u 还是 -1，说明未确定集合里没有一个有限距离的顶点——要么图空，要么剩下的顶点全部不可达。best 记录当前见过的最小值，初始 INF；!done[v] && dist[v] < best 保证只在未确定顶点里找，且严格小于才更新。这里用 < 而不是 <=，是为了在平局时保留更早的顶点，行为更稳定。

第四段，提前终止。如果 u === -1 或者 dist[u] === INF，说明剩下的顶点都不可达，再跑下去只会反复选中 INF 顶点做无用松弛，直接 break。这个判断让代码对不连通图也正确：不可达顶点的 dist 永远是 INF，prev 永远是 -1，调用方一看便知。

第五段，确定与松弛。done[u] = true 是定案；随后遍历 graph[u]，对每条出边计算 nd = dist[u] + weight，如果 nd 比 dist[to] 小就更新 dist 和 prev。注意我们没有跳过已确定的邻居——因为贪心证明保证它们不会被更新，加了判断反而多余；让自然比较去忽略它们，代码更短、意图更清晰。

复杂度怎么算？外层循环最多 n 轮；每轮”找最小”要扫描 n 个顶点，花 O(n)；每轮”松弛”要把 u 的所有出边看一遍，所有轮加起来恰好是每条边被看一次，共 O(E)。所以总时间是 O(n² + E)。如果图是稠密的，E 接近 n²，这个复杂度是 O(n²)，还算能接受；但如果图是稀疏的（比如真实道路网络，E 和 n 差不多大），O(n²) 就成了瓶颈——n 是 100 万时，n² 是 10 的 12 次方，任何普通机器都跑不动。

6.2 版本二：优先队列，把”找最小”从 O(V) 降到 O(log V)

朴素版的瓶颈一眼可见：每轮都白扫一遍整个数组，只为了挑一个最小的。第 4 章就预告过解法——优先队列（最小堆）。堆能在 O(log V) 时间内取出最小值，也能在 O(log V) 时间内插入新元素；它正是树系列第 16 篇的主角。

但堆有一个使用上的小麻烦：Dijkstra 需要”把某个顶点的 dist 从 4 改成 3”，而普通二叉堆不支持”修改任意元素的值”这种操作——你无法在 O(log V) 时间内定位到那个元素并更新它。怎么绕过去？业界有一个经典技巧：懒惰删除（lazy deletion）。我们不修改堆里的旧条目，而是直接把新值 (3, v) 再推一次；堆里同时存在 (4, v) 和 (3, v) 两个条目。弹出时，如果发现某个条目的 d 不等于 dist[v] 当前值，说明它是过期条目，直接丢弃。这样虽然堆里可能堆积冗余条目，但每个条目的插入和弹出仍是 O(log V)，总复杂度不变。

下面是最小堆的完整实现，它专门为 Dijkstra 定制：每个元素是 { d, v }，d 是距离，v 是顶点编号，比较只依据 d：

class MinHeap {
  private heap: { d: number; v: number }[] = [];

  get size() {
    return this.heap.length;
  }

  push(d: number, v: number) {
    this.heap.push({ d, v });
    let i = this.heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;                    // 父节点下标
      if (this.heap[p].d <= this.heap[i].d) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }

  pop(): { d: number; v: number } | undefined {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0 && last) {
      this.heap[0] = last;
      let i = 0;
      for (;;) {
        const l = i * 2 + 1;
        const r = l + 1;
        let m = i;
        if (l < this.heap.length && this.heap[l].d < this.heap[m].d) m = l;
        if (r < this.heap.length && this.heap[r].d < this.heap[m].d) m = r;
        if (m === i) break;
        [this.heap[m], this.heap[i]] = [this.heap[i], this.heap[m]];
        i = m;
      }
    }
    return top;
  }
}

这段堆代码只有两个操作，值得逐行看一眼：

push 先把新元素放到数组末尾，然后”上浮”：反复与父节点比较，如果父节点更大就交换，直到满足堆性质（父 ≤ 子）。(i - 1) >> 1 是整数除法，用来从下标 i 算出父节点下标；>> 1 比 Math.floor((i - 1) / 2) 更简洁，效果一样。

pop 把堆顶（最小值）暂存，把数组最后一个元素移到堆顶，然后”下沉”：比较当前节点和它的左右孩子，找到三者中最小的，如果最小的不是自己就交换，继续下沉。l = i * 2 + 1 和 r = l + 1 是二叉堆的两个孩子下标公式。这里有个边界细节：const last = this.heap.pop() 之后，如果堆里还剩元素，才需要下沉；如果堆本来就只有一个元素，pop 完就是空堆，直接返回 top 即可。

堆的操作流程用一张图总结：插入走”上浮”，删除走”下沉”，两者的代价都只与树高有关，也就是 O(log V)：

flowchart TD
    PUSH["push：新元素放到数组末尾"] --> UP["与父节点比较：父大则交换"]
    UP --> UPQ{"已经到达根或父 ≤ 自己？"}
    UPQ -- "否" --> UP
    UPQ -- "是" --> DONE1["堆性质恢复"]
    POP["pop：保存堆顶，末尾元素移到堆顶"] --> DOWN["与两个孩子比较：选最小者"]
    DOWN --> DOWNQ{"最小者是自己？"}
    DOWNQ -- "否" --> DOWN
    DOWNQ -- "是" --> DONE2["堆性质恢复"]

6.3 版本三：优先队列版 Dijkstra，完整代码

把最小堆和 Dijkstra 主循环组装起来，就得到工程里最常见的版本：

function dijkstraFast(graph: Edge[][], s: number, n: number) {
  const INF = Number.MAX_SAFE_INTEGER;
  const dist = new Array<number>(n).fill(INF);
  const prev = new Array<number>(n).fill(-1);
  const done = new Array<boolean>(n).fill(false);
  const pq = new MinHeap();

  dist[s] = 0;
  pq.push(0, s);                          // 起点入堆

  while (pq.size > 0) {
    const { d, v: u } = pq.pop()!;        // 弹出当前堆顶
    if (done[u]) continue;                // 懒惰删除：过期条目直接丢
    if (d !== dist[u]) continue;          // 防御性检查：数值不一致也是过期
    done[u] = true;                       // 定案

    for (const { to, weight } of graph[u]) {
      const nd = d + weight;
      if (nd < dist[to]) {
        dist[to] = nd;
        prev[to] = u;
        pq.push(nd, to);                  // 推入新纪录，旧纪录留在堆里当垃圾
      }
    }
  }

  return { dist, prev };
}

这段代码比朴素版短，但每一行都藏着心思，逐行拆开讲：

第一行 const { d, v: u } = pq.pop()!：弹出堆顶并解构。堆顶一定是”堆里现存条目中 d 最小”的。注意这里的 d 是条目里的快照值，它不一定等于 dist[u] 的当前值——如果 u 后来被更短的路刷新过，堆里就会有 (旧值, u) 和 (新值, u) 两个条目，旧条目先被弹出，d 与 dist[u] 不一致。

第二行 if (done[u]) continue：如果 u 已经定案，这个条目必然是冗余的——因为每个顶点只会定案一次，定案之后推入的条目全是垃圾。直接丢弃，继续弹下一个。

第三行 if (d !== dist[u]) continue：这是懒惰删除的正式判据。d 是条目里的快照，dist[u] 是当前纪录；两者不等说明该条目在入堆之后被更新过，属于过期数据。这一行与上一行互为补充：done 判断挡住”定案后的垃圾”，d 判断挡住”定案前的过期”。你也可以只留一个，但两个都写会让代码在各种边界情况下都稳如老狗。

第四行 done[u] = true：定案。到这一步，可以保证 d === dist[u]，而且 d 就是 u 的最终最短距离。为什么？因为堆顶是全局未确定顶点里 dist 最小的——这正是第 3 章贪心直觉要求的”未确定集合里最小”，堆替我们自动完成了这件事。

第五行到第十行，松弛邻居：nd = d + weight 计算借道 u 的代价，如果小于 dist[to] 就更新 dist、prev，并把新条目推入堆。旧条目不删，任由它在堆里腐烂，等它浮到堆顶时被上面两行 continue 掉。这就是”懒惰删除”的全部含义：不主动清理，只在弹出时鉴别。

等一下，有一个细节需要澄清：堆顶的”全局最小”真的等价于”未确定顶点里最小”吗？如果堆顶恰好是已确定顶点（被 continue 丢掉），那下一个堆顶呢？直觉上，堆里可能混着垃圾，但我们弹出的顺序依然是按 d 从小到大。当我们终于弹出一个”非垃圾”条目 (d, u) 时，所有比它小的合法条目都已经处理完了，所以 u 就是未确定顶点里 dist 最小的。懒惰删除没有破坏堆的排序性质，只是让堆稍大了一些。

6.4 复杂度：为什么是 O((V + E) log V)

优先队列版的时间账怎么算？一条一条地数：

初始化：dist、prev、done 三个数组，各花 O(V)。

插入：每个顶点的 dist 每次被刷新都会推入一个新条目。一个顶点的 dist 最多被刷新多少次？每次刷新都要求 nd < dist[to]，而 dist[to] 只会越来越小；理论上刷新次数最多等于入边条数。所有顶点的入边条数之和就是 E，所以整个算法推入的条目总数是 O(E)（每条边最多触发一次成功刷新），每次 push 是 O(log V)，共 O(E log V)。

弹出：弹出的条目数不超过推入的条目数，也是 O(E)，每次 pop 是 O(log V)，共 O(E log V)。

松弛：每条边被扫描一次，共 O(E)，每次扫描是常数时间。

总计：O(V + E + E log V) = O((V + E) log V)。如果图是连通的（E ≥ V - 1），可以更简单地记成 O(E log V)；教科书里常见的写法 O((V+E) log V) 是更完整的表达。

把两个版本摆在一起对比，一目了然：

版本	取最小	总复杂度	适合场景
朴素线性扫描	O(V) 扫描	O(V² + E)	稠密图、教学演示、小数据
优先队列	O(log V) 弹出	O((V+E) log V)	稀疏图、大图、真实路网

一个常见的误区是”堆版本在所有情况下都更快”。未必：当图非常稠密、E 接近 V² 时，朴素版 O(V²) 反而可能赢过 O(V² log V) 的堆版。真实世界里的路网、社交网络大多是稀疏图，所以工程实现几乎一律用优先队列；但面试时如果能说出”稠密图用朴素版、稀疏图用堆版”这个权衡，会显得你真正理解了复杂度，而不只是背答案。

还有一个小优化值得知道：如果边权都是小整数，可以用”桶”代替堆（Dial’s algorithm），把复杂度进一步压到 O(V + E + maxDist) 附近；如果图是稠密图，斐波那契堆理论上可以把”取最小”摊还到 O(log V) 甚至 O(1) 摊还。这些属于进阶话题，第 9 篇会再展开，本篇知道”堆是主流选择”就够用了。

6.5 从手算到代码：两者如何一一对应

最后，把手算和第 6 章的代码做个对照，防止你”看得懂图、写不出码”：

手算里的”扫一遍表找最小”对应朴素版的内层 for 循环；代码里的 done[u] = true 对应手算表格里的”●“标记；代码里的 prev[to] = u 对应手算表格里 prev 列的每一次改写；代码里的 if (nd < dist[to]) 对应手算里”8 < 9 所以更新、8 < 8 所以忽略”的每一次决策。堆版本只是把”扫表”换成了”弹堆”，其余逻辑一字未改。

如果你把第 5 章的 7 节点图编上号（A=0, B=1, C=2, D=3, E=4, F=5, G=6），跑一遍 dijkstraFast，输出应该是 dist = [0, 3, 1, 8, 6, 9, 11]，prev = [-1, 2, 0, 1, 1, 3, 5]，和手算结果完全一致。亲手跑一遍代码、对照一遍表格，胜过读十遍文字。

6.6 边界情况：自环、重边、孤立点与 0 权边

代码能跑通标准例子，不等于在真实数据上不出错。Dijkstra 最容易在四类边界情况上翻车，这里逐一排查，帮你把代码打磨到”怎么喂都不吐”。

自环：顶点 u 连着自己的一条边，权重 w。松弛时检查 dist[u] + w < dist[u]，在 w ≥ 0 时永远不成立（等号只在 w = 0 时出现，而”小于”要求严格），所以自环对 Dijkstra 完全无害，代码不用做任何特殊处理。如果你把判断条件误写成 <=，0 权自环就会让顶点反复自我刷新、无限入堆，酿成事故——所以务必记住：松弛必须用严格小于。

重边：两个顶点之间有多条边，比如 A → B 权重 3 和 A → B 权重 1 同时存在。邻接表里会有两条记录，松弛时各自独立计算：先处理权重 1 的，dist[B] 变成 1；再处理权重 3 的，1 < 3 不成立，忽略。结果自动取最优，无需去重。反过来，如果建图时错误地只保留了最后一条边，把权重 1 弄丢了，答案就会错——所以建图阶段”重复边保留最小权重”是一个好习惯，但算法本身并不依赖它。

孤立顶点：没有任何边的顶点。它的 dist 永远是 ∞，永远选不中，循环在遇到它之前就 break 了。输出时它的 prev 是 -1，dist 是 INF，调用方可以据此判断”不可达”。这正是不连通图的标准结局：算法只负责起点所在的可达部分，其余顶点保持初始值，语义清晰。

0 权边：权重恰好为 0 的边。它不违反”非负”前提，Dijkstra 对它完全有效，但会带来一个有趣的现象：两个顶点可能”同样便宜”，谁先确定取决于堆里的顺序。比如 A → B 权重 0，A 确定后 B 的 dist 变成 0，和起点并列第一。下一轮堆里可能同时有 (0, s) 的过期条目、 (0, B) 的合法条目，谁先弹出谁先确定，但这不影响最终答案的正确性——B 和 s 距离都是 0，先确定谁都是对的。0 权边还会让”确定顺序非递减”变成”确定顺序非严格递增”，第 5 章那句”一路不回头”要理解成”允许相等”，不要教条。

把这些边界情况装进脑子，你的 Dijkstra 就从小白版升级成了能上生产的版本。顺带一提，上面说的每一条，在第 9 篇我们还会结合 LeetCode 风格的题目再练一遍，今天先有个印象即可。

7 负权边：为什么 Dijkstra 会当场崩盘

7.1 一个让人脊背发凉的反例

从第 1 章开始，我们反复强调一个前提：边权非负。你可能已经隐约猜到，这个前提不是随便加的，而是 Dijkstra 贪心证明的地基。现在我们把地基抽掉一块，看看会发生什么。

请看下面这张图。起点 S，顶点 A 和 B；三条边：S → A 权重 2，S → B 权重 1，A → B 权重 -3：

graph LR
    S["S（起点）"] -- "2" --> A["A"]
    S -- "1" --> B["B"]
    A -- "-3" --> B

从 S 到 B 有几条路？直接走 S → B，代价 1；绕一下走 S → A → B，代价 2 + (-3) = -1。正确答案是 -1——绕路不仅不贵，反而倒找钱，因为最后一条边是负的。

现在让 Dijkstra 跑一遍。初始化 dist = [S: 0, A: ∞, B: ∞]。第 1 轮，S 当选，松弛两条出边：dist[A] = 2，dist[B] = 1。第 2 轮，未确定集合是 {A: 2, B: 1}，最小的是 B（1），于是 B 被定案，dist[B] = 1 被锁死。第 3 轮，A（2）当选，松弛 A → B：2 + (-3) = -1，这个值明明比 1 小得多，可 B 已经 done 了，算法只能眼睁睁地看着这个更优解溜走，然后若无其事地输出 dist[B] = 1。

这就是 Dijkstra 在负权边面前的死法：它会把一个顶点过早地定案，而定案之后，任何来自其他顶点的更短路径都被拒之门外。在非负权图里，这种”过早定案”被证明是安全的；一旦出现负权边，“当前已知距离最小的顶点不可能再被刷新”这个命题直接失效——A 的 dist（2）确实比 B 的（1）大，但 A 身上藏着一条通往 B 的负边，让它能给出 -1 这个反超答案。

7.2 破坏发生在哪一环

回看第 3 章的安全性推理，我们当时说：任何想绕路到达 u 的方案，都必然先经过某个未确定顶点 x，而 x 的已知距离 ≥ dist[u]，再加上”一段非负的边权”，所以绕不出更便宜的结果。这个推理有三个支点：

第一，u 是未确定集合里 dist 最小的。

第二，到达 u 的新路径上，最后一个未确定顶点 x 满足 dist[x] ≥ dist[u]。

第三，从 x 到 u 的最后一段路程，边权之和 ≥ 0。

在负权图里，第三根支点断了：最后一段路程可能整体为负，而且负得足够多，把”x 比 u 远”的差距全部抵消还有富余。上面那个反例正是这么运作的：x 是 A（dist 2），u 是 B（dist 1），x 确实比 u”远”，但 A → B 的 -3 让总账变成了 -1。更准确地说，Dijkstra 的贪心选择需要”未来的边只会让代价变高”这个承诺，负权边撕毁了承诺。

还有一个更隐蔽的细节：在第 2 轮，B 被定案时，它其实已经”见过”A 了（A 的 dist 已从 ∞ 变成 2），但算法没有任何机制能预知”A 以后会通过一条负边把 B 拉下水”。你可以给 Dijkstra 打无数补丁——比如”定案前再看看所有未确定顶点能不能刷新它”——但补丁越打越像另一个算法，那个算法就是第 10 篇的主角 Bellman-Ford。

7.3 更可怕的灾难：负权环

单条负权边已经够呛，如果负权边凑成一个环，问题会从”算法给错答案”升级成”答案根本不存在”。请看下面这个环：

graph LR
    S["S"] -- "1" --> A["A"]
    A -- "-2" --> B["B"]
    B -- "-1" --> S

S → A → B → S 这个环的总权重是 1 + (-2) + (-1) = -2。这意味着什么？意味着你可以从 S 出发，绕着这个环走一圈，代价反而少了 2；再走一圈，又少 2。只要你想，你可以无限绕圈，把总代价压到负无穷。在存在负权环的图里，“最短路径”这个概念本身没有意义——不存在一条总权重最小的路径，因为总有一条更小的。

所以带权最短路径问题要分三种情况处理：权重全非负，用 Dijkstra；允许负权边但保证没有负权环，用 Bellman-Ford；存在负权环，问题无解（有些场景下需要检测并报告”存在负环”，而不是给出一个荒谬的距离）。这个三分法非常重要，面试时如果题目里出现负数，先别急着套模板，停下来问自己一句：“图的权重大于等于零吗？”

7.4 预告：第 10 篇的 Bellman-Ford 如何救场

既然 Dijkstra 救不了负权图，谁来救？答案是 Bellman-Ford 算法。它的思路和 Dijkstra 完全不同：Dijkstra 是”每轮挑一个最值得定案的顶点”，Bellman-Ford 是”不挑，把所有边一口气全部松弛一遍，重复 V-1 轮”。每一轮，每条边都有机会把信息向前传播一跳；V-1 轮之后，任何不包含负环的最短路径都已经被充分松弛，dist 表必然收敛。

为什么是 V-1 轮？因为一条不含环的路径最多经过 V 个顶点，也就是最多 V-1 条边；最短路径如果不含环（有负环则无解），它的边数不会超过 V-1，所以把整张图松弛 V-1 遍就足够了。Bellman-Ford 的代价是复杂度：O(VE)，在稠密图里接近 O(V³)，比 Dijkstra 慢得多；它的回报是能处理负权边，还能在最后一轮再松弛一遍来检测负环——如果第 V 轮还有边能刷新 dist，说明存在负权环。

具体怎么实现、怎么证明、怎么写代码，就留给第 10 篇。本篇你只需要记住一句话：看到负权，第一反应不是”给 Dijkstra 打补丁”，而是”换 Bellman-Ford”。

7.5 顺带回答：0 权边算朋友还是敌人

上一节 6.6 里我们说过 0 权边对 Dijkstra 无害，这里再补一刀，把”非负”和”严格为正”的区别彻底说清。很多人以为 Dijkstra 要求”边权都大于 0”，其实它只要求”边权都大于等于 0”。为什么 0 可以？回到贪心证明：我们需要的不是”最后一段路一定变贵”，而是”最后一段路不会让总账变便宜”。0 权边虽然不会让路径变贵，但也不会让路径变便宜——它顶多让两条路打平。打平不破坏”dist[u] 是最小值”的结论，只是可能出现并列第一，谁先确定都无伤大雅。

那 0 权边有没有麻烦？有，但麻烦在实现而不在理论：如 6.6 所说，0 权边会让多个顶点同时拥有相同的最小 dist，堆里可能出现大量并列条目，懒惰删除的工作量略微增加；如果你把松弛条件误写成 <=，0 权边还会诱发无限自我刷新。只要坚持”严格小于 + 已确定检查”，0 权边就是完全安全的。记住这个边界：Dijkstra 的门槛是”非负”，不是”为正”。面试时如果有人问你”Dijkstra 能不能处理 0 权边”，答案是能；如果有人问”能不能处理负权边”，答案是绝对不能——这两句话之间的分界线，就是第 3 章那个贪心证明里”后续边权 ≥ 0”的一行字。

8 应用：导航、路由、单词阶梯，以及通向 A* 的一扇门

8.1 地图导航：Dijkstra 是地基，工程是摩天楼

回到第 1 章的手机地图。真实导航软件当然不会只跑一个裸 Dijkstra——路网有几百万个顶点，逐顶点扩展太慢，而且用户只要”从家到公司”一条路，不需要到全城每个路口的最短路。工程上常见的加速手段有：双向搜索（从家和公司同时跑，在中途相遇）、A* 启发式（用直线距离引导搜索方向，优先扩展”看起来离目标近”的顶点）、分层路网（先在高等级道路网络上规划，再细化到街区），以及预计算（对热门路段提前算好距离表）。但无论怎么加速，核心引擎仍然是”按累计代价从小到大扩展”这套 Dijkstra 思想，A* 甚至可以被看成”Dijkstra + 一个聪明的排队顺序”。

另一个工程细节是权重怎么定义。导航的”代价”几乎从来不是纯距离：红绿灯数量、限速、拥堵指数、收费、坡度，甚至天气，都会被揉进一个综合评分。今天早上高架堵了，权重变大，推荐路线可能瞬间变成地面道路——这就是为什么同样的起点和终点，不同时间打开地图会得到不同的”最短路径”。算法没变，变的是权重，而权重就是问题的灵魂。

8.2 网络路由：OSPF 与 Dijkstra 的百年好合

互联网路由协议里有一大类叫链路状态路由协议，最著名的就是 OSPF（Open Shortest Path First，开放最短路径优先）。它的工作流程大致是：每台路由器先通过”你好”报文发现邻居，然后把自己知道的所有链路信息（连了谁、代价多少）广播给全网，最终每台路由器都拥有一张完整一致的网络拓扑图。有了图，剩下的就交给 Dijkstra：每台路由器以自己为起点跑一遍 Dijkstra，得到一棵以自己为根的最短路径树（Shortest Path Tree），树上的每条边就是数据包应该走的方向。

下面是一张小型的 OSPF 网络拓扑。R1 是”自己”，R2、R3、R4、R5 是其他路由器，边上的数字是链路代价（可以理解为延迟或管理距离）：

graph LR
    R1["R1（本机）"] -- "2" --> R2["R2"]
    R1 -- "5" --> R3["R3"]
    R2 -- "1" --> R4["R4"]
    R3 -- "3" --> R4
    R2 -- "4" --> R5["R5"]
    R4 -- "2" --> R5

从 R1 出发跑 Dijkstra：R2 代价 2，R3 代价 5；R2 确定后 R4 变成 3，R5 变成 6；R3 确定后 R4 还是 3（5 + 3 = 8 更差）；R4 确定后 R5 变成 5（3 + 2 = 5，比 R2 直接过去便宜）；最终 R5 = 5，路径是 R1 → R2 → R4 → R5。如果 R2 → R4 的链路突然断了，拓扑变化会被广播，每台路由器重新跑一次 Dijkstra，新路径可能变成 R1 → R3 → R4 → R5。OSPF 的”收敛”过程，本质上就是全网重跑 Dijkstra 的过程。

有趣的是，真实路由器的链路代价并不一定等于物理距离或延迟，网络管理员可以手工配置：想让流量走光纤，就把光纤的代价配成 1，把卫星链路的代价配成 1000。权重是管理员的指挥棒，Dijkstra 只是忠实的执行者——这和导航软件里”权重是产品经理的指挥棒”如出一辙。

8.3 单词阶梯的加权变体

图系列第 4 篇讲过单词阶梯（word ladder）：给定一个起始单词和一个目标单词，每次只改变一个字母，求最少几步从起点变到目标。经典版本里，“换一个字母”的成本是 1，所以它是一道无权图 BFS 题：每个单词是一个顶点，两个单词只差一个字母就连一条边。

现在做一个加权变体：如果不同字母的”替换成本”不一样呢？比如把 ‘a’ 换成 ‘e’ 要 2 元，把 ‘e’ 换成 ‘i’ 要 3 元，把 ‘a’ 直接换成 ‘i’ 要 10 元——于是从 “cat” 到 “cit” 就有两条路：直接换 10 元，或者先换成 “cet” 再换成 “cit” 共 5 元。单词还是那些单词，图还是那张图，但边的权重不再全是 1，问题就从”最少几步”变成了”最小总成本”，BFS 正式下课，Dijkstra 上台：

graph LR
    CAT["cat"] -- "2" --> CET["cet"]
    CET -- "3" --> CIT["cit"]
    CAT -- "10" --> CIT

这个变体提醒我们一件重要的事：同样是”单词接龙”这道题，题目描述里一个词的变化就可能改变算法选择。见到”最少几步”想 BFS，见到”最小代价""每步成本不同""带权”想 Dijkstra，见到”可能出现负收益”想 Bellman-Ford——把题面翻译成图模型的能力，往往比背十个模板更值钱。

8.4 一句话通向 A*：在 Dijkstra 的队列里加一点”方向感”

Dijkstra 有个”缺点”：它从起点向四面八方均匀扩展，哪怕目标就在起点正东 100 米，它也会先扫完西边和北边所有更近的顶点。对追求”单点到单点”的导航场景，这太浪费了。A* 算法的改进只有一句话：不再按”已经花费的代价 g”排序，而是按”g + 启发式估计 h”排序，其中 h 是”从当前顶点到目标的估计代价”，比如欧几里得距离。有了 h 的牵引，搜索会优先朝目标方向扩展，常常只用 Dijkstra 的一小部分工作量就找到答案。

下面这个 iframe 就是我们的寻路算法可视化实验室，里面同时实现了 Dijkstra 和 A*，还有迷宫、权重地形、可拖动起点终点等玩法。强烈建议你亲手拖一拖：先看 Dijkstra 如何”以起点为圆心”均匀扩张，再切到 A* 看它如何”瞄准目标”直线突进；你还可以在网格上画出带权区域，观察带权图里”绕路”如何胜过”直行”。理论配动手，才是把算法变成直觉的最快路径：

玩的时候建议按这个顺序做三组实验。第一组：在空白网格上从左上角到右下角跑 Dijkstra，观察它的扩展形状像不像一个逐渐变大的圆；第二组：切换到 A*，同样的起点终点，观察扩展形状被”拉”向目标，访问的格子明显变少；第三组：在中间画一片高成本区域，让 Dijkstra 帮你找出一条”宁可绕远也避开高成本区”的路径——你看到的每一次拐弯，都是第 2 章”直达贵、绕路便宜”的活教材。

8.5 单源与全源：Dijkstra 只回答了一半问题

在收尾之前，把”最短路径”这个问题的版图再补完整一点，免得你误以为 Dijkstra 就是最短路径的全部。按”需要几个起点”来分，最短路径问题可以分成三大类：

第一类叫单源最短路径：给定一个起点 s，求 s 到所有顶点的最短距离。Dijkstra 和 Bellman-Ford 都属于这一类，本篇的主角就是它。

第二类叫多源最短路径：给定若干个起点，求”离任意一个起点最近”的结果。很多看似多源的问题（比如”求离任意一家便利店最近的小区”）可以通过一个巧妙的技巧化归为单源：加一个超级源点，用 0 权边连到所有真实起点，然后跑一次 Dijkstra。这个技巧在面试里出现频率极高，值得记在小本本上。

第三类叫全源最短路径：给定图里任意两个顶点，求它们之间的最短距离。最朴素的做法是把每个顶点都当一次单源起点，跑 V 次 Dijkstra，得到 O(V × (V+E) log V)；更经典的算法是 Floyd-Warshall，用动态规划在 O(V³) 内一口气算出所有顶点对的距离，代码只有三层循环十几行，特别适合顶点数不多（几百以内）的稠密图，比如求”社交网络里任意两人之间最少经过几个人”这类问题。

为什么要在这里提全源？因为它能帮你建立”算法选型”的大局观：问题问的是’一个点到所有点’、‘几个点到所有点’还是’所有点到所有点’，决定了你该掏出 Dijkstra、超级源技巧还是 Floyd。本篇先把单源的 Dijkstra 学扎实，多源技巧今天已经给了钥匙，全源留给图系列后面的篇章。现在你手里已经握着至少三把钥匙，遇到”最短路径”四个字时，先想清楚问题属于哪一类，再决定开哪扇门。

9 收尾：速查表、自测题与下一篇预告

在读速查表和自测题之前，先允许我把整篇文章浓缩成三句话，作为你合上文章前最后的记忆锚点。第一句：BFS 用”边数”当尺子，只在每步代价相同时正确；带权图要换”总权重”这把尺子，于是有了 Dijkstra。第二句：Dijkstra 的每一轮都只做一件事——从尚未定案的顶点里挑出已知距离最小的那个，宣布它定案，再把这份”好消息”通过松弛传给邻居；只要边权非负，这个贪心就永远安全。第三句：负权边不是小 bug，而是整个贪心证明的敌人，遇到它请绕道 Bellman-Ford。这三句话能秒答 80% 的”最短路径”概念题，剩下的细节，速查表会接住你。

9.1 Dijkstra 要点速查表

把本篇最重要的内容压缩进一张表。这张表适合复习时逐行自查，也适合面试前快速过一遍：

项目	内容
适用问题	单源最短路径，边权全部非负的带权图
核心思想	按累计代价从小到大逐顶点”定案”，每次定案后松弛其邻居
核心数据结构	dist 表 + prev 表 + done 标记；工程版用最小堆取”当前最小”
关键动作	松弛：若 dist[u] + w < dist[v]，则更新 dist[v] 并记录 prev[v] = u
贪心选择	每轮取”未确定集合里 dist 最小”的顶点，标记为已确定
为什么安全	边权非负时，任何绕路方案都需经过已知距离更大的顶点再加非负边权，无法反超
朴素实现	线性扫描取最小，O(V² + E)，适合稠密图
堆优化	最小堆 + 懒惰删除，O((V+E) log V)，适合稀疏大图
惰性删除	堆里旧条目不删，弹出时若 d ≠ dist[u] 或 done[u] 则丢弃
路径还原	从终点沿 prev 回溯到起点，再反转；并列最短路只保留一条
终止条件	未确定集合为空，或剩余顶点 dist 均为 ∞（不可达）
负权边	直接失效；允许负权无负环用 Bellman-Ford，有负环则问题无解
常见应用	导航路线、OSPF 路由、加权单词阶梯、游戏寻路（A* 的基础）

9.2 三个高频误区

送佛送到西，把初学者最容易踩的三个误区再钉一遍，每个都用一句话点破。

误区一：Dijkstra 每轮选的是”全图 dist 最小”。 不对，是”未确定顶点里 dist 最小”。起点定案后 dist 仍是 0，如果不跳过已确定顶点，每一轮都会选中它，算法当场死循环。

误区二：Dijkstra 求的是”边数最少”的路径。 不对，它求的是”总权重最小”。第 2 章那个 100 元直达 vs 2 元绕路的例子，就是给这个误区立的反面教材。

误区三：负权边只是”小问题”，改改比较条件就行。 改不了。负权边破坏的是贪心证明本身，不是某个 if 写错了。要么换 Bellman-Ford，要么确保题目保证非负，没有第三条捷径。

9.3 自测题

9.5 下一篇预告

这一篇我们完成了从 BFS 到 Dijkstra 的跃迁：用反例看清了”层数少不等于代价小”，用贪心直觉建立了”当前最小可定案”的安全感，用手算走完了一张 7 节点图，用两版代码实现了朴素与堆优化，还看穿了负权边为何致命。但 Dijkstra 的世界远未穷尽：它的严格正确性证明（数学归纳法）、prev 路径还原的工程细节、稠密图与稀疏图的复杂度权衡、Dial 桶优化、双向 Dijkstra、以及 Dijkstra 与 A* 的统一视角，都还没有展开。

下一篇《图系列第 9 篇：Dijkstra 深入》，我们就来把这些坑一个个填平：先给出严谨的证明框架，再聊聊工程实现里的边界情况（大数溢出、重复边、自环、孤立点），然后对比多种变体与优化，最后用几道经典题目把 Dijkstra 的应用手感练出来。等你读完第 9 篇，再回头看今天这篇，你会发现自己对”为什么敢贪心”的理解又上了一个台阶。

我们下一篇见。