CSCI3160 L13 Dijkstra最短路径与松弛

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L13 Dijkstra最短路径与松弛 · 原件 L13-Graph-03-Dijkstra-未核-隐藏.pdf（本地课件） p.1–21 定位：在非负边权下，每次确定当前最近的未处理顶点。

p.1–3：边权非负是算法条件【新】

p.1 为标题；p.2 从单源最短路径 SSSP 开始。p.3 输入是有向简单图和非负整数边权。方向决定能否走，权重决定走的代价；不能把图画成无向图来计算。

p.3 “non-negative integer value”

p.4–6：距离是路径权重之和

图（p.4）：9 个顶点的带权有向图。元素：完整边表为 a→b:1、b→c:1、c→d:2、c→e:10、d→a:6、d→g:1、e→d:5、f→e:1、g→f:2、g→i:1、h→d:3、h→g:1、i→f:2。看什么：e→d 的方向与 d→e 不同，h 有向外的边却没有从 c 到它的路径。

p.5 把路径长度定义为边权和，不可达距离为 $\infty$ 。p.6 要求对每个可达点给出最短路。所谓最短路径树应理解为源点可达部分上的树；原文同时说顶点集为 V，但例中 h 不可达，不能硬造 c 到 h 的树路径。实现可保留 h 的空父指针，并单独报告不可达。

p.7–9：松弛只做一次局部改善

p.8 “the shortest path length from s to v found so far”

距离表存目前找到的最好路径，不是算法一开始就知道的真实距离。松弛 (u,v) 比较 $dist(v)$ 与 $dist(u)+w(u,v)$ ，后者小才更新，并把 parent(v) 改成 u。初始化源点0、其他无穷、父指针空。p.9 每次从未处理集合 S 中取距离最小者，再松弛它的所有出边。

图（p.7）：源点 c 的最终树。元素：c→d，d 分向 g、a，g 分向 f、i，f→e，a→b。看什么：树上距离最短不代表整棵树总权最小；这是 SSSP，不是 MST。

p.9 全算法如下，保留原课件的未处理集合 S 语义：

对每个 v：parent[v]=空；dist[v]=无穷
令 dist[s]=0，S=全部顶点
当 S 非空：
  从 S 中删除 dist 最小的 u
  对 u 的每条出边 (u,v)：
    若 dist[u]+w(u,v) < dist[v]：
      dist[v]=dist[u]+w(u,v)
      parent[v]=u
最后对每个非空 parent[v]，把 v 接为 parent[v] 的孩子

使用无穷哨兵的实现应跳过不可达 u 的加法。这里 S 是“未取出的点”，与 Prim 中 S 表示“已加入的点”恰好不同，应按本讲定义理解。

p.10–12：从无穷表开始

p.10 只有 c=0。p.11 取 c，令 d=2、e=10，父亲均为 c。p.12 取 d=2，经 d→a 得 a=8，经 d→g 得 g=3。此时 e 虽已经发现，距离10仍可能改善；“已发现”和“已取出确定”不是同一状态。

p.13–15：选择最小候选，再改写旧候选

p.13 取 g=3，得到 f=5、i=4；p.14 取 i=4，经 i→f 的候选为6，比已有5差，所以不更新。p.15 取 f=5，把 e 从10降到6，parent(e) 也必须从 c 改成 f。少改父指针会得到与最终距离不一致的路径。

p.16–18：没有改善也是完整的一步

p.16 取 e=6，经 e→d 的候选为11，不改善 d=2。p.17 取 a=8，令 b=9。p.18 取 b=9，经 b→c 的候选10，不改善 c=0。所有这些检查都有意义：算法并非只列出改变数字的边。

原页 p.10–18 的每个距离表可合成如下逐轮表；各列顺序固定，未变的值也保留，便于独立复算：

页／处理后	a	b	d	e	f	g	h	i
p.10 初始	∞	∞	∞	∞	∞	∞	∞	∞
p.11 c	∞	∞	2	10	∞	∞	∞	∞
p.12 d	8	∞	2	10	∞	3	∞	∞
p.13 g	8	∞	2	10	5	3	∞	4
p.14 i	8	∞	2	10	5	3	∞	4
p.15 f	8	∞	2	6	5	3	∞	4
p.16 e	8	∞	2	6	5	3	∞	4
p.17 a	8	9	2	6	5	3	∞	4
p.18 b	8	9	2	6	5	3	∞	4

每次距离首次从无穷变有限或严格降低时才更换父亲，未变化时父亲也保持；因此初始全空，依次新增 d←c、e←c、a←d、g←d、f←g、i←g，然后把 e←c 改为 e←f，最后新增 b←a。这完整复现了原页的 parent 列。

p.19–21：结果、恢复路径和实现代价

p.19 最后剩 h，其距离无穷，无法改善任何点。p.20 由最终 parent 生成可达部分的树。完整结果为：

顶点	a	b	c	d	e	f	g	h	i
距离	8	9	0	2	6	5	3	∞	4
父亲	d	a	空	c	f	g	d	空	g

例如从 e 倒追 f,g,d,c，反向得到 c→d→g→f→e，权重2+1+2+1=6。取出顺序是 c,d,g,i,f,e,a,b,h。

p.21 “Dijkstra’s algorithm does not work if edges can take negative weights.”

二叉堆实现用 $O((V+E)\log V)$ 时间；邻接表逐边松弛，堆支持取最小和降键。讲义提到更高级数据结构可到 $O(V\log V+E)$ ，此处不把它当普通二叉堆的复杂度。

补充／为什么能确定最小者。 假设已确定点都正确，取出的 u 若仍不是最短，沿其真正最短路找第一个未确定点 y，其前驱已确定，所以松弛已使 y 的候选不大于该最短路到 y 的长度。后续边非负，y 不会比 u 的真正距离更远；这与 u 是候选最小却高估真实距离矛盾。负边会破坏“后续不会降低长度”这一步。数字是我为演示取的，讲义没给：s→a 为2、s→b 为5、b→a 为−4，先确定 a=2 会错过真实距离1。

补充：距离表中的有限值始终是一条真实走法的长度。 初始只有源点的空路径长度为 0；每次从已有走法延长一条边得到候选，因此 dist 只能高估或等于真实最短距离，不能凭空更小。贪心证明再说明取最小候选的那个点不会高估，于是两边夹成等号。单独说“取最近点所以正确”漏掉了这两种不同的保证。

实现中要区分未发现、堆内有候选、已确定三个阶段。使用不支持 decrease-key 的堆时，可在改善后插入新 (距离,顶点)，旧记录暂留；出堆时若距离不等于当前 dist 就跳过，不能把过时记录当第二次确定。空间和时间需按可能插入的边数分析，不能将这种实现无条件写成只含 V 个堆元素的版本。

自测：何时能提前停止到目标 t 的查询？

在 t 以当前最小有效候选被取出并确定时。刚通过一条边发现 t 还不行，原例 e 最初为 10，后来降为 6。若最小候选已经是无穷，剩下的点均不可达，可以停止；程序里应先判断无穷，避免整数哨兵加边权发生溢出。

本讲核心考点

（C 级通识）逐次写取出顶点、松弛比较和 parent 更新。
（C 级通识）非负条件用在贪心正确性的哪一步。
（C 级通识）区分最短路径树与最小生成树。

附录

本讲所需过程已在正文展开。

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L13-Graph-03-Dijkstra-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。