Floyd最短路算法详解

2026-06-05

算法概述

Floyd-Warshall 算法（简称 Floyd 算法）是由 Robert Floyd 和 Stephen Warshall 共同提出的一种动态规划算法，用于求解加权图中任意两点之间的最短路径。该算法可以处理有向图或无向图，并且可以处理负权边（但不能处理负权环）。

动态规划初步

在讲解 Floyd 算法之前，让我们先来了解一下什么是动态规划（Dynamic Programming，简称 DP）。

什么是动态规划？

动态规划是一种解决复杂问题的算法思想，它的核心思想是：将一个复杂问题分解为若干个重叠的子问题，先求解子问题，再从这些子问题的解中得到原问题的解。

一个简单的例子：爬楼梯

假设你要爬楼梯，每次可以爬 1 阶或 2 阶，问爬到第 n 阶有多少种不同的方法？

我们可以这样思考：

爬到第 1 阶：只有 1 种方法（直接爬 1 阶）
爬到第 2 阶：有 2 种方法（1+1 或直接爬 2 阶）
爬到第 n 阶：可以从第 n-1 阶爬 1 阶上来，或者从第 n-2 阶爬 2 阶上来

因此，我们可以定义：

dp[i] 表示爬到第 i 阶的方法数
状态转移方程：dp[i] = dp[i-1] + dp[i-2]

这就是动态规划的基本思想！

动态规划的关键要素

状态定义：用 dp 数组表示问题的某种状态
状态转移方程：描述如何从已知状态推导出未知状态
初始条件：确定边界情况的初始值
计算顺序：按照正确的顺序计算状态值

Floyd 算法与动态规划

Floyd 算法正是利用了动态规划的思想，通过逐步考虑加入更多的中间节点，来更新所有点对之间的最短路径。接下来我们就来详细讲解 Floyd 算法的核心思想。

核心思想

Floyd 算法的核心思想是动态规划。我们考虑对于每一对顶点 (i, j)，是否存在一个中间顶点 k，使得从 i 经过 k 再到 j 的路径比直接从 i 到 j 的路径更短。

定义状态 dp[k][i][j] 表示只经过前 k 个顶点，从 i 到 j 的最短路径长度。

状态转移方程：

1	dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])

通过优化，我们可以使用二维数组 dp[i][j] 来节省空间，直接在原数组上进行更新。

详细步骤

初始化距离矩阵：
- dp[i][j] 表示从 i 到 j 的直接距离
- dp[i][i] = 0（自己到自己的距离为 0）
- 如果 i 和 j 之间没有直接边，则 dp[i][j] = INF（无穷大）
三重循环更新：
- 最外层循环 k 枚举中间节点
- 中间层循环 i 枚举起点
- 最内层循环 j 枚举终点
- 更新公式：dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
输出结果：
- 最终 dp[i][j] 即为 i 到 j 的最短路径长度

代码实现

完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 10;

int main() {
    int n, m;
    cin >> n >> m;
    
    int dp[105][105];
    
    // 初始化距离矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                dp[i][j] = 0;
            else
                dp[i][j] = INF;
        }
    }
    
    // 输入边
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dp[u][v] = min(dp[u][v], w);
        dp[v][u] = min(dp[v][u], w);  // 无向图
    }
    
    // Floyd 算法核心
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
            }
        }
    }
    
    // 输出结果
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << dp[i][j] << " ";
        }
        cout << endl;
    }
    
    return 0;
}

输入输出示例

输入：

输出：

复杂度分析

时间复杂度：O(n³)，其中 n 是顶点数量。三重循环每层都是 O(n)。
空间复杂度：O(n²)，用于存储距离矩阵。

与其他最短路算法对比：

Dijkstra：O(m + n log n)（单源最短路）
Bellman-Ford：O(nm)（单源最短路，可处理负权）
Floyd：O(n³)（多源最短路）

实际应用案例

城市间交通规划：计算任意两座城市之间的最短路径
网络路由：确定数据包在网络中的最优传输路径
社交网络分析：计算用户之间的最短社交距离
地图导航系统：提供多目的地的最优路线规划

常见问题及解决方案

问题一：处理负权边

Floyd 算法可以处理负权边，但需要注意：

不能有负权环（即总权值为负的环）
如果存在负权环，算法会一直更新，导致结果错误

问题二：如何记录路径

如果需要记录具体的路径，可以额外维护一个 path[i][j] 数组，记录从 i 到 j 的最短路径上 j 的前驱节点。

int path[105][105];

// 初始化
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        path[i][j] = j;  // 初始化为直接到 j
    }
}

// 更新时
if (dp[i][k] + dp[k][j] < dp[i][j]) {
    dp[i][j] = dp[i][k] + dp[k][j];
    path[i][j] = path[i][k];
}

问题三：顶点编号问题

如果顶点编号不是从 1 开始，或者编号不连续，可以使用哈希表或重映射来处理。

问题四：INF 的取值

INF 的取值要足够大，但又要避免溢出：

一般可以取 1e9 或 0x3f3f3f3f
注意 dp[i][k] + dp[k][j] 不要超过数据类型范围

注意事项

循环顺序很重要：必须按照 k → i → j 的顺序，不能颠倒
初始化要正确：对角线元素为 0，其他初始化为无穷大
处理重边：输入时取最小值
溢出问题：注意数据类型，避免整数溢出
负权环检测：如果需要检测负权环，可以检查 dp[i][i] < 0
注意审题：如果题目中说明是无向图，那么就要正反都存一次边

负环与环的检测

什么是负环？

负环是指图中一个环（从某个点出发，经过若干条边后回到原点），其所有边的权值之和为负数。如果图中存在负环，那么在这个环上不断走下去，路径长度会越来越小（趋向于负无穷），此时不存在最短路径。

Floyd 算法检测负环

Floyd 算法可以很方便地检测图中是否存在负环，方法如下：

检测原理：
在 Floyd 算法运行结束后，检查是否存在某个顶点 i，使得 dp[i][i] < 0。

如果存在这样的 i，说明图中存在负环
因为只有当存在一个包含 i 的负环时，从 i 出发绕这个环走一圈再回到 i 的路径长度才会小于 0

检测负环的代码实现

#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9 + 10;

int main() {
    int n, m;
    cin >> n >> m;
    
    int dp[105][105];
    
    // 初始化距离矩阵
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i == j)
                dp[i][j] = 0;
            else
                dp[i][j] = INF;
        }
    }
    
    // 输入边
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        dp[u][v] = min(dp[u][v], w);
        // 如果是无向图，取消下面这行的注释
        // dp[v][u] = min(dp[v][u], w);
    }
    
    // Floyd 算法核心
    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (dp[i][k] < INF && dp[k][j] < INF) {
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
                }
            }
        }
    }
    
    // 检测负环
    bool fu_cycle = false;
    for (int i = 1; i <= n; i++) {
        if (dp[i][i] < 0) {
            fu_cycle = true;
            break;
        }
    }
    
    if (fu_cycle) {
        cout << "图中存在负环" << endl;
    } else {
        cout << "图中不存在负环" << endl;
        // 输出最短路径
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                cout << dp[i][j] << " ";
            }
            cout << endl;
        }
    }
    
    return 0;
}

检测负环示例

输入：

输出：

图中存在负环

解释：存在环 1→2→3→1，权值之和为 1 + 1 + (-3) = -1 < 0，因此存在负环。

一般环的检测

如果只是想检测图中是否存在环（不要求是负环），Floyd 算法也可以做到：

方法：

先运行 Floyd 算法
对于任意两个顶点 i 和 j（i ≠ j），如果 dp[i][j] < INF 且 dp[j][i] < INF，说明 i 和 j 在同一个强连通分量中
如果强连通分量的大小大于 1，说明存在环

不过需要注意的是，Floyd 算法检测环的效率不如专门的算法（如 DFS、拓扑排序等），如果只需要检测环，建议使用更高效的算法。

传递闭包

Floyd 算法的思想还可以用于计算图的传递闭包（Transitive Closure），即判断任意两点之间是否连通。

传递闭包代码：

bool reach[105][105];

// 初始化
for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        if (i == j || 有边 i->j)
            reach[i][j] = true;
        else
            reach[i][j] = false;
    }
}

// Floyd-Warshall 计算传递闭包
for (int k = 1; k <= n; k++) {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            reach[i][j] = reach[i][j] || (reach[i][k] && reach[k][j]);
        }
    }
}

总结

Floyd 算法虽然时间复杂度较高，但实现难度较小，可以通过该算法对动态规划问题作初步认识。

附件下载

本文配套的 PPT 讲义可在此下载：

下载 Floyd 最短路算法 PPT