Floyd算法核心是动态规划，通过k在最外层的三重循环，以di = min(di, di + dk)松弛所有点对；需正确初始化（如0x3f3f3f3f防溢出）、检测负环（disti
弗洛伊德算法的核心是三重循环更新 dist[i][j]
弗洛伊德（Floyd-Warshall）本质是动态规划，用中间点 k 松弛所有点对 (i, j) 的最短路径。关键不是“怎么写循环”，而是初始化和更新顺序不能错：dist[i][j] 初始必须设为足够大的值（如 INT_MAX/2），避免加法溢出；k 必须放在最外层循环，否则状态转移不完整。
常见错误是把 k 放在内层，或用 INT_MAX 直接参与加法导致溢出变成负数，后续比较全乱。正确做法是：
- 用
vector或手动限制最大值（如> 1e18）替代INT_MAX -
k从0到n-1枚举，内层i、j遍历全部顶点 - 更新时写成
if (dist[i][k] != INF && dist[k][j] != INF) dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
有向图和无向图只需改输入，算法本身不变
弗洛伊德不关心图的有向性——它处理的是邻接矩阵。输入时，无向图要双向赋值：dist[u][v] = dist[v][u] = w;；有向图只赋单向：dist[u][v] = w;。其余逻辑完全一致。容易被忽略的是自环（u == v）：若题目允许自环且权值非负，可保留；否则初始化时应设 dist[i][i] = 0，并在读入时跳过 u == v 的边（除非明确要求）。
示例片段：
for (int i = 0; i > u >> v >> w;
if (u != v) dist[u][v] = min(dist[u][v], (long long)w); // 防重边
}
检测负环只需检查 dist[i][i]
弗洛伊德运行完后，若任意 dist[i][i] 小于 0，说明存在从 i 出发又回到 i 的负权环。注意不是看 dist[i][j] 是否为负——负权边合法，负环才非法。实际使用中，常在三重循环后加一轮检查：
- 遍历所有
i，若dist[i][i] ，立即返回有负环 - 不要在循环中提前 break，因为
k没跑完时dist[i][i]可能暂时为负（尚未收敛） - 如果题目只要求单源最短路且可能有负环，弗洛伊德不如 Bellman-Ford 高效，别硬套
空间和时间开销大，别在稀疏图上硬用
O(n³) 时间和 O(n²) 空间是硬伤。当 n > 500 时，纯弗洛伊德大概率超时或爆内存。此时应考虑：n 很大但边很少？用 n 次 Dijkstra（需堆优化）；只要部分点对距离？用 Johnson 算法；需要动态加边？那就不是弗洛伊德的场景了。
另外，二维数组用 vector 会比原生 int dist[N][N] 稍慢，但更安全。若确定 n 不超过 400，用 int dist[405][405] 配 #define INF 0x3f3f3f3f 是常见竞赛写法——它比 INT_MAX 小，加法不易溢出，且 memset(dist, 0x3f, sizeof dist) 可一键初始化。
真正容易被忽略的，是问题是否真的需要“所有点对最短路”。很多时候你只查几个 (s, t)，却写了全套弗洛伊德——先确认需求，再选算法。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
