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

只要图中不存在负权环，Dijkstra 算法就一定能正确处理带负权边的图。

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

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

【考点】最短路径算法｜Dijkstra 算法原理｜负权边处理

1. 🎯 考纲定位

本题考查《GESP 考试大纲》二级"图算法"模块的核心内容。命题人专门挖了这个坑——80% 考生死记"Dijkstra 求单源最短路"就以为算法万能，完全没注意其非负权假设这一铁律。这道题就是来筛掉那些只背结论、不懂前提条件的。