GESP 八级 · GESP 202603 C++ 八级 第 9 题

关于图论中的最短路径算法，下列说法中严格正确的是（ ）。

BFS 使用队列，按层次逐层遍历，适合求最短路径（边权为1时）。核心：标记已访问，避免重复入队。

BFS 入队后立即标记已访问，防止重复入队。队列为空时搜索结束。注意区分树的BFS（无需visited标记）和图的BFS。

【考点】最短路径算法｜Dijkstra 与 Floyd 算法｜负权边与负权环

本题位于 GESP 八级"图论算法"模块，核心考查点在于区分不同最短路径算法的适用场景。命题人故意用"负权边"和"无向图"这两个高频易混点设卡，正是为了筛掉只背结论不会辨析的学生。

看到"最短路径"先定位算法：Dijkstra 贪心策略要求边权非负，Floyd 本质是动态规划，可处理负权边但需无负权环。逐项验证：A 错在 Dijkstra 遇到负权边会失效（松弛顺序被破坏）；C 错在无向图同样适用 Dijkstra/Bellman-Ford（BFS 仅用于无权图）；D 错在 Dijkstra 始终选距离起始点最近的未访问节点，而非最远。

选项 C 的陷阱在于偷换"无向图"与"无权图"的概念——无向图完全可以用 Dijkstra 求解，命题人用"只能通过 BFS"诱导学生将 BFS 泛化到所有图；选项 D 是典型的反向表述陷阱，利用"最远"与"最近"的语义混淆，考察对贪心策略的记忆精度。

若把 Dijkstra 改成 Bellman-Ford，即可处理负权边（但时间复杂度升至 O(nm)）；若允许负权环，Floyd 需额外检测环（否则距离会无限小）。刷到此类题先自问：命题人想考我算法的"边界条件"还是"适用图类型"？