【算法基础篇】（三十七）图论基础之多源最短路：Floyd 算法吃透所有点对最短路径！

前言

在图论的应用场景中，我们常常会遇到这样的需求：地图应用中查询任意两个城市间的最短车程、网络拓扑中计算任意两台设备间的最优传输路径、物流规划中确定任意两个仓库间的最低运输成本…… 这些问题的核心，都是多源最短路—— 即求出图中每一对顶点之间的最短路径。 单源最短路解决的是 “从一个起点到所有其他点” 的路径问题，而多源最短路则需要覆盖 “所有点到所有点” 的全量路径。今天这篇文章，我会聚焦多源最短路的经典解法 ——Floyd-Warshall 算法（简称 Floyd 算法），从原理剖析、代码实现到实战例题，带你彻底掌握这一 “通吃所有点对” 的强大算法。 不仅如此，我还会分享 Floyd 算法的核心拓展应用（如无向图最小环问题、动态加点的最短路径查询），结合洛谷经典例题，让你从 “理解算法” 到 “灵活运用”，真正吃透多源最短路问题！下面就让我们正式开始吧！

一、前置知识：多源最短路与 Floyd 算法的核心定位

在正式讲解算法之前，我们先明确几个关键概念，帮你建立对多源最短路的清晰认知：

1. 什么是多源最短路？

多源最短路的定义很简单：给定一个带权图（有向或无向，边权可正可负，但不能存在负环，否则部分点对的最短路径不存在），求出所有顶点对 (i, j) 之间的最短路径长度（i 到 j 的最短路径，以及 j 到 i 的最短路径，若图为有向图则可能不同）。

2. 为什么选择 Floyd 算法？

解决多源最短路，其实有两种思路：

• 思路 1：对每个顶点都跑一遍单源最短路算法（如 Dijkstra 或 SPFA）。若图中有 n 个顶点，时间复杂度为 O (n×(m log n))（堆优化 Dijkstra），适用于稀疏图。
• 思路 2：使用 Floyd 算法，时间复杂度为 O (n³)，适用于稠密图（n 较小，如 n≤200）。

Floyd 算法的核心优势在于实现简单、代码简洁，仅需三层循环即可完成，无需复杂的数据结构支持。对于 n≤200 的场景，O (n³) 的时间复杂度完全可接受（200³=8e6，计算机可瞬间处理），因此成为多源最短路的首选算法。

3. 关键前提：Floyd 算法的适用条件

Floyd 算法虽然强大，但有一个重要前提：图中不能存在负环。因为如果存在负环，那么经过负环的点对之间的路径长度可以无限减小，不存在最短路径。

但要注意：Floyd 算法支持负权边（只要没有负环）。例如，图中存在边权为 - 2、-3 的边，只要没有形成回路的边权和为负，就可以正常计算。

4. 核心思想：动态规划与 “插点法”

Floyd 算法的本质是动态规划，其核心思想可以概括为 “插点法”—— 通过不断在两个顶点之间插入新的顶点，更新这两个顶点之间的最短路径。

我们用一个三维数组 f[k][i][j] 来表示动态规划的状态：

• 状态定义：f[k][i][j] 表示 “仅允许经过顶点 1~k 作为中转点时，顶点 i 到顶点 j 的最短路径长度”。

基于这个状态定义，我们可以得到状态转移方程：

• 当不使用顶点 k 作为中转点时：f[k][i][j] = f[k-1][i][j]（最短路径还是原来的路径）；
• 当使用顶点 k 作为中转点时：f[k][i][j] = min(f[k-1][i][k] + f[k-1][k][j], f[k-1][i][j])（比较 “直接从 i 到 j” 和 “i 经过 k 到 j” 的路径长度，取较小值）。

空间优化：从三维到二维

观察状态转移方程可以发现，f[k][i][j] 只依赖于 f[k-1][...]（上一层的状态），因此我们可以将三维数组优化为二维数组 f[i][j]，直接在原数组上进行更新。

优化后的状态转移方程为：

f[i][j] = min(f[i][j], f[i][k] + f[k][j])

这里的 k 是 “当前允许使用的中转顶点”，因此循环顺序必须是先枚举 k，再枚举 i 和 j—— 这是 Floyd 算法的关键细节，也是最容易出错的地方！

5. 算法流程总结

Floyd 算法的流程非常简洁，总共分为 3 步：

1. 初始化：创建二维数组 f，f[i][j] 表示顶点 i 到顶点 j 的初始距离。
   • 若 i == j，则 f[i][j] = 0（自己到自己的距离为 0）；
   • 若 i 和 j 之间有直接边（权值为 w），则 f[i][j] = w；
   • 若 i 和 j 之间没有直接边，则 f[i][j] = INF（INF 表示无穷大，代表初始时不可达）。
2. 插点更新：枚举所有可能的中转顶点 k（1~n），然后枚举所有顶点对 (i, j)，用 f[i][k] + f[k][j] 更新 f[i][j]。
3. 结果输出：f[i][j] 即为顶点 i 到顶点 j 的最短路径长度（若仍为 INF，则表示不可达）。

二、Floyd 算法的代码实现：简洁到极致

基于上述思路，我们可以写出 Floyd 算法的 C++ 代码。代码非常简洁，核心仅需三层循环，适合记忆和默写。

1. 基础模板代码（无向图）

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;  // 顶点数上限，根据题目调整
const int INF = 0x3f3f3f3f;  // 表示无穷大（注意：避免溢出）

int n, m;
int f[N][N];  // f[i][j]：i到j的最短路径长度

void floyd() {
    // 枚举中转顶点k
    for (int k = 1; k <= n; ++k) {
        // 枚举所有顶点对(i, j)
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                // 状态转移：用k更新i到j的最短路径
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
}

int main() {
    cin >> n >> m;

    // 1. 初始化f数组
    memset(f, 0x3f, sizeof f);  // 所有边初始化为无穷大
    for (int i = 1; i <= n; ++i) {
        f[i][i] = 0;  // 自己到自己的距离为0
    }

    // 2. 读入边的信息（无向图，双向赋值）
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 若存在重边，取权值最小的边
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[v][u], w);
    }

    // 3. 执行Floyd算法
    floyd();

    // 4. 输出所有点对的最短路径
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (f[i][j] == INF) {
                cout << "INF ";  // 不可达
            } else {
                cout << f[i][j] << " ";
            }
        }
        cout << endl;
    }

    return 0;
}

2. 有向图的修改

如果图是有向图，只需修改边的初始化部分 —— 仅需赋值 f[u][v] = min(f[u][v], w)，无需赋值 f[v][u]（因为有向边的方向是单向的）。

修改后的边初始化代码：

// 读入有向边（u→v，权值w）
for (int i = 0; i < m; ++i) {
    int u, v, w;
    cin >> u >> v >> w;
    f[u][v] = min(f[u][v], w);  // 仅单向赋值
}

3. 关键细节说明

• 无穷大的选择：使用 0x3f3f3f3f 作为无穷大，原因是：
  1. 它是一个较大的数（约 1e9），不会被正常的边权值超过；
  2. 两个 0x3f3f3f3f 相加不会溢出（0x3f3f3f3f * 2 = 0x7ffffffe，小于 int 的最大值 0x7fffffff）。
• 重边处理：如果图中存在重边（多个边连接同一对顶点），我们取权值最小的边，因此用 min(f[u][v], w) 赋值。
• 循环顺序：必须先枚举中转顶点 k，再枚举 i 和 j！如果顺序错误，会导致部分路径无法正确更新。

三、模板题实战：洛谷 B3647 【模板】Floyd

题目链接

B3647 【模板】Floyd

题目描述

给出一张由n个点m条边组成的无向图，求出所有点对(i, j)之间的最短路径。

输入描述

• 第一行：两个整数n、m，分别表示顶点数和边数；
• 接下来m行：每行三个整数u、v、w，表示顶点u和v之间有一条权值为w的无向边。

输出描述

输出n行，每行n个整数，第i行第j个整数表示顶点i到j的最短路径长度。

示例输入

4 4
1 2 1
2 3 1
3 4 1
4 1 1

示例输出

0 1 2 1
1 0 1 2
2 1 0 1
1 2 1 0

解题思路

这是 Floyd 算法的基础模板题，无向图可看作双向有向图，因此读入边时需同时更新f[u][v]和f[v][u]。直接套用 Floyd 算法框架即可。

完整 C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;

int n, m;
int f[N][N];

int main() {
    // 初始化f数组
    memset(f, 0x3f, sizeof f);
    for (int i = 1; i <= N; ++i) {
        f[i][i] = 0;
    }

    // 读入数据
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        // 无向边，双向更新，保留最小权值（避免重边）
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[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 (f[i][k] != INF && f[k][j] != INF) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
    }

    // 输出结果
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cout << f[i][j] << " ";
        }
        cout << endl;
    }

    return 0;
}

代码解释

• 初始化时，f[i][i] = 0，其余为INF；
• 无向边需双向更新，避免重边影响（取最小权值）；
• 三层循环严格按照k → i → j的顺序，确保每个中间顶点都能正确更新路径；
• 输出时直接打印f[i][j]，即为i到j的最短路径长度。

四、基础应用：洛谷 P2910 Clear And Present Danger

题目链接

P2910 [USACO08OPEN] Clear And Present Danger S

题目描述

农夫约翰驾驶小艇在海上航行，海上有N个岛屿，编号 1~N。约翰需要按照藏宝图上的序列A₁, A₂, ..., Aₘ依次经过这些岛屿（从A₁出发，最后到Aₘ），求经过的航线危险指数之和的最小值。

危险指数D[i][j]表示岛屿i到j的直接航线危险指数（题目已给出所有D[i][j]）。

输入描述

• 第一行：两个整数N、M，分别表示岛屿数和必须经过的岛屿序列长度；
• 接下来M行：每行一个整数Aᵢ，表示必须经过的第i个岛屿；
• 接下来N行：每行N个整数，第i行第j个整数表示D[i][j]（D[i][i] = 0）。

示例输入

3 4
1
2
1
3
0 5 1
5 0 2
1 2 0

示例输出

7

解题思路

1. 题目给出的D[i][j]是直接航线的危险指数，但可能存在经过其他岛屿的更短路径（危险指数更小）；
2. 因此需要先通过 Floyd 算法求出所有岛屿对之间的最短危险指数（即任意两个岛屿之间的最优路径）；
3. 然后按照序列A₁ → A₂ → ... → Aₘ，累加相邻岛屿的最短危险指数之和，即为答案。

完整 C++ 代码

#include <iostream>
#include <cstring>
typedef long long LL;  // 防止结果溢出
using namespace std;

const int N = 110;
const int INF = 0x3f3f3f3f;

int n, m;
int f[N][N];
int a[10010];  // 存储必须经过的岛屿序列（M最大为1e4）

int main() {
    // 读入岛屿数和序列长度
    cin >> n >> m;

    // 读入必须经过的岛屿序列
    for (int i = 1; i <= m; ++i) {
        cin >> a[i];
    }

    // 读入初始危险指数矩阵D[i][j]，并初始化f数组
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            cin >> f[i][j];
        }
    }

    // Floyd算法求所有岛屿对的最短危险指数
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (f[i][k] != INF && f[k][j] != INF) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
    }

    // 累加序列中相邻岛屿的最短危险指数之和
    LL res = 0;
    for (int i = 2; i <= m; ++i) {
        int u = a[i-1], v = a[i];
        res += f[u][v];
    }

    // 输出结果
    cout << res << endl;

    return 0;
}

代码解释

• 由于M最大为 1e4，N最大为 100，f[i][j]最大为 1e5，累加和可能超过 int 范围，因此用long long存储结果；
• 初始时f[i][j]直接赋值为题目给出的D[i][j]，无需额外初始化（题目已保证D[i][i] = 0）；
• 累加过程中，直接使用 Floyd 更新后的f[u][v]（u和v为序列中相邻岛屿），确保每一段都是最优路径。

五、进阶实战：洛谷 P1119 灾后重建

题目链接

P1119 灾后重建

题目描述

B 地区有N个村庄（编号 0~N-1），M条双向公路。每个村庄i有一个重建完成时间t[i]（t[i]为 0 表示初始即可通车），重建完成当天即可通车。有Q个询问(x, y, t)，询问在第t天，村庄x到y的最短路径长度（路径必须经过已重建完成的村庄）。若无法到达（如x或y未重建、无路径），输出-1。

输入描述

• 第一行：两个整数N、M，表示村庄数和公路数；
• 第二行：N个非负整数t[0], t[1], ..., t[N-1]，表示每个村庄的重建时间（保证t非递减）；
• 接下来M行：每行三个整数i、j、w，表示村庄i和j之间有一条长度为w的公路；
• 接下来一行：整数Q，表示询问数；
• 接下来Q行：每行三个整数x、y、t，表示询问（保证t非递减）。

示例输入

4 5
1 2 3 4
0 2 1
2 3 1
3 1 2
2 1 4
0 3 5
4
2 0 2
0 1 2
0 1 3
0 1 4

示例输出

-1
-1
5
4

解题思路

这道题是 Floyd 算法的经典进阶应用，核心在于理解 “重建时间” 对路径的限制 —— 只有重建完成的村庄才能作为中间顶点或路径上的顶点。

关键观察

1. 村庄的重建时间t是非递减的（t[0] ≤ t[1] ≤ ... ≤ t[N-1]）；
2. 询问的时间t也是非递减的；
3. Floyd 算法的 “插点法” 本质是依次将顶点作为中间顶点加入，更新路径。这与 “村庄按重建时间依次通车” 的过程完全契合！

算法设计

1. 初始化 Floyd 数组f，公路初始长度为给定w，无公路为INF，f[i][i] = 0；
2. 维护一个指针pos，表示当前已重建完成的村庄（初始pos = 0）；
3. 对于每个询问(x, y, t)：a. 先将所有重建时间≤ t的村庄（t[pos] ≤ t）作为中间顶点加入 Floyd 算法，更新路径（因为这些村庄已通车，可作为中转）；b. 检查x和y是否已重建（t[x] ≤ t且t[y] ≤ t）；c. 若已重建且f[x][y] != INF，输出f[x][y]；否则输出-1。

为什么这样可行？

• 由于村庄重建时间和询问时间都是非递减的，一旦某个村庄被加入（作为中间顶点），后续的询问都可以使用它，无需重复处理；
• 每次询问前只需要处理新增的已重建村庄，避免了重复计算，时间复杂度优化为O(Q + N² + M)（因为每个村庄最多被处理一次，每次处理O(N²)）。

完整 C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 210;
const int INF = 0x3f3f3f3f;

int n, m, q;
int t[N];  // 每个村庄的重建时间
int f[N][N];  // Floyd数组

// 加入村庄k作为中间顶点，更新所有路径
void floyd(int k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            if (f[i][k] != INF && f[k][j] != INF) {
                f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
            }
        }
    }
}

int main() {
    // 初始化Floyd数组
    memset(f, 0x3f, sizeof f);
    for (int i = 0; i < N; ++i) {
        f[i][i] = 0;
    }

    // 读入村庄数和公路数
    cin >> n >> m;

    // 读入每个村庄的重建时间
    for (int i = 0; i < n; ++i) {
        cin >> t[i];
    }

    // 读入公路信息
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        f[u][v] = min(f[u][v], w);
        f[v][u] = min(f[v][u], w);  // 无向公路，双向更新
    }

    // 读入询问数
    cin >> q;

    int pos = 0;  // 当前已处理的最后一个村庄（已重建完成）
    while (q--) {
        int x, y, time;
        cin >> x >> y >> time;

        // 将所有重建时间≤当前询问时间的村庄加入Floyd
        while (pos < n && t[pos] <= time) {
            floyd(pos);
            pos++;
        }

        // 检查x和y是否已重建，且存在路径
        if (t[x] > time || t[y] > time || f[x][y] == INF) {
            cout << -1 << endl;
        } else {
            cout << f[x][y] << endl;
        }
    }

    return 0;
}

代码解释

• 村庄编号从 0 开始（与题目一致），因此数组初始化和循环均从 0 开始；
• floyd(k)函数的作用是将村庄k作为中间顶点，更新所有顶点对的最短路径；
• 指针pos的作用是 “懒加载” 已重建的村庄，避免重复处理，优化时间复杂度；
• 询问处理时，先确保所有已重建的村庄都被作为中间顶点加入，再判断路径是否存在。

六、拓展应用：洛谷 P6175 无向图的最小环问题

题目链接

P6175 无向图的最小环问题

题目描述

给定一张无向图，求图中一个至少包含 3 个顶点的环，使得环上所有边的权值之和最小（即最小环）。若无环，输出No solution.。

输入描述

• 第一行：两个整数n、m，表示顶点数和边数；
• 接下来m行：每行三个整数u、v、d，表示顶点u和v之间有一条权值为d的无向边。

示例输入

5 7
1 4 1
1 3 300
3 1 10
1 2 16
2 3 100
2 5 15
5 3 20

示例输出

61

解题思路

最小环问题是多源最短路的经典拓展，Floyd 算法可以巧妙地解决这个问题。

核心观察

无向图中的最小环，必然可以表示为i → ... → k → j → i，其中：

• k是环中编号最大的顶点；
• i和j是环中与k直接相连的两个顶点；
• i → ... → j的路径中不包含k（因为k是最大编号顶点），因此这条路径的最短长度就是f[k-1][i][j]（只允许经过顶点 1~k-1 时的最短路径）。

因此，最小环的长度可以表示为：f[k-1][i][j] + w[i][k] + w[k][j]，其中w[i][k]是i到k的直接边权，w[k][j]是k到j的直接边权。

算法设计

1. 初始化 Floyd 数组f和原始边权数组w（w[i][j]存储i到j的直接边权）；
2. 枚举中间顶点k（从 1 到 n）：a. 在更新f[k][i][j]之前，先枚举所有i < k、j < k、i != j，计算f[k-1][i][j] + w[i][k] + w[k][j]，并更新最小环长度；b. 然后正常执行 Floyd 的状态转移，更新f[k][i][j]；
3. 枚举结束后，若最小环长度仍为无穷大，输出No solution.，否则输出最小环长度。

关键细节

• 必须在更新f[k][i][j]之前计算最小环，因为此时f[i][j]仍保持着 “只允许经过 1~k-1” 的状态；
• 原始边权数组w需要单独保存，不能被 Floyd 更新覆盖，因为w[i][k]是i到k的直接边权，而非最短路径。

完整 C++ 代码

#include <iostream>
#include <cstring>
using namespace std;

const int N = 110;
const int INF = 1e8;  // 无穷大（避免溢出）

int n, m;
int f[N][N];  // Floyd数组，存储最短路径
int w[N][N];  // 原始边权数组，存储直接边权
int min_cycle = INF;  // 最小环长度

int main() {
    // 初始化f和w数组
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= N; ++j) {
            f[i][j] = w[i][j] = INF;
        }
        f[i][i] = w[i][i] = 0;
    }

    // 读入顶点数和边数
    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, d;
        cin >> u >> v >> d;
        // 无向边，双向更新，保留最小边权（避免重边）
        w[u][v] = w[v][u] = min(w[u][v], d);
        f[u][v] = f[v][u] = min(f[u][v], d);
    }

    // Floyd算法求最短路径，并同时找最小环
    for (int k = 1; k <= n; ++k) {
        // 步骤1：找包含k的最小环（k是环中最大编号顶点）
        for (int i = 1; i < k; ++i) {
            for (int j = i + 1; j < k; ++j) {
                // 环的长度 = i到j的最短路径（不经过k） + i到k的直接边 + k到j的直接边
                if (f[i][j] != INF && w[i][k] != INF && w[k][j] != INF) {
                    min_cycle = min(min_cycle, f[i][j] + w[i][k] + w[k][j]);
                }
            }
        }

        // 步骤2：正常更新Floyd数组（插入k作为中间顶点）
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                if (f[i][k] != INF && f[k][j] != INF) {
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
                }
            }
        }
    }

    // 输出结果
    if (min_cycle == INF) {
        cout << "No solution." << endl;
    } else {
        cout << min_cycle << endl;
    }

    return 0;
}

代码解释

• 单独维护w数组存储原始边权，避免被 Floyd 更新覆盖；
• 枚举k时，先找包含k的最小环（i < k、j < k确保k是环中最大编号顶点），再更新 Floyd 数组；
• 最小环的长度是i→j的最短路径（不经过k）加上i→k和k→j的直接边权，确保环的完整性和最小性。

七、Floyd 算法的优化与注意事项

1. 空间优化

Floyd 算法的空间复杂度是O(n²)，对于n=1000的场景，n²=1e6，内存占用约 4MB（int 类型），完全可以接受；但对于n=1e4，n²=1e8，内存占用约 400MB，会超出内存限制。此时可以考虑：

• 若只需查询部分顶点对的最短路径，可使用多源 Dijkstra（对每个顶点跑一次 Dijkstra）；
• 对于稀疏图，多源 Dijkstra 的时间复杂度O(n m log n)可能优于 Floyd 的O(n³)。

2. 避免溢出

• 无穷大INF的取值要合适，不能太大（否则INF + INF会溢出），也不能太小（否则会与实际边权冲突）。通常取0x3f3f3f3f（约 1e9），因为0x3f3f3f3f + 0x3f3f3f3f = 2e9，小于 int 的最大值（2^31-1=2147483647）；
• 若边权较大或顶点数较多，需用long long存储f[i][j]，避免累加和溢出。

3. 处理重边和自环

• 重边：保留权值最小的边（如w[u][v] = min(w[u][v], d)）；
• 自环：由于f[i][i] = 0，自环的边权不会影响最短路径（因为i→i的最短路径长度为 0），因此可以忽略自环（或在初始化时不处理自环）。

4. 负环的检测

Floyd 算法本身无法直接检测负环，但可以通过以下方法判断：

• 运行 Floyd 算法后，若存在f[i][i] < 0，则说明顶点i在一个负环上（因为自己到自己的最短路径长度为负数，存在负环）；
• 若只需检测是否存在负环，建议使用 Bellman-Ford 或 SPFA 算法（效率更高）。

总结

Floyd 算法是多源最短路的核心算法，代码简洁、思想巧妙，虽然时间复杂度为O(n³)，但在顶点数较小的场景（n ≤ 200）中效率很高，且能处理有向图、无向图、带权图（非负权或负权无负环）等多种情况。 Floyd 算法虽然简单，但蕴含的动态规划思想和 “插点法” 技巧值得深入思考。希望通过本文的学习，你能彻底掌握多源最短路问题，并能灵活应对各类实战场景！如果有任何疑问或问题，欢迎在评论区交流讨论～