GESP 五级 · GESP 202506 C++ 五级 第 22 题

求解下图中 A 点到 D 点最短路径，其中 A 到 B 之间的 12 可以理解为距离。求解这样的问题常用 Dijkstra 算法，其思路是通过逐步选择当前距离起点最近的节点来求解非负权重图（如距离不能为负值）单源最短路径的算法。从该算法的描述可以看出，Dijkstra 算法是贪心算法。


贪心算法每一步做出当前最优选择，且不回溯。难点在于证明贪心策略的正确性（常用交换论证法）。

贪心算法需要严格证明正确性。典型错误：局部最优不等于全局最优。例如0-1背包问题就不能用贪心。

【考点】贪心策略｜Dijkstra 算法｜图算法

考纲定位：GESP 五级《算法与程序设计》图算法模块，最短路径专题。命题人把“贪心”概念和 Dijkstra 实现绑在一起，卡住只会背步骤不会理解策略的考生。这类题意在测试考生能否将算法名称映射到设计思想，而非仅仅记住步骤。学生常误以为 Dijkstra 是动态规划，其实它是纯贪心。命题人还通过“非负权重”这一边界条件，设置语义陷阱，让只看结论不读细节的考生选错。

解题思维：看到“Dijkstra 算法”先锁定“单源最短路径、非负权重”。算法核心是：每次选当前距离起点最近的未访问节点，加入已确定集合，再松弛其邻接边。这符合贪心定义——每一步局部最优，且因非负权重保证全局最优。其正确性基于“切性质”：一旦节点被选定，后续边权非负使其距离不可能再被改进。时间复杂度 O(V^2) 或 O(E+V log V)（优先队列优化），但无论哪种实现，贪心思想不变。

陷阱拆解：选 B 的考生常把 Dijkstra 和 Bellman‑Ford 混淆，以为它能处理负权重，但题目明确“非负权重图”，贪心才成立。另外“逐步选择”被误读为“动态规划”，其实 Dijkstra 是纯贪心，无子问题重叠。最阴险的是“绝对化表述”——题干说“Dijkstra 算法是贪心算法”，若学生纠结“有没有例外”，就掉进语义陷阱；其实非负权重下贪心是充分且必要的。边界条件“非负”被偷换为“任意”，导致逻辑漏洞。若改成“允许负权重”，Dijkstra 就失效，得换 Bellman‑Ford 或 SPFA。

反命题思维：若改成“允许负权重”，Dijkstra 就失效，得换 Bellman‑Ford 或 SPFA。所以刷题时先问：“这个条件变动会否推翻原策略？”