弗洛伊德算法 (Floyd-Warshall) 详解
1. 算法核心思想
Floyd 算法本质上是 动态规划 (Dynamic Programming)。
核心问题：从顶点 $i$ 到顶点 $j$，如果我们允许经过一些中转点，最短路径是多少？
1.1 状态定义
我们定义 $dp[k][i][j]$ 为：
“只允许使用节点 $1$ 到 $k$ 作为中转节点的情况下，从 $i$ 到 $j$ 的最短路径长度。”
1.2 状态转移方程（核心逻辑）
当我们要计算允许使用节点 $1...k$ 的最短路时，我们有两种选择：
- 不经过节点 $k$：如果不使用 $k$ 做中转，那么最短路径就等于“只允许使用 $1...k-1$”时的路径。即：$dp[k-1][i][j]$。
- 经过节点 $k$：如果我们利用 $k$ 做中转，那么路径就变成了 $i \to k \to j$。这条路的长度是：$dp[k-1][i][k] + dp[k-1][k][j]$。
结论：我们要在这两者中取最小值。
1.3 空间优化（降维打击）
就像背包问题一样，因为第 $k$ 阶段的状态只依赖于 $k-1$ 阶段，我们可以把第一维 $k$ 去掉，直接在二维数组上通过“滚动更新”来实现：
这就是著名的 Floyd 松弛操作。
2. 算法步骤与初始状态
2.1 初始化矩阵
我们需要一个二维数组（邻接矩阵） dist[N][N]。
- 对角线：
dist[i][i] = 0 （自己到自己距离为0）。
- 有边相连：
dist[i][j] = weight。
- 无边相连：
dist[i][j] = INF （表示不可达）。
2.2 三重循环（核心代码）
Floyd 的代码几乎是所有图论算法中最短的，但也是最容易写错循环顺序的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
|
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
}
}
}
}
````
### 2.3 为什么 k 必须在最外层？（常见考点）
- **动态规划的阶段性**：$k$ 代表的是 DP 的**阶段**。
- 如果不把 $k$ 放在最外层，意味着我们在计算 $i \to j$ 时，只尝试了某一个特定的中转点，而没有利用“之前已经计算好的、利用了其他中转点的最短路”。
- **简言之**：$k=1$ 循环结束时，保证了图中任意两点间只经过节点 1 的最短路被找到了；$k=2$ 结束时，保证了只经过 1 和 2 的最短路被找到了……直到 $k=n$。
---
## 3. C++ 代码实现 (包含路径还原)
如果在你的航班系统中，你不仅想知道从“北京”到“纽约”的最短时间，还想知道中间要在哪转机，我们就需要维护一个 `path` 矩阵。
### 3.1 路径记录原理
定义 `path[i][j]`：从 $i$ 到 $j$ 的最短路径上，**$i$ 的下一个节点是谁**（或者 $j$ 的前驱是谁，这里我们用后继节点法）。
- 初始化：如果 $i, j$ 直连，`path[i][j] = j`。
- 更新时：如果 $i \to k \to j$ 更短，那么从 $i$ 去 $j$ 的第一步，就变成了“从 $i$ 去 $k$ 的第一步”，即 `path[i][j] = path[i][k]`。
### 3.2 完整代码模板
C++
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
const int INF = 1e9;
void printPath(int u, int v, const vector<vector<int>>& path) {
cout << u;
while (u != v) {
u = path[u][v];
cout << " -> " << u;
}
cout << endl;
}
void floydWarshall(int n, vector<vector<int>>& dist, vector<vector<int>>& path) {
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] != INF && dist[k][j] != INF &&
dist[i][j] > dist[i][k] + dist[k][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[i][k];
}
}
}
}
}
int main() {
int n = 4, m = 6;
vector<vector<int>> dist(n + 1, vector<int>(n + 1, INF));
vector<vector<int>> path(n + 1, vector<int>(n + 1, 0));
for(int i = 1; i <= n; i++) dist[i][i] = 0;
vector<tuple<int, int, int>> edges = {
{1, 2, 2}, {1, 4, 6}, {2, 3, 3}, {2, 4, 2}, {3, 1, 7}, {3, 4, 1}
};
for (auto [u, v, w] : edges) {
dist[u][v] = w;
path[u][v] = v;
}
floydWarshall(n, dist, path);
cout << "Shortest path from 1 to 3:" << endl;
cout << "Cost: " << dist[1][3] << endl;
cout << "Path: ";
printPath(1, 3, path);
return 0;
}
|
4. 算法分析与适用场景
4.1 复杂度
时间复杂度：$O(N^3)$。
空间复杂度：$O(N^2)$，用于存储邻接矩阵。
4.2 优点
代码极其简单：容易记忆，不容易写出 Bug。
多源最短路：跑一次，查表即可知道任意两点距离。
处理负权边：可以处理边权为负的情况（Dijkstra 不行）。
检测负权环：如果跑完算法后，发现某个点 dist[i][i] < 0，说明图中存在负权回路（转了一圈回来距离变小了），此时最短路不存在。
4.3 缺点
慢：对于大规模稀疏图，不如跑 $N$ 次 Dijkstra（后者是 $O(N \cdot E \log N)$）。
无法处理负权环：虽然能检测，但如果有负权环，数值会一直变小，无解。
4.4 你的项目中该怎么选？
