CSP-S 提高级 · CSP 2021 提高级第一轮 第 15 题

有如下的有向图，节点为 $A ,B , \cdots , J$, 其中每条边的长度都标在图中。则节点 $A$ 到节点 $J$ 的最短路径长度为（ ）。 

这题本质是手算 Dijkstra。别盯着 A 出发的边，先标出 A 到各点当前最短距离，每次把距离最小的那个点圈起来，再用它的出边去松弛邻居，直到圈到 J 为止。

最容易栽跟头的是把有向图当无向图看，比如看到 A→D 就以为能 D→A，结果绕出一堆废路径。其次是贪心直觉太强，只盯着离 A 最近的点跑，忘了可能得先绕远一点才能换来后面更短的总长。还有人喜欢用 DFS 暴力枚举所有路径，在节点多时不仅算得慢，还容易漏掉更优解。

考点与概念

本题考查最短路径问题，核心算法是Dijkstra。它适用于所有边权非负的图，思想非常朴素：每次从“还没确定最短距离的点”里挑一个距离最小的，把它的最短距离固定下来，然后用它的出边去更新（松弛）它的邻居。只要边权都是正的，这个贪心策略就永远正确。

命题视角

命题人喜欢在有向图上挖坑，一是边有方向，二是边权大小不一，容易诱使学生凭直觉选“看起来最近”的路。本题图节点较多，若不按 Dijkstra 的步骤来，很容易漏掉绕路反而更短的分支。

思考心法与计算过程

拿到题先别急着选边，按步骤来： 1. 初始化：A 的距离为 0，其余点记作无穷大。 2. 第一轮：只有 A 的距离是 0，把 A 圈定。看 A 的出边：A→B(10)、A→C(8)、A→D(4)。更新后：B=10，C=8，D=4。 3. 第二轮：未圈定的点里最小的是 D(4)，圈定 D。D 的出边：D→E(5)、D→G(6)。更新：E=4+5=9，G=4+6=10。 4. 第三轮：未圈定最小的是 C(8)，圈定 C。C 的出边：C→F(3)、C→G(5)。更新：F=8+3=11，G 原来 10，现在 8+5=13，取小仍为 10。 5. 第四轮：未圈定最小的是 E(9)，圈定 E。E 的出边：E→F(2)、E→G(7)。更新：F=9+2=11（不变），G=9+7=16（比 10 大，不更新）。 6. 第五轮：未圈定最小的是 G(10)，圈定 G。G 的出边：G→H(3)、G→J(9)。更新：H=10+3=13，J=10+9=19。 7. 第六轮：未圈定最小的是 F(11)，圈定 F。F 的出边：F→H(2)、F→I(6)。更新：H=11+2=13（不变），I=11+6=17。 8. 第七轮：未圈定最小的是 H(13)，圈定 H。H 的出边：H→I(4)、H→J(6)。更新：I=13+4=17（不变），J=13+6=19（不变）。 9. 第八轮：未圈定最小的是 I(17)，圈定 I。I 的出边：I→J(2)。更新：J=17+2=19（仍为 19）。 10. 第九轮：未圈定最小的是 J(19)，圈定 J，算法结束。

最终得到 A 到 J 的最短距离为 19，对应选项 B。

避坑提醒

• 有向边只能按箭头走，别把 A→D 当成 D→A 用。
• 不要只盯着“离 A 最近”的点，Dijkstra 的关键是每次选“当前距离最小”的点。
• 手工算时，把每个点的当前最短距离写在图上，圈定一个就划掉，避免重复更新。

考频与趋势

图的基本概念在题库中非常高频，2023-2026 年分别考了 36、61、58、71 题，呈明显上升趋势；最短路径算法题整体 35 题，2026 年考了 7 题，2025 年 7 题，2024 年 6 题，近四年每年都在 6 题以上，且 2026 年达到 7 题，说明这类题已成为高频考点。结合图论基础的高频增长，未来 CSP 提高级、NOIP 提高组初赛继续考查最短路径的概率很大，出题形式仍可能以有向图、正权边为主，偶尔加入多条等价最短路让学生判断。

预测

基于近年考频（2024-2026 最短路径题数分别为 6、7、7）和图论基础题的爆发式增长（2026 年 71 题），可以预测 2027 年及以后，最短路径算法题仍将保持每年 6 题以上的频率，且更倾向于在初赛环节出现，难度上可能延续本题这种中等规模、需要手算 Dijkstra 的题型，偶尔会结合多源或多条件限制增加一点变化。