k必须放在最外层，因为状态disti定义为只允许经0到k中转时的最短距离；若k在内层，disti和distk可能已含未授权的更高编号中转点，破坏状态含义。
直接说结论：floydWarshall 的核心不是“写三个 for 循环”就完事，而是必须让 k 作为最外层循环——它定义了「允许使用的中转点编号上限」，这是动态规划状态转移的依赖顺序，错一层就会算错最短路径。
为什么 k 必须放在最外层？
因为状态定义是：dist[i][j] 表示「只允许经过顶点 0 到 k 作为中转点时，i 到 j 的最短距离」。每次迭代 k，相当于把中转能力从 {0…k−1} 扩展到 {0…k}。
如果把 k 放在内层，比如 i-j-k 顺序，那么更新 dist[i][j] 时用的 dist[i][k] 和 dist[k][j] 可能已经包含了尚未被允许的更高编号中转点（比如 k+1），破坏了状态含义，导致结果不可靠。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
- 正确顺序：
for (int k = 0; k - 错误顺序举例：
for (int i = 0; i —— 此时 <code>dist[i][k]可能已含k+1中转，逻辑崩坏 -
k从0开始递增不是风格问题，是状态定义强制要求：只有按序扩展中转集，才能保证子问题最优性
dist[i][k] + dist[k][j] 前为什么要检查 <code>INF？
避免整数溢出和逻辑错误。C++ 中用 INT_MAX 表示无穷大，但 INT_MAX + INT_MAX 会溢出为负数，导致错误更新。
- 必须先判断：
dist[i][k] != INT_MAX && dist[k][j] != INT_MAX - 再比较：
dist[i][k] + dist[k][j] - 漏掉前者，可能让
dist[i][j]被赋一个负得离谱的值，后续所有计算全乱 - 有些实现用
#define INF 0x3f3f3f3f防溢出，但检查仍是更安全、更明确的做法
如何重建任意 i→j 的最短路径？
仅靠 dist 矩阵只能知道距离，要还原路径需额外维护 next[i][j]：表示从 i 到 j 的最短路径上，i 的下一个顶点是谁。
- 初始化：
next[i][j] = j（若存在直连边i→j），否则为-1 - 更新距离时同步更新：
if (dist[i][k] + dist[k][j] - 重建路径：
vector<int> path; for (int u = i; u != j; u = next[u][j]) path.push_back(u); path.push_back(j);</int> - 注意：
next矩阵不能省略初始化，否则未设置的next[i][j]是随机值，path会崩溃或死循环
最容易被忽略的是：Floyd 不检测负权环，但一旦图中存在负权环，dist[i][i] 最终会变成负数——这是唯一可靠的负环信号。别指望算法自动报错，得自己加一行 for (int i = 0; i 。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
