目标

通过 26 道分层选择题，让学生辨析最短路径的以下核心点：

• 松弛主线：四个算法都是同一松弛操作在不同调度顺序下的产物（BFS 按层、Dijkstra 贪心选最小、Floyd 按中转点、Bellman-Ford 无差别迭代）；
• 核心性质与不变量：上界性、单调性、Dijkstra 的“确定即永久”、最短路径的最优子结构；
• 边界与反例：负权如何精准摧毁 Dijkstra、Floyd 对负权/负环的兼容与死穴、最短路径树的不唯一性；
• 复杂度与选型：稠密/稀疏、单源/全源、非负权/含负权时分别选哪个算法。

题目分三层：基础（★，认定义与性质）、进阶（★★，例图步骤模拟与对比混淆）、拔高（★★★，破坏不变量与选型推理）。

前置知识

建议先阅读 7.3 最短路径，理解 BFS / Dijkstra / Floyd-Warshall 的统一主线“松弛”，以及三个算法各自的适用条件。

作答方法

1. 阅读题面后点击一个选项，先写下选择依据；
2. 点击“提交答案”，再核对对错、正确答案和题解；
3. 做错的题点击“重新作答”后再次推导，直到能说明其余选项为什么不成立；
4. 完成全部题目后再使用页面末尾的答案总览复核。

选择题

答题进度已答 0/26正确 0

第 1 题

难度★考点Dijkstra、不变量、性质判断标识sp-001

在标准 Dijkstra（边权非负）中，关于“顶点一旦被选出并标记为已确定，其 dist 就永不反悔”这一不变量，下列描述正确的是？

请选择一个答案

A顶点 u 一旦被标记为已确定，其 dist[u] 就恒等于真实最短距离 d(u)，且后续松弛不会再改变它

B即使图中存在负权边，该不变量依然成立

Cdist[u] 确定后还可能被某个更小非负值覆盖

D该不变量依赖“每一次松弛都生效”才成立

第 2 题

难度★考点松弛、主线标识sp-002

最短路径算法的统一微观操作“松弛（relaxation）”指的是？

请选择一个答案

A把当前最短路径上所有边权相加

B用一条已知路径尝试压短某个距离估计：dist[v] = min(dist[v], dist[u] + w(u,v))

C从图中删除权值最大的边

D直接把 dist[v] 设为某条具体路径的长度

第 3 题

难度★考点BFS、Dijkstra、对比标识sp-003

常说“BFS 求无权最短路可视为 Dijkstra 的特例”，其依据是？

请选择一个答案

ABFS 用队列而 Dijkstra 用堆，实现不同

B当所有边权相等（如均为 1）时，按“距离”贪心等价于按“层数”扩展

CBFS 总比 Dijkstra 快

DDijkstra 不能处理无权图

第 4 题

难度★考点最优子结构、性质判断标识sp-004

关于最短路径的“最优子结构”性质，下列说法正确的是？

请选择一个答案

A最短路径上的任一子路径，也必是对应端点之间的最短路径

B最短路径必然唯一

C最短路径不可能经过任何中间顶点

D最优子结构只在边权非负时才成立

第 5 题

难度★考点Floyd、负权、负环标识sp-005

关于 Floyd 算法对边权的要求，下列正确的是？

请选择一个答案

A必须所有边权非负

B允许存在负权边，但不能包含总权为负的环

C既不能含负权边也不能含负环

D对负权与负环都完全兼容

第 6 题

难度★考点负环、性质判断标识sp-006

若从源点 s 能到达一个总权为负的环，并且从该负环又能到达顶点 v，则 d(s,v) 会怎样？

请选择一个答案

A一定是某个有限负数

B没有有限下界，可记为 −∞

C仍可由 Dijkstra 正确确定

D只要 s 不在负环上就不受影响

第 7 题

难度★考点Floyd、负环检测标识sp-007

用 Floyd 判断图中是否存在负环，应当检查什么？

请选择一个答案

A是否存在某条边权为负

B算法结束后是否出现某个 d(i,i) < 0

C是否存在 d(i,j) = ∞

D迭代轮数是否超过 n

第 8 题

难度★考点Dijkstra、复杂度、选型标识sp-008

对于边稠密的图（m ≈ n²），单源 Dijkstra 用“朴素数组实现”与“二叉堆实现”的时间复杂度分别约为？

请选择一个答案

AO(n²) 与 O((n+m)log n)，稠密时前者更优

BO(n log n) 与 O(n²)

C两者都是 O(n³)

DO(m log n) 与 O(n²)，堆实现更优

第 9 题

难度★考点Floyd、复杂度标识sp-009

Floyd-Warshall 求全源最短路的时间复杂度是？

请选择一个答案

AO(n²)

BO(n³)

CO(nm)

DO(nm log n)

第 10 题

难度★★考点Prim、Dijkstra、对比、贪心标识sp-010

Prim（最小生成树）与 Dijkstra 都基于“每步贪心选最小者”，二者的根本区别是？

请选择一个答案

APrim 维护已连通顶点集，每次选跨越该集合的最小权边；Dijkstra 维护距源点已确定最短距离的顶点集，每次选 dist 最小的顶点

B两者完全等价，只是目标表述不同

C两者都只能用于有向图

DPrim 需要边权非负，而 Dijkstra 允许负权

第 11 题

难度★★考点Dijkstra、步骤模拟、例图标识sp-011

在 03 文档例图（源点 A，边权见边表）上运行 Dijkstra。第 3 轮出队确定的顶点是？

请选择一个答案

AB

BC

CD

DE

第 12 题

难度★★考点Dijkstra、步骤模拟、例图标识sp-012

同例图（源点 A）运行 Dijkstra，算法结束时 dist[E] 的值是？

请选择一个答案

A9

B6

C5

D∞

第 13 题

难度★★考点BFS、Dijkstra、对比、例图标识sp-013

在例图上，把边权看作“跳数”（无权）时 BFS 求得的 A→F 距离，与 Dijkstra 加权最短路长度，分别是？

请选择一个答案

A1 跳 与 7

B4 跳 与 7

C1 跳 与 10

D7 跳 与 7

第 14 题

难度★★考点Floyd、步骤模拟、例图标识sp-014

在例图上运行 Floyd，最终矩阵中 d(B,F) 的值是？

请选择一个答案

A9

B6

C10

D∞

第 15 题

难度★★考点Floyd、步骤模拟、例图标识sp-015

同例图 Floyd 最终矩阵中 d(C,F) 的值是？

请选择一个答案

A4

B5

C7

D8

第 16 题

难度★★考点Dijkstra、正确性证明、非负权标识sp-016

在 Dijkstra 正确性的反证法（“第一个错误顶点”）中，“边权非负”这一前提唯一在哪一步被使用？

请选择一个答案

A初始化 dist[s] = 0

B证明“路径前缀的长度不超过整条最短路的全长”（即 y→u 尾段权非负）

C选择当前 dist 最小的未确定顶点

D把 u 标记为已确定

第 17 题

难度★★考点Floyd、循环顺序、反例标识sp-017

把 Floyd 三重循环写成 for i for j for k（k 在最内层），对图 A→B(1)、B→D(1)、D→C(1)（正确 d(A,C)=3）会得到错误结果。其根本原因是？

请选择一个答案

A递推式写反了

B处理 (A,C) 时所需的中间值 d(A,D) 尚未就绪（D 在本轮作为 j 排在 C 之后）

Ck 必须在最内层才能正确

D该图含负环

第 18 题

难度★★考点Dijkstra、负权、反例标识sp-018

三点图 A→B(1)、A→C(2)、C→B(−2)，真实 d(A,B)=0（走 A→C→B）。Dijkstra 会输出 dist[B] = ？

请选择一个答案

A0

B1

C−2

D∞

第 19 题

难度★★考点松弛、调度顺序、对比标识sp-019

关于 BFS、Dijkstra、Floyd、Bellman-Ford 的“松弛顺序”，下列配对正确的是？

请选择一个答案

ABFS：按中转点松弛；Floyd：按层松弛

BBFS：按层松弛；Dijkstra：按当前 dist 最小顶点松弛；Floyd：按中转点松弛

CDijkstra：按层松弛；BFS：按 dist 最小顶点松弛

DFloyd：无差别全边松弛 n−1 轮

第 20 题

难度★★考点最短路径树、性质判断标识sp-020

关于从源点出发的“最短路径树”（由各点的最短路径前驱构成），下列说法正确的是？

请选择一个答案

A对任何图都唯一

B不一定唯一：当存在多条等长最短路时，树的结构可能不同

C一定包含图中所有顶点

D与最小生成树是同一棵树

第 21 题

难度★★★考点Dijkstra、不变量、边界标识sp-021

在正权图的堆优化 Dijkstra 中，去掉 done 数组，允许同一顶点因距离下降而多次入堆；弹出记录后仍按“只有更短才更新”的规则松弛。此时结果如何？

请选择一个答案

A结果仍然正确，但若不跳过过期堆记录，可能做额外工作

B一定错误，因为没有 done 就无法保证最短距离

C只有稠密图上的结果正确

D算法会自动变成 Bellman-Ford

第 22 题

难度★★★考点Floyd、Dijkstra、选型、复杂度标识sp-022

给定 n 个顶点的稠密带权图（m ≈ n²）、边权非负，要一次性求出所有点对最短路，下列哪种最合适？

请选择一个答案

A跑 n 次堆优化 Dijkstra，复杂度约 O(n³ log n)

B直接 Floyd-Warshall，复杂度 O(n³)，比 A 更优

C跑 n 次 Bellman-Ford

D对每个源点跑 BFS

第 23 题

难度★★★考点Bellman-Ford、Dijkstra、负权、选型标识sp-023

若图中允许负权边但保证无负环，求单源最短路应选用？

请选择一个答案

ADijkstra

BBellman-Ford（或 SPFA）

CFloyd

DBFS

第 24 题

难度★★★考点Floyd、空间优化、负环标识sp-024

Floyd 能把三维状态 d(k,i,j) 优化为二维数组 d(i,j)（原地更新），其安全性依赖什么？

请选择一个答案

Ak 必须在最外层循环

B无负环时，第 k 轮不会修改第 k 行与第 k 列（即 d(k,k)=0，经 k 绕回 k 不会更短）

C图必须无向

D边权必须非负

第 25 题

难度★考点松弛、不变量、性质判断标识sp-025

松弛操作带来的“上界性”不变量是指：算法运行过程中，任意时刻都有？

请选择一个答案

Adist[v] ≤ d(v)（估计可能低估真实最短路）

Bdist[v] ≥ d(v)（估计永不低估真实最短路）

Cdist[v] = d(v)（估计始终精确）

Ddist[v] 只可能增大

第 26 题

难度★★考点Dijkstra、步骤模拟、例图标识sp-026

同例图（源点 A）运行 Dijkstra，dist[D] 在第 2 轮经 B 被设为 4，后来 C 也提供一条 A→C→D（权 4+1=5）的路。Dijkstra 结束时 dist[D] 为？

请选择一个答案

A4

B5

C3

D6

答案总览（建议完成全部题目后查看）

1. 第 1 题：A
2. 第 2 题：B
3. 第 3 题：B
4. 第 4 题：A
5. 第 5 题：B
6. 第 6 题：B
7. 第 7 题：B
8. 第 8 题：A
9. 第 9 题：B
10. 第 10 题：A
11. 第 11 题：B
12. 第 12 题：B
13. 第 13 题：A
14. 第 14 题：B
15. 第 15 题：A
16. 第 16 题：B
17. 第 17 题：B
18. 第 18 题：B
19. 第 19 题：B
20. 第 20 题：B
21. 第 21 题：A
22. 第 22 题：B
23. 第 23 题：B
24. 第 24 题：B
25. 第 25 题：B
26. 第 26 题：A

完成清单

• 所有题目均在提交答案前独立作答；
• 每道错题都记录了错误原因，而不只抄写正确答案；
• 能说明至少两道题的完整推理过程；
• 复做错题时能够在不看解析的情况下得到正确结论。

思考题

下列题目没有唯一标准答案，目的是把“松弛”主线从“会做题”推进到“能设计”。建议先独立写一段思路，再展开参考答案。

1. 松弛顺序的统一框架：调度策略即算法

四个算法被我们统一描述为“同一松弛操作在不同调度顺序下的产物”。试着抽象出一个框架：给定一种“决定下一条放松哪条边 / 哪个顶点”的调度策略，是否就唯一确定了一个最短路径算法？除了调度，还必须规定哪些状态、更新和终止规则？例如，标准 Dijkstra 的 done 版本与不使用 done、允许堆中出现重复记录的懒惰版本，为什么都能在非负权图上得到正确结果？

参考思路

调度策略只是算法的一部分；完整算法还要规定距离估计的含义、松弛条件、过期记录如何处理、顶点能否重新入队以及何时终止。

• BFS：调度由“入队先后（层）”决定，恰好匹配单位权场景；
• Dijkstra：调度用“当前 dist 最小”，需要非负权来保证首次取出的最小距离已经是最终答案；
• Floyd：调度用“第 k 个中转点”，把选择外包给 DP 维度，因此不依赖贪心、能兼容负权；
• Bellman-Ford：所有边迭代松弛至多 n−1 轮，用轮次覆盖所有无环最短路径，并可额外检测负环。

标准 Dijkstra 可以用 done 标记已确定顶点；懒惰堆版本也可以不设 done，在弹出记录时用 du != dist[u] 跳过过期项。即使重复处理过期项，只要松弛始终取更小值，过大的旧估计也不会破坏答案，只会增加工作量。两种实现的正确性都来自“非负权 + 每次选择当前最小距离”，而不是来自 done 数组本身。

一旦允许负权，首次取出的最小距离便未必永久正确；这时必须改用 Bellman-Ford 等允许有效重新传播、并有明确收敛或轮次规则的算法。由此可见：调度顺序不会单独唯一确定算法，正确性来自调度、状态更新和终止条件的共同约束。

2. 负权到底破坏了哪一条不变量

Dijkstra 在负权下失效，BFS（边权恒为 1）却天然与负权绝缘。请从“松弛带来的三条不变量”——上界性、单调性、确定即永久——中精确指出：负权打破的是哪一条？为什么打破这一条就足以让算法给出错误答案，而另外两条在负权下其实仍然成立？

参考思路

负权打破的是“确定即永久”（以及与之绑定的“dist[u] 出队时等于 d(u)”）。

• 上界性（dist[v] ≥ d(v)）在负权下依然成立：松弛只用真实路径压低估计，估计永远不小于真值。
• 单调性（dist[v] 只减不增）在负权下也依然成立：松弛取 min，方向不变。
• 但“确定即永久”依赖一个隐藏前提：当 u 是当前 dist 最小的未确定顶点时，没有“更短但尚未被发现”的路径。这个前提来自“所有边权非负”——正是 sp-016 证明里唯一用到非负权的那一步（前缀 ≤ 全长）。负边使得“一个已确定的顶点，其真实最短路可能还要先经过某个 dist 更大的顶点”，于是“先出队 = 先确定”的贪心序被颠覆。

BFS 之所以不受影响，是因为它的等价场景是“所有边权 = 1”，仍是非负、只是退化成单位权——并没有引入负权，所以“确定即永久”在 BFS 里同样成立（层数序 = 距离序）。

一句话：负权没有破坏“估计的上下界”，它破坏的是“贪心选最小”这件事的正当性。

3. 为什么 Floyd 能兼容负权，而 Dijkstra 不能

Dijkstra 与 Floyd 都用于最短路径，但适用边权不同：Floyd 能处理负权边（前提是不存在负环），Dijkstra 则要求边权非负。请用本页的“松弛调度”视角解释这种差异，并指出它们各自的正确性靠什么保证。

参考思路

根本差异：Dijkstra 的正确性靠“贪心序”，Floyd 的正确性靠“DP 穷举”，二者对负权的敏感度天然不同。

• Dijkstra 每步断言“当前 dist 最小的顶点已确定”，这一步的合法性来自非负权（见思考题 2）。负权让这个断言失效，所以 Dijkstra 怕负权。
• Floyd 的更新 d(i,j) = min(d(i,j), d(i,k)+d(k,j)) 本身只是一个恒等式——只要“经 k 中转是否更短”这个比较成立，它就在正确工作，完全不要求边权符号。它的正确性由“k 在最外层、穷举所有中转点”这一 DP 结构保证，而不是由任何“当前最小者已确定”的贪心断言保证。因此负边只是带来更短的合法路径，Floyd 照常捕捉。

但要注意：Floyd 也怕负环，只是怕的方式不同——负环让 d(i,i) 持续下降、最短路无定义，Floyd 用对角线 d(i,i)<0 来“报告”而非“解决”。所以更精确地说：

Dijkstra 与 Floyd 的分野不是“负权 vs 非负权”，而是“贪心正确性 vs 穷举正确性”。负权只杀死依赖贪心的那一个。

4.（拔高）工程上的全源最短路：当 n 很大时

假设一张 10⁵ 个顶点、边数约 2×10⁵（稀疏）、边权非负、且需要反复回答“任意两点间最短路”的图。理论上：

• Floyd 是 O(n³)，在此规模完全不可行；
• 跑 n 次 Dijkstra 是 O(n·m log n) ≈ 2×10¹⁰·log，同样不可行。

这时通常不会显式保存完整的 n×n 距离矩阵，而会怎样利用路网结构，在“预处理成本、单次查询时间、空间和精确性”之间取舍？提示：现实路网具有明显的层级性和地理结构。

参考思路

这是开放题，没有唯一答案。几条现实路线供参考：

1. 按需精确查询 + 路网索引：收缩层次（Contraction Hierarchies）等方法通过预处理路网层级，大幅缩小每次查询要搜索的范围；标准 CH 仍返回精确最短路，并不天然是近似算法。
2. Landmark / ALT：预计算少量地标距离，用三角不等式构造 A* 的可采纳启发函数。只要启发函数不高估剩余距离，ALT 仍能得到精确答案。
3. A 与近似变体*：基于可靠下界的标准 A* 可以精确求解；只有主动使用不可采纳启发式、Weighted A* 等策略时，才是在用可控误差换速度。
4. 缓存热门查询：若业务只反复查询少量起终点对，可缓存精确结果，而不必物化全部点对。

落脚点：课本里的 O(n³) / O(n·m log n) 是理论最坏情况；工程上要利用稀疏、层级、地理下界和查询分布来选算法，同时明确所选方案是否保留精确性。

复盘

• 我最容易在哪个前提上出错：算法性质、边界条件，还是选型/复杂度？
• 哪道题的干扰项最容易混淆？它利用了哪个常见误区？

查看参考答案

先把错误归因到具体前提：BFS 需要单位权，Dijkstra 需要非负权，Floyd 需要 k 外层且题目通常排除负环；再单独检查不可达、负环和整数溢出边界。最常见混淆是把“最短路径树”当成 MST，或把负权边与负环混为一谈。