Floyd算法适用于求解所有节点对最短路径，支持负权边但不支持负权环，适合n≤500的稠密图；核心是k为中转点的三层循环；负权环通过检查disti
什么是 Floyd 算法适用的场景
Floyd 算法本质是动态规划，用来求解所有节点对之间的最短路径（All-Pairs Shortest Paths），适用于有向图或无向图，允许负权边（但不能有负权环）。它不适用于稀疏图的大规模场景（时间复杂度 O(n³)），但代码简洁、易于理解，特别适合顶点数 n ≤ 500 的情况。
如何用 C++ 实现 Floyd 核心逻辑
核心就是三层循环：枚举中转点 k，再枚举起点 i 和终点 j，判断是否能通过 k 缩短 i→j 的距离。关键点在于初始化和边界处理：
- 邻接矩阵
dist[i][j]初始化时，i == j设为0，有边则设为边权，否则设为一个足够大的值（如INT_MAX/2，避免加法溢出） - 必须用
dist[i][k] + dist[k][j] 判断更新，不能写成（否则可能误更新） - 内层循环顺序固定：
k必须是最外层，否则不是 Floyd
const int INF = INT_MAX / 2;
int dist[510][510]; // 假设最多 500 个点
// 初始化
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (i == j) dist[i][j] = 0;
else dist[i][j] = INF;
}
}
// 输入边（无向图则双向赋值）
for (int i = 0; i < m; i++) {
int u, v, w;
cin >> u >> v >> w;
dist[u][v] = min(dist[u][v], w); // 防重边
}
// Floyd 主循环
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]);
}
}
}
}
怎么检测负权环
Floyd 运行结束后，若存在某个 i 满足 dist[i][i] ，说明从 i 出发能回到自身且总权为负，即存在负权环。注意：不能只检查输入时的自环，因为负权环可能是长度 ≥ 2 的环。
- 检测必须在 Floyd 完全执行后进行
- 只要任意一个
dist[i][i] 就可判定存在负权环 - 此时所有涉及该环的路径最短距离无意义，
dist数组不再可靠
常见错误与性能陷阱
实际写的时候最容易栽在三类地方：
立即学习“C++免费学习笔记（深入）”；
-
INF设太大（如0x3f3f3f3f是常用安全值），但直接用INT_MAX会导致dist[i][k] + dist[k][j]溢出为负数，进而误更新 - 忘记判断
dist[i][k]和dist[k][j]是否可达（即是否），导致非法加法污染结果 - 把顶点编号当成从
1开始却用0到n-1的数组索引，造成越界或漏更新 - 在稠密图上硬套 Floyd（比如
n = 10⁴），会 TLE；此时应改用n次 Dijkstra（配合堆优化）
算法本身不记录路径，如需输出具体路径，得额外维护 next[i][j] 数组，每次更新 dist[i][j] 时同步更新中继点 —— 这部分容易写错且增加内存开销，非必要不建议加。
