NOIP 提高组初赛 · NOIP 2011 提高组初赛试题 第 19 题

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

拿到题先圈出起点S和终点B，盯着所有与B相连的边看。Dijkstra里d[B]初始是8，后面能不能变小，全看有没有更短的‘绕路’——比如S→A→B这种两步走，或者S→C→B这种。把每条能到B的路径长度算出来，跟8比，比得小的才会出现在算法过程中。

最容易栽跟头的是把'最终答案'当成'过程中出现的值'。比如S→A→B算出来是7，S→C→B算出来是6，S→D→B算出来是5，这三个数确实会在松弛步骤里更新d[B]，但S→A→C→B这条绕远的路径算出来是3，它比当前d[B]还小，可Dijkstra一旦把某个点标记为'已确定最短'就不会再回头改它，而且3这条路径里中间点C的d值还没更新到能支持它，所以3根本不可能出现在d[B]的变化序列里。还有同学会以为初始d[B]=8也算'过程中'，其实初始赋值不算松弛，题目问的是'执行过程中还会出现的值'，所以8不算。

考点与概念

这题考的是Dijkstra算法的松弛过程，核心在于理解：d[v]表示从源点S到v的当前已知最短距离，初始时只有直接边能更新d值，后续通过其他点中转可能让d值变小。关键要分清“初始赋值”和“松弛更新”的区别，以及算法一旦确定某点最短距离就不会再回头改。

命题视角

命题人爱挖的坑就是让你分不清“最终答案”和“过程中出现的中间值”。比如S→A→B算出来是7，S→C→B算出来是6，S→D→B算出来是5，这三个数确实会在松弛步骤里更新d[B]，但S→A→C→B这条绕远的路径算出来是3，它比当前d[B]还小，可Dijkstra一旦把某个点标记为'已确定最短'就不会再回头改它，而且3这条路径里中间点C的d值还没更新到能支持它，所以3根本不可能出现在d[B]的变化序列里。还有同学会以为初始d[B]=8也算'过程中'，其实初始赋值不算松弛，题目问的是'执行过程中还会出现的值'，所以8不算。

思考心法

拿到题先圈出起点S和终点B，盯着所有与B相连的边看。Dijkstra里d[B]初始是8，后面能不能变小，全看有没有更短的‘绕路’——比如S→A→B这种两步走，或者S→C→B这种。把每条能到B的路径长度算出来，跟8比，比得小的才会出现在算法过程中。具体步骤：

1. 列出所有从S出发能到B的路径： - S→B（直达）：8 - S→A→B：5+2=7 - S→C→B：4+2=6 - S→D→B：3+2=5 - S→A→C→B：5+1+2=8（比当前d[B]=8没优势，不会触发更新） - S→A→D→B：5+1+2=8（同上） - S→C→D→B：4+1+2=7（比当前d[B]=8小，但此时d[C]还没更新到4，所以这条路径在算法里不可能先出现）

2. 按Dijkstra顺序模拟松弛： - 初始d[B]=8 - 先更新S→A，d[A]=5 - 再用d[A]更新B：d[B]=min(8,5+2)=7 → 出现7 - 更新S→C，d[C]=4 - 再用d[C]更新B：d[B]=min(7,4+2)=6 → 出现6 - 更新S→D，d[D]=3 - 再用d[D]更新B：d[B]=min(6,3+2)=5 → 出现5

3. 验证其他路径： - S→A→C→B：虽然总长8，但此时d[C]已经是4，所以不会触发d[B]更新 - S→C→D→B：总长7，但d[D]是3，所以也不会触发

避坑提醒

• 别把3当成可能值：S→A→C→B这条路径虽然总长3，但算法里d[C]在d[A]之后才更新，而d[B]在d[C]更新前已经被拉到了7，所以3这条路径不可能在d[B]还没到7的时候先出现。也就是说，3根本不会出现在d[B]的变化序列里。
• 别把8当成‘过程中出现的值’：题目明确问的是‘还会出现的值’，初始赋值不算松弛，所以8不算。

考频与趋势

最短路径是NOIP和CSP的常客，题库共考过35题，覆盖7个考试级别（2008-2026）。逐年分布：2008年2题、2011年1题、2012年1题、2013年1题、2014年1题、2015年2题、2016年1题、2018年1题、2019年1题、2020年1题、2021年1题、2024年6题、2025年7题、2026年7题。分赛事：GESP八级17题、NOIP提高组初赛9题、CSP提高级5题、GESP六级1题、NOIP普及组初赛1题、GESP五级1题、GESP七级1题。

从数据看，2024-2026连续三年考得密集（6+7+7=20题），说明命题人正把最短路径作为高频考点反复打磨。未来可能继续以单选形式考查算法执行过程中的中间值，或者结合多源最短路径、路径计数等变体出现。

预测

暂无足够依据预测具体题型变化，但基于近年趋势，未来仍大概率会考Dijkstra松弛过程中的中间值判断，尤其要区分‘最终答案’和‘过程中出现的值’。

结论

d[B]在算法执行过程中还会出现的值是7、6、5，对应选项B、C、D。