🏷️ 知识点：Dijkstra算法
对如下有向图带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短路径，则得到的第一条最短路径的目标顶点是 b，第二条最短路径的目标顶点是 c，后续得到的其余最短路径的目标顶点依次是（ ）。
A. d, e, f
B. e, d, f
C. f, d, e
D. f, e, d
[tag_link]
正确答案：C
从 a 到各顶点的最短路径的求解过程：
| 顶点 | 第 1 趟 | 第 2 趟 | 第 3 趟 | 第 4 趟 | 第 5 趟 |
|---|---|---|---|---|---|
| b | (a,b)2 | ||||
| c | (a,c)5 | (a,b,c)3 | |||
| d | ∞ | (a,b,d)5 | (a,b,d)5 | (a,b,d)5 | |
| e | ∞ | ∞ | (a,b,c,e)7 | (a,b,c,e)7 | (a,b,d,e)6 |
| f | ∞ | ∞ | (a,b,c,f)4 | ||
| 集合 S | {a,b} | {a,b,c} | {a,b,c,f} | {a,b,c,f,d} | {a,b,c,f,d,e} |
后续目标顶点依次为 f,d,e。第三轮已有 dist(f)=4<dist(d)=5<dist(e)=7，先固定 f；随后固定 d，并把 e 更新为路径 a→b→d→e、长度 6；最后固定 e。因此选 C。
使用迪杰斯特拉（Dijkstra）算法求下图中从顶点 1 到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是（ ）。
A. 5, 2, 3, 4, 6 B. 5, 2, 3, 6, 4 C. 5, 2, 4, 3, 6 D. 5, 2, 6, 3, 4
[tag_link]
正确答案：B
根据 Dijkstra 算法，从顶点 1 到其余各顶点的最短路径如下表所示。
| 顶点 | 第 1 趟 | 第 2 趟 | 第 3 趟 | 第 4 趟 | 第 5 趟 |
|---|---|---|---|---|---|
| 2 | 5v1→v2 | 5v1→v2 | |||
| 3 | ∞ | ∞ | 7v1→v2→v3 | ||
| 4 | ∞ | 11v1→v5→v4 | 11v1→v5→v4 | 11 v1→v5→v4 | 11v1→v5→v4 |
| 5 | 4v1→v5 | ||||
| 6 | ∞ | 9v1→v5→v6 | 9v1→v5→v6 | 9v1→v5→v6 | |
| 集合 S | {1, 5} | {1, 5, 2} | {1, 5, 2, 3} | {1, 5, 2, 3, 6} | {1, 5, 2, 3, 6, 4} |
顶点 1 到其余顶点的最终最短距离分别为 d(5)=4、d(2)=5、d(3)=7、d(6)=9、d(4)=11。Dijkstra 每轮固定当前暂定距离最小的未确定顶点，因此顺序为 5,2,3,6,4，选 B。
下列关于图的最短路径的叙述中，正确的是（ ）。
A. 最短路径一定是简单路径 B. Dijkstra 算法不适合求有回路的带权图的最短路径 C. Dijkstra 算法不适合求任意两个顶点的最短路径 D. Dijkstra 算法可以正确处理含有负权边的图
[tag_link]
正确答案：A
结论
选 A。
推导
在不存在负权回路的通常最短路定义下，若一条路径重复顶点，就含有回路；去掉该回路不会增加长度，因此存在一条同样不长于它的简单最短路径。Dijkstra 可处理有回路图，也可从每个源点重复运行求任意点对最短路，但要求边权非负，故 B、C、D 均错误。
易错点
Dijkstra 的限制是“不能有负权边”，不是“不能有回路”。
下列关于图的最短路径的叙述中，正确的是（ ）。
Ⅰ．Dijkstra 算法求单源最短路径不允许边的权为负。
Ⅱ．Dijkstra 算法求每对顶点间的最短路径的时间复杂度为 O(n²)。
Ⅲ．Floyd 算法求每对顶点间的最短路径允许边权为负，但不允许含有负权回路。
A. Ⅰ、Ⅱ和Ⅲ B. 仅Ⅰ C. Ⅰ和Ⅲ D. Ⅱ和Ⅲ
[tag_link]
正确答案：C
结论
选 C。
推导
Ⅰ正确：Dijkstra 的贪心确定性要求边权非负。Ⅱ错误：对 n 个源点分别运行 Dijkstra（朴素实现）为 O(n³)，不是 O(n²)。Ⅲ正确：Floyd 可处理负边，但负权回路使最短路无定义。
易错点
要区分“单源”与“每对顶点”；算法调用次数会改变复杂度。
已知带权连通无向图 G=(V,E)，其中
V={v₁,v₂,v₃,v₄,v₅,v₆,v₇}，
E={(v₁,v₂,10),(v₁,v₃,2),(v₃,v₄,2),(v₃,v₆,11),(v₂,v₅,1),(v₄,v₅,4),(v₄,v₆,6),(v₅,v₇,7),(v₆,v₇,3)}。
括号外的数表示边权。从源点 v₁ 到顶点 v₇ 的最短路径上经过的顶点序列是（ ）。
A. v₁,v₂,v₅,v₇
B. v₁,v₃,v₄,v₆,v₇
C. v₁,v₃,v₄,v₅,v₇
D. v₁,v₂,v₅,v₄,v₆,v₇
[tag_link]
正确答案：B
结论
选 B，路径长度为 2+2+6+3=13。
推导
候选路径长度分别为 A=10+1+7=18、B=13、C=2+2+4+7=15、D=10+1+4+6+3=24。因此最短路径为 v₁→v₃→v₄→v₆→v₇。
易错点
必须把边权累加并比较总长度，不能按边数或局部最小边选择。
用 Dijkstra 算法求带权有向图从顶点 0 出发的最短路径。在算法执行的某时刻，已求得最短路径的顶点集合 S={0,2,3,4}，下一步选取的目标顶点是 1，则可能被修改的最短路径是（ ）。
A. 从顶点 0 到顶点 3 的最短路径 B. 从顶点 0 到顶点 2 的最短路径 C. 从顶点 2 到顶点 4 的最短路径 D. 从顶点 0 到顶点 1 的最短路径
[tag_link]
正确答案：D
结论
选 D。
推导
集合 S 中顶点的源点最短距离已经确定，之后的松弛只会检查从新确定的顶点到 V−S 的边。因此不可能改变 0→3、0→2 或 2→4 这类已确定路径；只能把尚未确定的 0→1 的暂定距离更新为更短值（权威表述为“只能修改从源点 0 到集合 V−S 中顶点的路径”）。
易错点
“选出顶点 1”表示其路径被最终确定；被松弛修改的是选出前的暂定值，不能回改已加入 S 的顶点。
一连通无向图，边非负权值，问用 Dijkstra 最短路径算法能否给出一棵生成树，该树是 否一定是最小生成树?说明理由。
[tag_link]
参考答案
Dijkstra 算法能给出一棵以源点为根的最短路径树，但这棵树不一定是最小生成树。
原因是两种贪心目标不同：Dijkstra 每次固定“从源点到某顶点的当前最短距离”，而 Prim 每次选择“已入树顶点集合到树外的最轻边”。前者优化每个顶点到源点的路径，后者优化整棵树的边权总和。
反例：无向图有边 a-b=5、a-c=5、a-d=5、b-d=1、c-d=1。从 a 出发执行 Dijkstra，在三个距离同为 5 的顶点中先固定 d 时，a-b 和 a-c 仍分别比绕经 d 的距离 6 更短，因此可得到边集 {a-b,a-c,a-d}，总权值为 15。最小生成树则可取 {a-d,b-d,c-d}，总权值为 7。
所以“能生成树”正确，“一定是最小生成树”错误。