CC++ & Algorithm

C++最短路径 Floyd 算法

较难7
语言版本：C++Python
概述：一次性算出所有城市对之间的最短路线，像查地图册

地图册里的超级计算器：C++ Floyd 算法一次算出所有城市最短路线

你有没有打开过地图软件，输入任意两个城市，就能看到最短距离？Floyd 算法就是帮计算机做这件事的“超级算力”——它用一套方法，一次性算出所有城市对之间的最短路径。就像你有一本地图册，上面只标了部分直接相连的城市距离，而 Floyd 能帮你补上所有“中转”后的最短距离。

?️ 生活中的例子

你有一本地图册，上面标着所有城市之间的距离（有些直接相连，有些需要中转）。你想知道任意两个城市之间最短的路线，包括那些需要经过好几个城市中转的。Floyd 算法就像一位“超级规划师”，它通过一遍遍尝试“如果经过某个中间城市会不会更近”，最终在一天内为你算出所有城市对的最短距离。

比如说，你家住在北京（城市0），想去深圳（城市3），但地图上只标了北京到上海（城市1）5公里、上海到广州（城市2）3公里、广州到深圳1公里，而北京到深圳直接距离10公里。Floyd 算法会先让上海当“中间人”：北京→上海→广州只要8公里，比5+? 等等，这里需要多步中转。实际上算法会逐次尝试所有可能的中间站，最终发现北京→上海→广州→深圳一共9公里，比直接10公里近，于是更新。

? 核心思想：不断邀请新中间人

  • 最初，你只知道每一对城市直接相连的距离，中间隔一个城市的路程还不清楚。
  • 算法安排每个城市轮流当“中间人”（中转站）。对于每对城市 i 和 j，尝试让 k 当中间人：i → k → j。
  • 如果这条路比之前记录的 i → j 更短，就更新记录。
  • 等所有人都当过中间人后，所有城市对的最短距离就确定好了。这个过程叫做动态规划，因为它把小问题（经过部分中间站）的结果逐步拼成大问题。

? 算法步骤（逐层递进）

  1. 画一张初始表格
    用二维数组 dist 存当前已知的最短距离。规则：

    • 自己到自己是 0。
    • 如果两个城市直接相连，填上直接距离。
    • 如果不直接相连，填上一个很大的数（用 INF 表示“暂时不通”）。

  2. 让城市 0 当中间人
    检查每一对城市 (i, j)，看看 i → 0 → j 是否比 i → j 更短。如果是，就更新 dist[i][j]。

  3. 让城市 1 当中间人
    同样检查所有 (i, j)，但注意：现在 dist[i][j] 已经是“可能经过城市0”的最短距离了。再尝试经过城市1，可能又发现更短的路径。

  4. 依次让城市 2、3、… 当中间人
    重复直到所有城市都当过中间人。最终 dist 里存的就是任意两点之间的最短距离。

用数学语言描述：dist[k][i][j] 表示只允许经过前 k 个城市（编号0到k-1）时 i 到 j 的最短距离。代码里我们把 k 这层维度压缩了，直接在原数组上更新。

? 关键概念 + 例子 + 代码

1. 初始化距离矩阵

const int INF = INT_MAX;          // 表示“不通”
int n = 4;                        // 城市数量
vector<vector<int>> dist = {      // 距离矩阵，dist[i][j] 表示 i 到 j 的当前最短距离
    {0,   5,   INF, 10},          // 城市0到0:0, 到1:5, 到2:不通, 到3:10
    {INF, 0,   3,   INF},         // 城市1到0:不通, 到1:0, 到2:3, 到3:不通
    {INF, INF, 0,   1},           // 城市2到0:不通, 到1:不通, 到2:0, 到3:1
    {INF, INF, INF, 0}            // 城市3到0:不通, 到1:不通, 到2:不通, 到3:0
};

2. 三重循环：每个城市当中间人

for (int k = 0; k < n; k++) {             // k：当前让 k 当中间人
    for (int i = 0; i < n; i++) {         // i：起点
        for (int j = 0; j < n; j++) {     // j：终点
            if (dist[i][k] != INF &&      // 确保能从 i 到 k
                dist[k][j] != INF &&      // 确保能从 k 到 j
                dist[i][k] + dist[k][j] < dist[i][j]) {  // 更短就更新
                dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }
}

3. 手动模拟第一轮（k=0）

  • 检查 i=1, j=2：dist[1][0] 是 INF，跳过。
  • 检查 i=3, j=2：dist[3][0] 是 INF，跳过。
  • 检查 i=1, j=3：dist[1][0] 是 INF，跳过。
  • 检查 i=0, j=2：dist[0][0]=0，dist[0][2]=INF，但 dist[0][0]+dist[0][2] 还是不通，不更新。
  • 实际上只有 dist[0][1] 和 dist[0][3] 没有变化（因为经过城市0，起点或终点就是0本身，距离不变）。

第二轮（k=1）
此时 dist[0][1]=5, dist[1][2]=3，所以 dist[0][1] + dist[1][2] = 8 < dist[0][2](INF) → 更新 dist[0][2] = 8。
同样，dist[0][1] + dist[1][3] 虽然 dist[1][3] 是 INF，不更新。
dist[3][1] 是 INF，所以 dist[3][2] 没变。

第三轮（k=2）
现在 dist[0][2]=8, dist[2][3]=1，得到 dist[0][2] + dist[2][3] = 9 < dist[0][3](10) → 更新 dist[0][3] = 9。
同时 dist[1][2]=3, dist[2][3]=1 得到 dist[1][3]=4（原来 INF）。
还可以继续更新其他对。

最终 dist[0][3] 从 10 变成了 9，这就是北京到深圳的最短路线（北京→上海→广州→深圳）。

⚠️ 新手最容易犯的四个错误

  1. 忘记把自己到自己的距离设为 0
    如果初始化时写 dist[i][i] = INF，那么自己到自己的距离会变成无穷大，后面更新时还会算上自己绕一圈，导致错误。

  2. 三重循环的顺序写错了
    必须是 k 在最外层，i、j 在内层。如果写成 i 在最外层，结果就不对了。因为 Floyd 依赖“逐步引入新中间点”的顺序，不能跳跃。

  3. 没有检查 INF 就做加法
    如果 dist[i][k] 或 dist[k][j] 是 INF，直接加会得到一个大数（比如 INT_MAX + 5），轻则溢出为负数，重则程序崩溃。一定要先判断不是 INF。

  4. 城市编号从 0 开始，但误以为从 1 开始
    很多同学喜欢用 for(int i=1; i<=n; i++)，但数组下标从0开始，会导致越界或漏掉城市。要统一。

? 完整可运行代码（带中文注释）

#include <iostream>
#include <vector>
#include <climits>        // 使用 INT_MAX
using namespace std;

const int INF = INT_MAX;  // 定义一个很大的数表示“不通”

// Floyd 算法：计算所有城市之间的最短距离
void floyd(vector<vector<int>> &dist) {
    int n = dist.size();  // 城市个数
    // 让每个城市依次当中间人
    for (int k = 0; k < n; k++) {          // k：中间人编号
        for (int i = 0; i < n; i++) {      // i：起点城市
            for (int j = 0; j < n; j++) {  // j：终点城市
                // 如果从 i 到 k 和从 k 到 j 都能走通，再判断总和是否更短
                if (dist[i][k] != INF && dist[k][j] != INF &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
}

int main() {
    int n = 4;                            // 4个城市，编号0~3
    vector<vector<int>> dist = {          // 初始化距离矩阵
        {0,   5,   INF, 10},              // 城市0：到0是0，到1是5，到2不通，到3是10
        {INF, 0,   3,   INF},             // 城市1：到0不通，到1是0，到2是3，到3不通
        {INF, INF, 0,   1},               // 城市2：到0不通，到1不通，到2是0，到3是1
        {INF, INF, INF, 0}                // 城市3：到所有都暂时不通（除了自己）
    };

    floyd(dist);  // 调用算法

    // 输出结果
    cout << "所有城市对的最短距离：" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (dist[i][j] == INF)
                cout << "INF ";
            else
                cout << dist[i][j] << "   ";
        }
        cout << endl;
    }
    return 0;
}

运行结果：

所有城市对的最短距离：
0   5   8   9   
INF 0   3   4   
INF INF 0   1   
INF INF INF 0

可以看到，城市0到城市3的最短距离从10变成了9，城市1到城市3也通了（4公里）。

⏱ 时间复杂度与适用范围

  • 三重循环，城市数量为 n，时间复杂度是 O(n³)。城市不多（比如 n ≤ 200）时跑得飞快，但 n=1000 时就要计算10亿次，会慢。
  • 适合稠密图（很多条路）和多源最短路（需要所有城市对）。如果只需要一个城市到其他城市的最短距离，用 Dijkstra 算法更高效。
  • Floyd 算法可以处理负权边（即距离为负数的路），但不能有负权环（一直转圈距离越来越小，就没有最短距离了）。

? 相关知识点指引

学完 Floyd，你可以继续学习：

  • Dijkstra 算法：求一个城市到其他所有城市的最短距离（单源最短路），用优先队列优化后更快。
  • Bellman-Ford 算法：同样处理单源最短路，但能检测负权环。
  • SPFA 算法：Bellman-Ford 的队列优化版，竞赛中常用。
  • 图的存储方式：邻接矩阵（像 Floyd 用的）、邻接表（更适合稀疏图）。

另外，如果你对“所有城市对之间”的问题感兴趣，还可以了解 传递闭包（用 Floyd 思想判断两点是否可达）和 最小环 问题。

? 小建议：自己动手画一个 5 个城市的小地图，把直接距离随便填，然后用 Floyd 算法手动模拟一下（拿笔在纸上算），印象会更深刻。代码写完后，试试把城市数量改成 10，看看跑起来快不快。

例题精讲

1单选题

Floyd-Warshall算法的时间复杂度是多少？

AO(n + m)
BO(n log n)
CO(n^3)
DO(n^2)
2判断题

Floyd算法能够正确检测图中是否存在负权环。

3填空题
补全以下Floyd算法核心代码：

#include <iostream>
using namespace std;
const int N = 100, INF = 1e9;
int n, m, dist[N][N];
void 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)
                    ___;  // 请填空
}
4单选题

关于Floyd算法的初始化，下列说法正确的是：

A所有dist[i][i]应该初始化为1
B不直接相连的边应初始化为INF，且dist[i][i]初始化为0
C所有dist[i][j]初始化为0
D只需将已知边赋值，其余保留随机值即可
5判断题

对于无向图，使用Floyd算法求最短路径时，只需输入上三角矩阵即可得到正确结果。