NOIP 提高 2018 第一轮 第 13 题：下列关于最短路算法的说法正确的有（

题目

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

答案

A、B、D

题解

考点定位

本题考「最短路算法适用性（不定项）」,对应大纲 4.3.3 最短路（难度【4】）。

解题过程

• A 无负回路但有负边 ⇒ Dijkstra ✗、Floyd ✓（ Floyd 不依赖非负权）……官方答案 A ✓（无负回路时多次调用 Dijkstra 的 Johnson 重赋权法可行）；
• B 无负边多次 Dijkstra ✓；
• C 负回路时 Dijkstra ✗（结果错误）；
• D 无负边一次 Dijkstra 求单源 ✓。

答案：A、B、D。

易错提醒

① Dijkstra 要求非负边权；② 负边存在用 Bellman-Ford/SPFA；Johnson 用 BF 重赋权后跑 Dijkstra。