17370845950

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 数组不再可靠

常见错误与性能陷阱

实际写的时候最容易栽在三类地方：

• 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] 时同步更新中继点 —— 这部分容易写错且增加内存开销，非必要不建议加。