答案是k必须为外层循环，因为Floyd是动态规划算法，状态dpk[j]表示只经编号≤k的节点的最短路，依赖dpk-1[k]和dpk-1[j]，必须先按k顺序求解子问题。
为什么 Floyd 算法必须用三重循环，且 k 必须是外层循环？
因为 Floyd 的核心是「以顶点 k 为中转点，更新所有 i→j 的最短距离」，这个“中转”必须按顺序逐步放开——k=0 允许经过顶点 0；k=1 允许经过 0 或 1；……直到 k=n−1 允许经过全部顶点。如果把 k 放在内层，dist[i][j] 可能用到尚未被当前 k 正确松弛过的中间值，导致路径重复计算或跳过更优解。
常见错误现象：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]) 写对了，但循环顺序写成 i, j, k，结果输出全是初始值或明显偏大。
- k 必须是外层循环（
for (int k = 0; k ） - 内层 i、j 顺序任意，但推荐先 i 后 j，符合内存局部性
- 初始化时，
dist[i][i]必须设为 0，否则自环会污染后续更新 - 用
INT_MAX/2而非INT_MAX做无穷大，防止dist[i][k] + dist[k][j]溢出变成负数
C++ 中如何安全初始化邻接矩阵并处理不存在的边？
Floyd 要求输入是完整 n×n 距离矩阵，不存在的边不能填 0（会被误认为长度为 0 的边），也不能留未初始化值（行为未定义）。标准做法是统一用一个足够大的数表示“不可达”。
使用场景：读入稀疏图后转稠密表示；或需要支持负权边（但不能有负环）。
立即学习“C++免费学习笔记（深入）”；
- 推荐初始化为
vector<vector>> dist(n, vector<int>(n, INT_MAX / 2))</int></vector> - 对角线清零：
for (int i = 0; i - 读入边
u → v权重w时，直接赋值dist[u][v] = w（注意是否允许重边，若允许则取 min） - 不要用
memset(dist, 0x3f, sizeof(dist))这类 C 风格初始化——对 vector 无效，且易错位
如何检测负环？Floyd 后还能不能查任意两点距离？
Floyd 运行结束后，若存在某个 i 满足 dist[i][i] ，说明从 i 出发有一条总权为负的回路——即负环。此时整个最短路径系统失效，<code>dist[i][j] 不再有意义。
性能影响：检测负环只需 O(n) 额外时间，加在三重循环之后即可，无兼容性代价。
- 负环检测代码紧接 Floyd 主循环后：
for (int i = 0; i - 一旦发现负环，不应再使用任何
dist[i][j]值——它们可能已失真 - 若无负环，
dist[i][j]就是 i 到 j 的最短距离，包括 i≠j 且原图不连通的情况（此时仍为INT_MAX/2） - 注意：Floyd 不能区分“不可达”和“数值溢出”，所以初始化上限必须合理（
INT_MAX/2是底线）
实际编码时 vector 和数组哪个更快？要不要手写堆优化？
对于 Floyd，二维 vector 和原生 int dist[N][N] 在 n ≤ 500 时性能差异微乎其微；但 vector 更安全、可变长、免静态大小限制。完全没必要手写堆——Floyd 本质就是 O(n³) 暴力动态规划，堆对它无加速作用，反而破坏状态转移依赖。
容易踩的坑：有人试图把 Floyd 改成“只更新受影响的行/列”，这是错的。Floyd 的 DP 状态依赖所有中间节点，无法剪枝。
- 竞赛/工程中优先用
vector<vector>></vector>，清晰且不易越界 - 若 n 固定且很大（如 1000+），可考虑
vector<int> dist(n * n)</int>手动映射下标提升缓存命中率 - 别碰“优化版 Floyd”——网上某些所谓“提前终止”或“稀疏化”的变种，99% 场景下要么错，要么没效果
- 真正该省的是空间：若只需求路径长度不需路径本身，可复用同一二维数组，无需额外
next数组
Floyd 看似简单，但 k 循环位置、无穷大选值、负环检测时机这三点，只要错一个，结果就不可信。调试时建议先用 3 个点的手算案例跑通，再扩规模。
