C++实现单源最短路径Floyd算法 _ 动态规划思想【详解】-C++-PHP中文网

floyd算法是全源最短路径算法，非单源；其三重循环结构强制计算所有点对距离，无法优化为单源，时间复杂度o(n³)远高于dijkstra的o(m log n)。

c++实现单源最短路径floyd算法 _ 动态规划思想【详解】

Floyd 算法不是单源最短路径算法，它天生就是全源（APSP）的。如果你在 C++ 里用 Floyd 去“解决单源问题”，本质是做了冗余计算：它会算出所有点对的最短距离，但你只取其中一行（比如第 s 行）——这没错，但代价是 O(n³) 时间，而 Dijkstra 或 SPFA 只要 O(m log n) 或 O(nm)。

别被“单源 + Floyd”这种提法带偏。真正该问的是：什么时候非得用 Floyd，哪怕只关心一个起点？

为什么不能把 Floyd 当作单源算法来“优化”？

因为它的更新逻辑根本不区分起点：

Floyd 的核心是三重循环：for (int k = 0; k
每次迭代都在检查「是否经过 k 能让 i→j 更短」，和你关心不关心 i == s 完全无关
你无法提前 break 或跳过某些 i、j —— 一旦跳过，后续依赖该状态的更新就会失效
试图只初始化第 s 行为 0、其余设 INF，然后跑 Floyd？结果大概率全错：因为 dist[i][k] 和 dist[k][j] 大概率仍是 INF，未判就相加会溢出，或导致错误松弛

什么场景下“单源需求”却必须用 Floyd？

只有两类现实情况值得考虑 Floyd，而不是因为它“能做单源”，而是因为它**不可替代**：

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

图极小且稠密（n ≤ 100），但你要查成百上千次不同起点到不同终点的距离：预处理一次 Floyd，之后 O(1) 查表，总代价远低于反复跑 Dijkstra
图含负权边，且你需要检测负环：跑完 Floyd 后检查任意 dist[i][i] 即可确认存在负环；<code>Dijkstra 在负权下直接失效，SPFA 检负环需额外维护入队次数

C++ 实现 Floyd 必须绕开的三个坑

这些坑和“单源”无关，但只要写错，哪怕只取第 0 行结果也是错的：

INF 不能用 INT_MAX：两段 INT_MAX 相加触发 signed integer overflow。改用 0x3f3f3f3f 或 LLONG_MAX / 2（对应 long long）
更新前必须判 INF：写成 dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 是危险的。正确写法是：
```
if (dist[i][k] != INF && dist[k][j] != INF) {
    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
```
k 必须是最外层循环：顺序改成 i 或 j 在外，dist[i][k] 和 dist[k][j] 可能还是上一轮旧值，算法退化为错误的松弛顺序，结果不可信

如果真只要单源，选 Dijkstra 还是 SPFA？

看边权性质：

非负权边 → 无脑用 Dijkstra + priority_queue，稳定高效
含负权边但无负环 → 用 SPFA（即队列优化的 Bellman-Ford），注意它最坏 O(nm)，稀疏图可接受；稠密图不如 Floyd 预处理后查表
不确定有没有负环 → 先跑一遍 Floyd 检 dist[i][i]，再决定后续用哪种单源算法

Floyd 的价值不在“能干单源的活”，而在它用固定二维数组、确定三重序、一次预处理就封印了全图拓扑关系——这种确定性，在需要多轮查询或负权分析时，比任何单源算法都更难替代。写的时候漏判一个 INF，或错调一层循环，整个矩阵就废了，而且很难 debug。