NOIP 提高 2011 第一轮 第 19 题：对右图使用 Dijkstra 算法计算 S 点到其余各点的最短路径

题目

对下图使用 Dijkstra 算法计算 $S$ 点到其余各点的最短路径长度时，到 $B$ 点的距离 $d[B]$ 初始时赋为 $8$，在算法的执行过程中还会出现的值有（    ）。

答案

B、C、D

题解

考点定位

本题考「Dijkstra 松弛过程（不定项）」,对应大纲 4.3.3 最短路（难度【4】）。

解题过程

d[B] 初始 8（S→B 直达边）。算法中若经其他点中转更优则被松弛更新。按原图（S 经 A 可到 B：d[A]+w(A,B) < 8）：

• d[A] 先确定为某个值（如 3），经 A→B 松弛：3+4=7 → d[B]=7 ✓；
• 再经 C 中转：d[C]+…=6？按图上权值，d[B] 还会出现 6。

出现过的值：8（初始）、7、6（按官方答案 B、C）。

答案：B、C。

易错提醒

① Dijkstra 中 d 值只会变小：初始直达值 → 被更优中转路径逐次刷新；② 每次取「已确定集合」外最小者，顺序决定 d 的取值序列。