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

在使用 Floyd 算法求任意两点间最短路径时，时间复杂度为 $O(V^3)$。若在某次算法执行前，已经用 Dijkstra 算法正确求出了所有点对的最短路并存入了 dist 数组。如果此时继续对该 dist 数组执行一次完整的 Floyd 算法过程（无任何提前终止），执行完毕后 dist 数组内的值（ ）。

分析时间复杂度时关注循环层数和每层迭代次数，递归算法则分析递归树。注意最坏/最好/平均情况的区别。

分析复杂度时注意外层循环和内层循环的关联。例如内外两层都到n的循环不一定是O(n²)，要看内层是否每次都在缩小。

【考点】Floyd 算法松弛原理｜Dijkstra 最短路最优性｜松弛操作的单调性

1. 🎯 考纲定位

本题属于 GESP 八级「图算法与应用」模块，专门考察 Floyd 算法核心机制与 Dijkstra 最短路算法最优性之间的逻辑关系。命题人卡住绝大多数考生的弱点在于：混淆了「松弛操作」与「状态改变」——以为只要跑了松弛就一定会变，却忘了松弛的本质是「取最小值」，已有最优解的情况下 min(S, S) 等于 S。