CC++ & Algorithm

全源最短路——Floyd-Warshall

较难5
语言版本：C++
概述：Floyd-Warshall算法像是一个“城市地图制作器”，一次性算出所有路口两两之间的最短距离。

Floyd-Warshall算法：一张表格搞定所有路口的最短距离

为什么我们需要“全源最短路”？

同学们，我们之前学了从一个起点出发找最短路径（比如用Dijkstra算法）。但是，假如你是一个城市规划师，需要知道任意两个路口之间开车的最短距离，该怎么办？是不是要把每个路口都当成起点，跑一遍单源最短路？那样的话，如果城市里有100个路口，就得跑100次，太累了！而且在CSP-S题目中，时间可能不够。

这时候，Floyd-Warshall算法就登场了。它就像一个“城市地图制作器”——只用一次计算，就能得到所有点对之间的最短距离。它的核心想法很简单：尝试让每个路口都变成“中转站”，看看走中转站会不会比直接走更近。如果更近，就更新距离。就像你在玩一个游戏，地图上有很多传送门，你不断发现新的传送门组合，让旅行越来越快。

算法的核心：把每个点当一次“万能中转站”

假设我们有4个路口（编号0、1、2、3），一开始我们只知道直接相连的道路长度（如果没有路，距离就是无穷大INF）。比如0→1距离3，0→3距离7；1→2距离2等等。但直接走不一定是最短——也许从0到1先经过2会更近？不知道，我们还没试。

Floyd算法的思路是：逐一考虑每个路口k，看看能不能用它当“中转站”，然后更新所有其他点对(i, j)的距离。

举个生活中的例子：你想从你家（路口i）到朋友家（路口j）。如果直接走有10公里，但你知道先到学校（路口k）找小明，再从小明家去朋友家，总共只要8公里，那你会选择经过学校。Floyd算法就是让每一个路口都充当一次“学校”，检查所有可能的“经停点组合”。

三重循环，每个变量到底在干吗？

Floyd的代码只有三层循环，但顺序非常重要。我们来看一个带注释的版本：

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

int main() {
    const int N = 4;  // 路口数量（节点数）
    
    // 邻接矩阵，dist[i][j] 表示从 i 到 j 的当前最短距离
    // 0 表示自身到自身，INT_MAX 表示还没有找到通路
    int dist[N][N] = {
        {0, 3, INT_MAX, 7},   // 从路口0出发：到1是3，到3是7，到2不通
        {8, 0, 2, INT_MAX},   // 从路口1出发：到0是8，到2是2，到3不通
        {5, INT_MAX, 0, 1},   // 从路口2出发：到0是5，到3是1，到1不通
        {2, INT_MAX, INT_MAX, 0} // 从路口3出发：到0是2，其他都不通
    };

    // Floyd-Warshall：三重循环
    // k 是当前允许使用的中转站编号
    for (int k = 0; k < N; ++k) {
        // i 是起点，j 是终点
        for (int i = 0; i < N; ++i) {
            for (int j = 0; j < N; ++j) {
                // 如果 i→k 和 k→j 都通，并且走 k 中转比原来更短
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出结果
    cout << "所有路口间最短距离（INF表示不可达）:\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (dist[i][j] == INT_MAX) 
                cout << "INF\t";  // 不可达
            else 
                cout << dist[i][j] << "\t";
        }
        cout << "\n";
    }
    return 0;
}

运行结果会是一张4×4的表格，告诉你任意两个路口之间的最短距离。你可以自己算一算：比如0→2最短是几？直接走不通，但可以0→1→2（3+2=5）或0→3→2（7+1=8），所以答案是5。

为什么循环顺序必须是 k 在最外层？

很多新手第一次写Floyd时，会把循环顺序写成 for i ... for j ... for k ...，结果发现答案不对。这是因为：

  • k 是最外层，意味着我们逐步放开中转站：最开始不允许任何中转（只走直接路），然后允许用0号路口中转，接着允许用0和1号路口中转……最后允许用所有路口中转。
  • 如果k放在最内层，比如for i for j for k，那么对于同一对(i,j)，我们会尝试所有k，但此时其他对(i,k)和(k,j)可能还没有更新到最新的最优值，导致结果不正确。

你可以想象成做一道菜：先放盐，再放酱油，味道才均匀。如果顺序乱了，菜就不好吃了。

生活中的例子：学校社团联络网

假设学校有三个社团：篮球社（A）、音乐社（B）、编程社（C）。你想知道任意两个社团之间最快传递一个消息需要多久。已知：

  • 篮球社到音乐社：直接找会长需要5分钟（但可以通过编程社转达？）
  • 篮球社到编程社：直接需要3分钟
  • 编程社到音乐社：直接需要1分钟

Floyd算法会这样算：

  1. 一开始，A→B=5，A→C=3，C→B=1（B→C未知，假设很大）。
  2. 考虑中转站C：A→C→B = 3+1=4 < 5，所以更新A→B为4。
  3. 最后得到所有对的答案。

你看，通过一个中间社团，消息能更快传递——这就是Floyd的“中转站”思想。

常见错误和避坑指南

1. 忘记初始化自身距离为0，其他为INF

如果dist[i][i]不设为0，自己到自己的距离变成无穷大，后续更新会出问题。

2. 用 INT_MAX 表示无穷大，但相加时溢出

比如 dist[i][k] + dist[k][j]，如果两者都是INT_MAX，相加会变成负数，导致比较时误以为更短。所以更新前一定要判断两边都不是INT_MAX。

3. 循环顺序写错

如上面所述，必须 k 在最外层，不能搞混。

4. 图是有向图还是无向图？

上面的例子是有向图（边有方向）。如果是无向图，邻接矩阵要对称赋初值。但Floyd算法的代码不需要改，只要初始矩阵正确就行。

5. 节点编号从0开始还是从1开始？

代码里用0N-1，如果你习惯1N，要小心数组下标对齐。通常按0开始更方便。

完整可运行代码（带更多注释）

下面是一个更完整的示例，包含输入输出和注释，你可以直接复制运行。

#include <iostream>
#include <climits>      // 包含 INT_MAX
using namespace std;

int main() {
    const int N = 4;    // 节点数量，可以自己改成其他数字
    // 初始化距离矩阵，0表示自身，INT_MAX表示不通
    int dist[N][N] = {
        {0, 3, INT_MAX, 7},
        {8, 0, 2, INT_MAX},
        {5, INT_MAX, 0, 1},
        {2, INT_MAX, INT_MAX, 0}
    };

    // Floyd-Warshall 核心代码
    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 都可达，且经过k更短，则更新
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 输出距离矩阵
    cout << "所有点对之间的最短距离（INF表示不可达）：\n";
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (dist[i][j] == INT_MAX) 
                cout << "INF\t";
            else 
                cout << dist[i][j] << "\t";
        }
        cout << "\n";
    }
    return 0;
}

你可以修改N和dist数组，测试不同图。比如试着把INT_MAX改成9999（自己定义一个大数），但要注意加法不能溢出。

算法的时间复杂度与适用场景

Floyd算法的时间复杂度是 O(n³)，其中 n 是节点数。这意味着如果节点数超过500（比如1000个点），运算次数达到10亿次，在CSP-S中可能会超时。因此，Floyd适合节点数较少（一般≤400）且需要所有点对距离的题目。

如果节点很多，你可以考虑：

  • 用Johnson算法（稀疏图，用Dijkstra+Bellman-Ford优化）
  • 或者对于稠密图用多次Dijkstra（堆优化后 O(n m log n) 但n太大仍慢）

总结与延伸

Floyd-Warshall算法就像一张“万能地图”，用简单的三重循环把城市里所有路口之间的最短路径都算清楚。它的代码短、思路直观，是CSP-S图论题的“老朋友”。

学完Floyd后，你可以去了解：

  • Dijkstra算法：单源最短路，非负权重。
  • Bellman-Ford算法：单源最短路，可以处理负权边，还能判断负环。
  • Johnson算法：全源最短路，适用于稀疏图，结合了Dijkstra和Bellman-Ford。

如果你还想知道“最短路径具体是哪条路”，Floyd可以额外维护一个 next[i][j] 数组来记录中转点，感兴趣的可以自己查一查“路径记录”。

记住：Floyd不是最快的，但它是最简单的**——当你看到题目里“n ≤ 300”时，可以毫不犹豫地掏出Floyd！

例题精讲

1单选题

在Floyd-Warshall算法中，动态规划的状态定义通常是什么？

Adp[i][j]表示从i到j经过若干中间节点的最短路径长度
Bdp[i][j]表示从i到j经过恰好k个中间节点的最短路径长度
Cdp[k][i][j]表示从i到j经过的中间节点编号不超过k的最短路径长度
Ddp[k][i][j]表示从i到j经过恰好k个中间节点的最短路径长度
2判断题

Floyd-Warshall算法可以正确处理图中存在负权边的情况，但如果图中存在负环，算法仍能正常运行并输出正确结果。

3填空题
下面是Floyd-Warshall算法的核心代码片段，请补全if语句中的赋值语句。

for(int k = 1; k <= n; k++) {
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            if(dist[i][k] + dist[k][j] < dist[i][j]) {
                ___
            }
        }
    }
}
4单选题

下列关于Floyd-Warshall算法时间复杂度的说法，正确的是？

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

使用邻接矩阵存储图并初始化Floyd-Warshall算法时，通常将dist[i][i]设为0，将dist[i][j]（i≠j）设为无穷大（INF），这是正确的初始化方式。