Floyd 算法#

算法概述#

Floyd算法是一种多源最短路径算法，用于求解图中任意两个节点之间的最短路径。该算法基于动态规划，通过不断在路径中插入中间节点来更新最短路径，因此也被称为插点法。

适用条件#

· 适用于任何图（有向图、无向图、带权图） · 要求不存在负环（但可以处理负权边） · 最短路必须存在

核心思想#

状态定义

设 f[k][i][j] 表示经过编号不超过 k 的节点，从节点 i 到节点 j 的最短路径长度。

状态转移方程

对于每个中间节点 k，考虑两种情况：

1
1. 不经过节点 k：f[k][i][j] = f[k-1][i][j]
2

3
2. 经过节点 k：f[k][i][j] = f[k-1][i][k] + f[k-1][k][j]
4

5

6
取两者最小值：f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j]

空间优化#

实际实现中省略第一维，使用二维数组迭代更新

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

代码实现#

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5

6
const int N = 210;  // 根据题目调整大小
7
const int INF = 0x3f3f3f3f;
8
int f[N][N];
9
int n, m;
10

11
int main() {
12
    cin >> n >> m;
13

14
    // 初始化
15
    memset(f, 0x3f, sizeof f);
16
    for (int i = 1; i <= n; i++) {
17
        f[i][i] = 0;  // 自己到自己的距离为0
18
    }
19

20
    // 读入边
21
    for (int i = 1; i <= m; i++) {
22
        int a, b, c;
23
        cin >> a >> b >> c;
24
        f[a][b] = f[b][a] = min(f[a][b], c);  // 处理重边，选择最小边
25
    }
26

27
    // Floyd算法核心
28
    for (int k = 1; k <= n; k++) {
29
        for (int i = 1; i <= n; i++) {
30
            for (int j = 1; j <= n; j++) {
31
                if (f[i][k] != INF && f[k][j] != INF) {  // 防止溢出
32
                    f[i][j] = min(f[i][j], f[i][k] + f[k][j]);
33
                }
34
            }
35
        }
36
    }
37

38
    // 输出结果
39
    for (int i = 1; i <= n; i++) {
40
        for (int j = 1; j <= n; j++) {
41
            if (f[i][j] == INF) {
42
                cout << "INF ";
43
            } else {
44
                cout << f[i][j] << " ";
45
            }
46
        }
47
        cout << endl;
48
    }
49

50
    return 0;
51
}

三维

1
#include <iostream>
2
#include <cstring>
3
#include <algorithm>
4
using namespace std;
5

6
const int N = 210;  // 根据题目调整大小
7
const int INF = 0x3f3f3f3f;
8
int f[N][N][N];
9
int n, m;
10

11
int main() {
12
    cin >> n >> m;
13

14
    // 初始化
15
    memset(f, 0x3f, sizeof f);
16

17
    // 初始化k=0的情况（不经过任何中间点）
18
    for (int i = 1; i <= n; i++) {
19
        for (int j = 1; j <= n; j++) {
20
            if (i == j) {
21
                f[0][i][j] = 0;  // 自己到自己的距离为0
22
            }
23
        }
24
    }
25

26
    // 读入边（初始化k=0的直接路径）
27
    for (int i = 1; i <= m; i++) {
28
        int a, b, c;
29
        cin >> a >> b >> c;
30
        f[0][a][b] = min(f[0][a][b], c);  // 处理重边
31
        f[0][b][a] = min(f[0][b][a], c);  // 无向图
32
    }
33

34
    // Floyd算法核心（三维版本）
35
    for (int k = 1; k <= n; k++) {
36
        for (int i = 1; i <= n; i++) {
37
            for (int j = 1; j <= n; j++) {
38
                // 状态转移：经过前k个点 = min(经过前k-1个点, 经过第k个点)
39
                if (f[k-1][i][k] != INF && f[k-1][k][j] != INF) {
40
                    f[k][i][j] = min(f[k-1][i][j], f[k-1][i][k] + f[k-1][k][j]);
41
                } else {
42
                    f[k][i][j] = f[k-1][i][j];
43
                }
44
            }
45
        }
46
    }
47

48
    // 输出结果（使用经过所有n个点的结果）
49
    for (int i = 1; i <= n; i++) {
50
        for (int j = 1; j <= n; j++) {
51
            if (f[n][i][j] == INF) {
52
                cout << "INF ";
53
            } else {
54
                cout << f[n][i][j] << " ";
55
            }
56
        }
57
        cout << endl;
58
    }
59

60
    return 0;
61
}

时空复杂度#

时间复杂度 · O(n³)，其中 n 为节点数 · 三重循环：k → i → j

空间复杂度 · O(n²)，使用二维数组存储距离矩阵

通过数学归纳法证明算法正确性：

· 基础：k=0时，f[i][j]为直接边权值 · 归纳：假设已知前k-1个节点时的最短路径，加入第k个节点时，要么不经过k，要么经过k

注意事项#

初始化要点： · 对角线元素初始化为0 · 有边连接的点初始化为边权值 · 无边连接的点初始化为无穷大

重边处理：

1
f[a][b] = min(f[a][b], c);  // 取最小边权

负权边处理： · 可以处理负权边 · 但不能处理负环（会陷入无限循环）

无穷大判断：

1
if (f[i][k] != INF && f[k][j] != INF) {
2
    // 防止整数溢出
3
}

应用场景#

任意两点间最短路径问题
传递闭包计算
最小环检测
图的连通性判断

音乐

音乐