floyd-warshall 不适合稀疏图因其时间复杂度恒为 o(v³)，与边数无关，而稀疏图（e≈v）用 dijkstra 或 spfa 更高效；v>500 易超时或爆内存，且 inf 选错易致溢出。
为什么 Floyd-Warshall 不适合稀疏图
Floyd-Warshall 是个三重循环的动态规划算法，时间复杂度固定为 O(V³)，和边数 E 无关。这意味着哪怕图里只有几条边，它照样要扫完所有顶点三元组。稀疏图（比如 E ≈ V）用 Dijkstra 配堆或 SPFA 更快；强行上 Floyd，纯属用大锤砸核桃。
常见错误现象：10⁴ 个点的图跑 Floyd 直接超时或爆内存——别试，V=500 就是安全线，再往上必须换算法。
- 适用场景：顶点数 ≤
500，且需要任意两点间最短距离（不止单源） - 优势在于能处理负权边（但不能有负环），且代码极简，易调试
- 初始化时，
dist[i][i]必须设为0，否则自环距离错，后续全崩
二维数组怎么初始化才不踩坑
核心是三点：无穷大值选什么、对角线怎么设、邻接关系怎么填。用 INT_MAX 当无穷大会导致 dist[i][k] + dist[k][j] 溢出——加法一越界就变负数，结果完全不可信。
实操建议：
立即学习“C++免费学习笔记（深入）”；
- 用一个明显大于所有可能路径和的常量，比如
1e9或0x3f3f3f3f（约109，且满足0x3f3f3f3f + 0x3f3f3f3f ） -
dist[i][i] = 0必须显式写，不能依赖初始化 - 读入边时，若存在重边，取
min(dist[u][v], w)，不是直接赋值
示例初始化片段：
const int INF = 0x3f3f3f3f;
int dist[505][505];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dist[i][j] = (i == j) ? 0 : INF;
}
}
// 加边：u→v 权重 w
dist[u][v] = min(dist[u][v], w);
三重循环顺序为什么不能调换
标准写法是 k 在最外层：for (int k = 1; k ，里面嵌套 <code>i 和 j。如果把 i 或 j 放最外，算法就退化成错的——它不再保证“只经由前 k 个点”的子问题正确转移。
本质原因：Floyd 的状态定义是 dist[k][i][j] 表示“只允许经过编号 ≤ k 的顶点”时 i→j 的最短距离。滚动数组优化后，k 必须是外层，才能确保更新 dist[i][j] 时，dist[i][k] 和 dist[k][j] 已经是“只经前 k−1 个点”的最优解。
- 错序后果：可能用到尚未收敛的中间值，结果随机、不可复现
- 编译器不会报错，但测试用例稍一变化就翻车
- 记忆口诀：“中转点 k 最外，它得先‘铺好路’，i 和 j 才能抄近道”
如何检测负环并避免误判
跑完 Floyd 后，检查任意 dist[i][i] 即可判定存在负环。但注意：初始化时 <code>dist[i][i] = 0，过程中若出现 dist[i][i] = dist[i][k] + dist[k][i] ，说明从 <code>i 出发绕一圈回来更短——这就是负环证据。
容易被忽略的细节：
- 不能只查输入边里的自环（
u == v且w ），因为负环可能跨多个点 - 如果图不连通，某些
dist[i][i]可能仍是INF，不影响判断；只要有一个就成立 - 检测必须在 Floyd 三重循环**结束后**立刻做，不能边跑边 break——否则漏检
检测代码片段：
bool has_negative_cycle = false;
for (int i = 1; i <= n; i++) {
if (dist[i][i] < 0) {
has_negative_cycle = true;
break;
}
}
真正难的不是写那三行循环，而是想清楚：你到底需不需要所有点对距离，以及能不能承受 V³ 的代价。很多号称“多源最短路”的需求，其实只需要几次 Dijkstra，或者根本只需连通性——别让算法惯性带偏了问题本身。
