Appearance
Floyd 算法
为什么需要Floyd 算法
Dijkstra 算法一次只能求出一个源点到其余顶点的最短路径。如果要求图中任意两点之间的最短路径，需要对每个顶点分别执行一次 Dijkstra，时间复杂度为 O(V³)（邻接矩阵实现）。
Floyd 算法用动态规划的思想，通过一段简洁的三重循环，直接求出所有顶点对之间的最短路径。代码短、易实现，是 408 考研中多源最短路径问题的首选算法。
核心思想
Floyd 算法的核心是逐步引入中转顶点：
- 维护一个距离矩阵
dist[i][j]，表示从顶点 i 到顶点 j 的当前最短路径长度 - 依次考虑以顶点 0, 1, 2, …, V-1 作为中转点，尝试松弛每一对 (i, j) 之间的距离
- 松弛条件：若
dist[i][k] + dist[k][j] < dist[i][j]，则更新dist[i][j]
状态转移方程：
dist(k)[i][j] = min( dist(k-1)[i][j], dist(k-1)[i][k] + dist(k-1)[k][j] )其中 dist(k)[i][j] 表示仅允许经过顶点 0 ~ k 作为中转时，i 到 j 的最短路径长度。
交互可视化
通过下方的交互动画，你可以逐步观察Floyd 算法的执行过程：
操作详解
算法思路
- 初始化：将邻接矩阵复制到
dist[][]，若 i 与 j 之间无边则置为 ∞，dist[i][i] = 0 - 三重循环：最外层枚举中转顶点 k，内两层枚举所有顶点对 (i, j)
- 松弛操作：若经过 k 中转能缩短 i→j 的距离，则更新
dist[i][j] - 路径记录：用辅助矩阵
path[i][j]记录 i→j 最短路径上 j 的前驱顶点，便于回溯完整路径
c
#define V 4
#define INF 0x3f3f3f3f
int dist[V][V]; // 最短距离矩阵
int path[V][V]; // 前驱矩阵，用于记录路径
// 初始化
void init(int graph[V][V]) {
for (int i = 0; i < V; i++)
for (int j = 0; j < V; j++) {
dist[i][j] = graph[i][j];
if (i != j && graph[i][j] < INF)
path[i][j] = i; // j 的前驱为 i
else
path[i][j] = -1; // 无路径
}
}
// Floyd 核心算法
void floyd() {
for (int k = 0; k < V; k++) // 枚举中转顶点
for (int i = 0; i < V; i++) // 枚举起点
for (int j = 0; j < V; j++) // 枚举终点
if (dist[i][k] + dist[k][j] < dist[i][j]) {
dist[i][j] = dist[i][k] + dist[k][j];
path[i][j] = path[k][j]; // 更新前驱
}
}执行过程详解
以一个 4 顶点有向图为例，初始邻接矩阵如下（∞ 表示不可达）：
| v0 | v1 | v2 | v3 | |
|---|---|---|---|---|
| v0 | 0 | 5 | ∞ | 7 |
| v1 | ∞ | 0 | 4 | ∞ |
| v2 | 3 | ∞ | 0 | 2 |
| v3 | ∞ | ∞ | 1 | 0 |
k = 0（以 v0 为中转）：检查所有 (i, j)，看经过 v0 中转是否更短。例如 dist[2][1] = min(∞, dist[2][0]+dist[0][1]) = min(∞, 3+5) = 8，更新。
k = 1（以 v1 为中转）：例如 dist[0][2] = min(∞, dist[0][1]+dist[1][2]) = min(∞, 5+4) = 9，更新。
k = 2（以 v2 为中转）：例如 dist[0][3] = min(7, dist[0][2]+dist[2][3]) = min(7, 9+2) = 7，不更新；dist[1][3] = min(∞, 4+2) = 6，更新。
k = 3（以 v3 为中转）：例如 dist[0][2] = min(9, dist[0][3]+dist[3][2]) = min(9, 7+1) = 8，更新。
最终 dist[][] 矩阵存储了所有顶点对之间的最短距离。通过 path[][] 矩阵可逆向回溯出具体路径。
复杂度分析
- 三重循环：k、i、j 各遍历 V 次，循环体为 O(1) 的比较与赋值
- 因此时间复杂度为 O(V³)，与顶点数的立方成正比
- 空间上需要
dist[][]和path[][]两个 V×V 矩阵
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V³) | 三重循环，每层 V 次 |
| 空间复杂度 | O(V²) | dist[][] 和 path[][] 各占 V² |
适用条件：
- 可处理负权边（Dijkstra 不行）
- 不能有负权回路（否则最短路径无意义，会无限减小）
- 既适用于有向图，也适用于无向图
考研高频考点
- ⭐ 三重循环的顺序：k 必须在最外层，i、j 在内层（选择题高频陷阱）
- ⭐ 手动模拟 dist[][] 矩阵的逐步更新过程（大题常考）
- ⭐ Floyd vs Dijkstra 对比：Floyd 求多源最短路径，Dijkstra 求单源最短路径
- ⭐ 负权边的处理能力：Floyd 可处理负权边，但不能有负权回路
- ⭐ 时间复杂度 O(V³)、空间复杂度 O(V²)（填空题）
- path[][] 矩阵的含义与路径回溯方法（偶尔考）