Floyd算法适合节点数≤500且需所有节点对最短路径的场景；支持有向/无向图及负权边（无负环），实现简洁，k必须为最外层循环枚举中转点，避免溢出与更新错误。
Floyd 算法适合什么场景
当图节点数 ≤ 500，且你需要所有节点对之间的最短路径（不只是单源），floyd-warshall 是最直接的选择。它不挑图类型：支持有向/无向、带负权边（但不能有负环），实现简单、逻辑清晰，比对每个点跑一次 dijkstra 更省心——尤其在稠密图中。
核心三重循环怎么写才不出错
关键不是记公式，而是理解 k 的含义：枚举“中转点”。顺序错了会算错，必须是 k 在最外层。
常见错误：i 或 j 放最外层，导致路径更新不完整；或初始化时把非邻接点设为 INT_MAX 后直接做加法，溢出变负数。
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (dist[i][k] != INF && dist[k][j] != INF) {
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
注意点：
立即学习“C++免费学习笔记（深入）”；
-
INF建议用1e9或0x3f3f3f3f，避免用INT_MAX（加法易溢出） - 自环初始化为
0，无边位置初始化为INF - 输入边时注意方向：有向图只赋
dist[u][v]，无向图要同时设dist[u][v]和dist[v][u]
如何检测负环
跑完 Floyd 后，检查任意 dist[i][i] 即可。因为 <code>dist[i][i] 表示从 i 出发回到 i 的最短路径长度，若为负，说明存在负环。
注意：不能在循环中途 break，必须等三重循环全部结束再查——否则 dist[i][i] 还没收敛。
实际判断写法：
bool has_negative_cycle = false;
for (int i = 0; i < n; i++) {
if (dist[i][i] < 0) {
has_negative_cycle = true;
break;
}
}
空间与性能要注意的坑
floyd 是 O(n³) 时间、O(n²) 空间，500 个节点时约需 1MB 内存和 1.25 亿次运算，在普通机器上约耗时 0.1–0.3 秒；到 1000 节点就变成 10 亿次，基本卡住。
如果你只关心路径长度、不需要具体路径，可以省掉 next 数组；但如果要还原路径，得额外维护 next[i][j] 记录 i → j 的第一个中转点，并在更新 dist[i][j] 时同步更新。
容易被忽略的一点：Floyd 无法处理「边权动态变化」——它是一次性离线算法。如果图结构会频繁变动，得换在线算法或重跑。
