GESP 八级 · GESP 202606 C++ 八级 第 10 题

有向非负权图边为 $1\to 2(3)$、$2\to 4(4)$、$1\to 3(10)$、$3\to 4(1)$、$2\to 3(2)$。使用 Dijkstra 算法从 1 号顶点出发到 4 号顶点的最短距离为（ ）。

单源最短路：Dijkstra（无负权，O(mlog n)）、SPFA/Bellman-Ford（可负权，检测负环）。全源：Floyd（O(n³)）。

Dijkstra不能处理负权边。有负权边用Bellman-Ford或SPFA。有负环时最短路不存在（可无限缩小）。

【考点】Dijkstra算法｜优先队列｜最短路径松弛

【1. 🎯 考纲定位】 GESP 八级图论模块核心考点：最短路径算法。命题人故意设计"非负权有向图 + 中间节点存在更优路径"的场景，卡住所有只会背算法流程、不会手动模拟松弛的学生——这是区分"看过课件"与"真正会做"的分水岭。

【2. 🧠 解题思维】 Dijkstra 标准流程：先置源点距离为 0，其余为 ∞；每次从优先队列弹出当前最小距离点，松弛其所有出边。本题关键步骤：

• 弹出 1：松弛 1→2(3)、1→3(10)，队列变 [(3,2),(10,3)]
• 弹出 2：松弛 2→4(4) 得 7、2→3(2) 把 3 更新为 5，队列 [(5,3),(7,4)]
• 弹出 3：松弛 3→4(1) 把 4 更新为 6，队列 [(6,4),(7,4)]
• 弹出 4：目标已确定，最短距离 6。

通法：对任意非负权图，Dijkstra 必须严格按距离从小到大松弛，不可跳过中间节点。

【3. 🪤 陷阱拆解】 选项 B(7) 是只走 1→2→4 的"最短路径"；选项 C(8) 来自 1→2→3→4 但误把 3→4 算成 5；选项 D(11) 是忽略 2→3 更新的"直连 1→3→4"。最阴险处在于：2 号点更新后，3 号点的距离从 10 降到 5，若只按弹出顺序处理而不回头松弛 3→4，就会得到 7。这恰恰是死记算法流程的学生最容易栽跟头的地方。

【4. 🔄 反命题思维】 如果把中间边 2→3 改成 100，答案会跳回 7；若把 3→4 改成 100，答案会跳回 8。命题人替换一个数值，就能把同一张图变成完全不同的题。刷到类似题时，先问自己："命题人想考我什么？"