Appearance
Floyd 算法
五行代码解决多源最短路径
Floyd 算法的核心只有五行代码（三重循环 + 一个 if），却能求出图中任意两点间的最短路径。这种"暴力美学"背后是动态规划的精髓——逐步扩大允许经过的中转顶点集合。
Floyd 算法是 408 考研中多源最短路径问题的首选算法。相比对每个顶点分别执行一次 Dijkstra（时间复杂度同为 O(V³)），Floyd 代码更简洁，且能处理负权边。
核心思想
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 在最外层。如果把 k 放在内层（如 i-j-k），算法就是错的——因为松弛 dist[i][j] 时，dist[i][k] 和 dist[k][j] 可能尚未被当前轮次更新到最优值。这是 408 选择题的经典陷阱。
k = 0（以 v0 为中转）：
检查所有 (i, j)（跳过 i=0 或 j=0 或 i=j 的情况），看 dist[i][0] + dist[0][j] 是否小于 dist[i][j]：
- dist[1][2]：dist[1][0]+dist[0][2] = ∞+∞ = ∞ >= 4，不更新
- dist[1][3]：dist[1][0]+dist[0][3] = ∞+7 = ∞ >= ∞，不更新
- dist[2][1]：dist[2][0]+dist[0][1] = 3+5 = 8 < ∞，更新 dist[2][1] = 8
- dist[2][3]：dist[2][0]+dist[0][3] = 3+7 = 10 > 2，不更新
- dist[3][1]：dist[3][0]+dist[0][1] = ∞+5 = ∞ >= ∞，不更新
- dist[3][2]：dist[3][0]+dist[0][2] = ∞+∞ = ∞ >= 1，不更新
k=0 后的 dist 矩阵：
| v0 | v1 | v2 | v3 | |
|---|---|---|---|---|
| v0 | 0 | 5 | ∞ | 7 |
| v1 | ∞ | 0 | 4 | ∞ |
| v2 | 3 | 8 | 0 | 2 |
| v3 | ∞ | ∞ | 1 | 0 |
k = 1（以 v1 为中转）：
检查所有 (i, j)（跳过 i=1 或 j=1 或 i=j）：
- dist[0][2]：dist[0][1]+dist[1][2] = 5+4 = 9 < ∞，更新 dist[0][2] = 9
- dist[0][3]：dist[0][1]+dist[1][3] = 5+∞ = ∞ >= 7，不更新
- dist[2][0]：dist[2][1]+dist[1][0] = 8+∞ = ∞ >= 3，不更新
- dist[2][3]：dist[2][1]+dist[1][3] = 8+∞ = ∞ >= 2，不更新
- dist[3][0]：dist[3][1]+dist[1][0] = ∞+∞ = ∞ >= ∞，不更新
- dist[3][2]：dist[3][1]+dist[1][2] = ∞+4 = ∞ >= 1，不更新
k=1 后的 dist 矩阵：
| v0 | v1 | v2 | v3 | |
|---|---|---|---|---|
| v0 | 0 | 5 | 9 | 7 |
| v1 | ∞ | 0 | 4 | ∞ |
| v2 | 3 | 8 | 0 | 2 |
| v3 | ∞ | ∞ | 1 | 0 |
k = 2（以 v2 为中转）：
检查所有 (i, j)（跳过 i=2 或 j=2 或 i=j）：
- dist[0][1]：dist[0][2]+dist[2][1] = 9+8 = 17 >= 5，不更新
- dist[0][3]：dist[0][2]+dist[2][3] = 9+2 = 11 >= 7，不更新
- dist[1][0]：dist[1][2]+dist[2][0] = 4+3 = 7 < ∞，更新 dist[1][0] = 7
- dist[1][3]：dist[1][2]+dist[2][3] = 4+2 = 6 < ∞，更新 dist[1][3] = 6
- dist[3][0]：dist[3][2]+dist[2][0] = 1+3 = 4 < ∞，更新 dist[3][0] = 4
- dist[3][1]：dist[3][2]+dist[2][1] = 1+8 = 9 < ∞，更新 dist[3][1] = 9
k=2 后的 dist 矩阵：
| v0 | v1 | v2 | v3 | |
|---|---|---|---|---|
| v0 | 0 | 5 | 9 | 7 |
| v1 | 7 | 0 | 4 | 6 |
| v2 | 3 | 8 | 0 | 2 |
| v3 | 4 | 9 | 1 | 0 |
k = 3（以 v3 为中转）：
检查所有 (i, j)（跳过 i=3 或 j=3 或 i=j）：
- dist[0][1]：dist[0][3]+dist[3][1] = 7+9 = 16 >= 5，不更新
- dist[0][2]：dist[0][3]+dist[3][2] = 7+1 = 8 < 9，更新 dist[0][2] = 8
- dist[1][0]：dist[1][3]+dist[3][0] = 6+4 = 10 >= 7，不更新
- dist[1][2]：dist[1][3]+dist[3][2] = 6+1 = 7 >= 4，不更新
- dist[2][0]：dist[2][3]+dist[3][0] = 2+4 = 6 >= 3，不更新
- dist[2][1]：dist[2][3]+dist[3][1] = 2+9 = 11 >= 8，不更新
k=3 后的最终 dist 矩阵：
| v0 | v1 | v2 | v3 | |
|---|---|---|---|---|
| v0 | 0 | 5 | 8 | 7 |
| v1 | 7 | 0 | 4 | 6 |
| v2 | 3 | 8 | 0 | 2 |
| v3 | 4 | 9 | 1 | 0 |
最终 dist[][] 矩阵存储了所有顶点对之间的最短距离。通过 path[][] 矩阵可逆向回溯出具体路径。
复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间复杂度 | O(V³) | 三重循环，每层 V 次 |
| 空间复杂度 | O(V²) | dist[][] 和 path[][] 各占 V² |
适用条件：
- 可处理负权边（Dijkstra 不行）
- 不能有负权回路（否则最短路径无意义，会无限减小）
- 既适用于有向图，也适用于无向图
易错：Floyd 能处理负权边但不能处理负权回路。如果存在负权回路，最短路径可以无限减小（绕一圈路径变短，再绕一圈更短...），此时最短路径无意义。判断方法：如果算法结束后存在 dist[i][i] < 0，则说明存在负权回路。
考研高频考点
- ⭐ 三重循环的顺序：k 必须在最外层，i、j 在内层（选择题高频陷阱）
- ⭐ 手动模拟 dist[][] 矩阵的逐步更新过程（大题常考）
- ⭐ Floyd vs Dijkstra 对比：Floyd 求多源最短路径，Dijkstra 求单源最短路径
- ⭐ 负权边的处理能力：Floyd 可处理负权边，但不能有负权回路
- ⭐ 时间复杂度 O(V³)、空间复杂度 O(V²)（填空题）
- path[][] 矩阵的含义与路径回溯方法（偶尔考）