Floyd-Warshall（弗洛伊德）算法考研笔记

一、算法概述

1.1 核心思想

Floyd算法是一种多源最短路径算法，基于动态规划思想，用于求解图中任意两个顶点之间的最短路径。

核心原理： 通过逐次引入每个顶点 k 作为”中间节点”，不断更新所有顶点对 (i, j) 之间的最短路径长度。

状态转移：

初始状态 D⁰： 只允许直接路径（邻接矩阵）
第k次迭代 Dᵏ： D$i$$j$ 表示从 i 到 j 只允许经过集合 {1, 2, …, k} 中的顶点作为中间节点的最短路径长度
最终状态 Dⁿ： 任意两点间的最短路径值

1.2 算法特点

特性	描述
算法类型	多源最短路径，动态规划
时间复杂度	O(V³)，三层循环
空间复杂度	O(V²)，需存储距离矩阵和路径矩阵
适用图	有向图、无向图均可
权值限制	可处理负权边，但不能处理负权环
优点	代码简洁，一次运行得到所有顶点对最短路径
缺点	时间复杂度高，不适合顶点数很多的图

二、算法步骤详解

2.1 第一步：初始化邻接矩阵

建议： 在每个元素下方添加角标（便于路径追溯）

初始角标格式： i-j（表示从 i 到 j 的直接路径）

示例邻接矩阵 D⁰：

	a(1)	b(2)	c(3)	d(4)	e(5)	f(6)
a(1)	0	6	∞	8	∞	∞
b(2)	18	0	7	∞	∞	10
c(3)	9	∞	0	15	∞	∞
d(4)	∞	∞	12	0	∞	∞
e(5)	∞	∞	∞	∞	0	∞
f(6)	24	5	∞	25	∞	0

2.2 第二步：迭代更新

核心公式：

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

迭代规则（第k次迭代）

考察对象： 主对角线第k个元素（第k个顶点），观察对应的行和列

（1）照抄部分

主对角线第k行整行照抄
主对角线第k列整列照抄
该行列中为∞的元素，其对应的行和列也照抄
主对角线元素（0）始终不变

（2）更新部分

对于其他位置的元素 (i, j)：

比较： 原值 vs (i到k的距离 + k到j的距离)
更新规则： 取较小值
角标更新： 若更新，则合并路径角标

核心思想： 判断”i→k→j”是否比”i→j”更短

三、手动模拟示例

3.1 第一次迭代（k=1，以顶点a为中间点）

目标： 判断所有路径 (i, j) 是否可以通过 a 变得更短

关键更新：

位置(3,2)（c → b）
- 原值：∞
- 计算：D$3 $1$ + D$1$ 2$ = 9 + 6 = 15 < ∞
- 更新为：15，角标：3-1-2
位置(2,4)（b → d）
- 原值：∞
- 计算：D$2 $1$ + D$1$ 4$ = 18 + 8 = 26 < ∞
- 更新为：26，角标：2-1-4
位置(6,4)（f → d）
- 原值：25
- 计算：D$6 $1$ + D$1$ 4$ = 24 + 8 = 32 > 25
- 不更新（原值更小）

3.2 第二次迭代（k=2，以顶点b为中间点）

目标： 在D¹基础上，判断所有路径是否可以通过 b 变得更短

关键更新：

位置(6,1)（f → a）
- 原值：24
- 计算：D¹$6 $2$ + D¹$2$ 1$ = 5 + 18 = 23 < 24
- 更新为：23，角标：6-2-1
位置(6,3)（f → c）
- 原值：∞
- 计算：D¹$6 $2$ + D¹$2$ 3$ = 5 + 7 = 12 < ∞
- 更新为：12，角标：6-2-3
位置(1,3)（a → c）
- 原值：∞
- 计算：D¹$1 $2$ + D¹$2$ 3$ = 6 + 7 = 13 < ∞
- 更新为：13，角标：1-2-3
位置(1,6)（a → f）
- 原值：∞
- 计算：D¹$1 $2$ + D¹$2$ 6$ = 6 + 10 = 16 < ∞
- 更新为：16，角标：1-2-6
位置(3,6)（c → f）
- 原值：∞
- 计算：D¹$3 $2$ + D¹$2$ 6$ = 15 + 10 = 25 < ∞
- 更新为：25，角标：3-1-2-6（体现路径递归：c→a→b→f）
位置(3,4)（c → d）
- 原值：15
- 计算：D¹$3 $2$ + D¹$2$ 4$ = 15 + 26 = 41 > 15
- 不更新（原值更小）

依此类推，完成k=3到k=6的迭代，得到最终最短路径矩阵。

四、算法原理深入理解

4.1 为什么∞对应的行列不更新？

原因： 若 i 到 k 的距离为∞，则”i→k→j”的路径必然 ≥ ∞，不可能优于原路径，因此无需计算更新。

4.2 角标的含义

角标 i-k-j： 表示从顶点 i 经过顶点 k 到达顶点 j
复合角标： 记录完整的最短路径经过的顶点序列（如 3-1-2-6 表示 c→a→b→f）
矩阵数值： 对应最短路径的实际长度

4.3 路径回溯方法

通过维护路径矩阵P，记录每对顶点之间最短路径上的下一个顶点，最终可回溯完整路径。

五、考研重点总结

5.1 必背核心

核心公式： D$i $j$ = min(D$i$ j$, D$i $k$ + D$k$ j$)
时间复杂度： O(V³)
迭代顺序： k 循环在最外层（逐步引入中间点）
负权处理： 可处理负权边，不能处理负权环

5.2 手算技巧

严格按照迭代规则：先照抄，后更新
遇到∞跳过计算
角标记录完整路径（便于验证）
对角线始终为0

5.3 常见考点

手动模拟： 给定小规模邻接矩阵，写出前1-2次迭代结果
复杂度分析： 解释为什么是O(V³)
算法比较： Floyd vs Dijkstra（多源vs单源，负权处理等）
路径回溯： 根据路径矩阵还原具体路径

5.4 算法流程口诀

初始化邻接矩阵（带角标）
依次以每个顶点为中转点进行n次迭代
每次迭代按”照抄-更新”规则处理
最终矩阵即为任意两点间最短距离
通过角标可回溯具体路径

六、与其他算法对比

特性	Floyd	Dijkstra	Bellman-Ford
路径类型	多源	单源	单源
时间复杂度	O(V³)	O(V²) 或 O(ElogV)	O(VE)
负权边	✓	✗	✓
负权环	✗	✗	可检测
实现难度	简单	中等	中等
适用场景	稠密图小规模	无负权单源	有负权单源