NOIP 提高组初赛 · NOIP 2018 提高组初赛试题 第 13 题

下列关于最短路算法的说法正确的有（ ）。

这题核心就是死磕 Dijkstra 的贪心前提——边权必须非负。拿到选项先想：有没有负权边？有没有负权环？一次跑能不能搞定所有点对？抓住这三个判断点，就能把四个选项逐个筛出来。

最容易栽跟头的是把 C 当对，以为只要没负权环，Dijkstra 就万无一失；其实有负权边哪怕没环，贪心策略也会把后续更短的路径给漏了。还有人选 D 时纠结“一次 Dijkstra 不能求每对”这句话是不是太绝对，其实它只是说单次跑只能算单源，想算全图确实得跑 n 次，这个逻辑是通的。

考点概念：Dijkstra 算法的适用条件

Dijkstra 的核心是贪心：每次从已确定最短路的集合里挑一个距离最小的点，然后松弛它的邻接边。这个“挑最小”的操作在边权全是正数时是安全的，因为一旦某个点被选中，它的距离就永远不会再被更小的值覆盖。可一旦图里出现负权边，哪怕没有负权环，被选中的点后面可能还有更短的路径（经过负权边），贪心就失效了。所以 A 选项说“有负权边（无负环）时不一定能求出最短路”是完全正确的。

命题视角：为什么爱考这个点

命题人最喜欢在“负权边 vs 负权环”之间挖坑，很多学生看到“没有负权环”就以为 Dijkstra 能随便用，其实负权环只是让最短路不存在，负权边才是让 Dijkstra 出错的根本原因。C 选项故意把“有负权环”和“一次 Dijkstra 一定正确”绑在一起，就是想让你掉进“只要没环就安全”的误区。D 选项则反其道而行，强调“一次 Dijkstra 只能算单源”，让你意识到要算所有点对得跑 n 次，或者用 Floyd，这也是高频考点。