Floyd 算法

2026 大纲 五（四）图的基本应用 2. 最短路径 · 所有顶点对（无权图见《BFS 最短路径》，单源见《Dijkstra》）。

换一个问法：让谁当中转站

Dijkstra 的思路是"每轮确定一个离源点最近的顶点"，那是贪心。Floyd 换了个完全不同的角度，它问的是：

如果只允许拿前 $k$ 个顶点当中转站，$v_i$ 到 $v_j$ 最短能走多远？

把这个量记作 $D^{(k)}[i][j]$——从 $v_i$ 到 $v_j$、且中间顶点的序号都不超过 $k$ 的最短路径长度。⚠️ 受限的只有中间顶点，起点和终点本身不受这个限制。

这个定义一给出，两个端点就明确了：

• $D^{(-1)}$：一个中转站都不许用，那就只能走直连边——它就是邻接矩阵。
• $D^{(n-1)}$：人人都可以当中转站，没有任何限制——它就是最终答案。

于是问题变成：怎么从 $D^{(-1)}$ 一步步推到 $D^{(n-1)}$？

顶点编号从 0 开始时，初始矩阵记作 $D^{(-1)}$（因为 $D^{(0)}$ 已经表示"允许经过 $v_0$"了）；若顶点从 1 编号，初始矩阵就记作 $D^{(0)}$。编号习惯不同，上标随之平移，含义不变。

转移方程：按"经不经过 $v_k$"分类

从 $D^{(k-1)}$ 推 $D^{(k)}$，只多开放了一个中转站 $v_k$。所以把"中间顶点序号不超过 $k$"的最短路径按它到底经不经过 $v_k$ 分成两类，不重不漏：

• 不经过 $v_k$：那它的中间顶点序号其实都不超过 $k-1$，长度就是 $D^{(k-1)}[i][j]$。
• 经过 $v_k$：在 $v_k$ 处把路径切成 $i⇝k$ 和 $k⇝j$ 两段。最短路径上顶点不重复（无负权回路时），所以两段的中间顶点序号都不超过 $k-1$，且各自必须最短，长度为 $D^{(k-1)}[i][k]+D^{(k-1)}[k][j]$。

两类取小者：

$$D^{(k)}[i][j]=min(D^{(k-1)}[i][j],D^{(k-1)}[i][k]+D^{(k-1)}[k][j])$$

这是动态规划，不是贪心——这一点与 Dijkstra 是本质区别。

落成代码就是那三重循环：

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];      // 注意不是 = k
            }

先动手看一眼

加载可视化中...

盯 $k$ 每加一，整张表刷新一遍的样子——$k$ 不是"第几轮"，是"允许的中转点集合有多大"。这个理解直接决定了下一节。

$k$ 为什么必须在最外层

这是 Floyd 唯一真正的坑。

$k$ 的含义是"允许的中转点集合上界"，而转移方程要求 $D^{(k)}$ 的每一格都建立在完整的 $D^{(k-1)}$ 之上。所以必须先固定这个集合、再把整张表刷一遍，然后才能扩大集合。写成 for i → for j → for k，就变成了"对每一格分别去试各种中转点"，而试的时候别的格子还没算好。

具体反例：4 个顶点、3 条弧，构成一条编号递减的链——$0\to 3$ 权 1，$3\to 2$ 权 1，$2\to 1$ 权 1。正确答案是 $dist[0][1]=3$（路径 $0\to 3\to 2\to 1$）。

错误写法 for i → for j → for k 的执行：

• $i=0,j=1$：试所有 $k$——$k=2$ 时 $dist[0][2]=\mathrm{\infty }$；$k=3$ 时 $dist[0][3]+dist[3][1]=1+\mathrm{\infty }=\mathrm{\infty }$。无更新。（$dist[3][1]$ 此刻还没算出来，因为 $i=3$ 排在后面。）
• $i=0,j=2$：$k=3$ 时更新 $dist[0][2]=2$——可惜晚了，$j=1$ 已经过去，本轮不回头。
• $i=3,j=1$：$k=2$ 时更新 $dist[3][1]=2$——同样晚了，$i=0$ 已经过去。

最终 $dist[0][1]=\mathrm{\infty }$，而正确答案是 3。

而正确写法 for k → for i → for j：$k=0,1$ 无更新；$k=2$ 时 $dist[3][1]=1+1=2$；$k=3$ 时 $dist[0][1]=dist[0][3]+dist[3][1]=1+2=\mathbf{3}$ ✓。

⚠️ 为什么反例要造成"编号递减"的链？ 若链是 $0\to 1\to 2\to 3$ 这种编号递增的形状，i-j-k 的扫描次序恰好顺着链的方向，误打误撞也能算对。"某些图上碰巧对"正是错误循环序最危险的地方——不构造逆序的图，你在纸上试几个例子可能永远发现不了它是错的。

另外说明：$i$ 与 $j$ 之间可以互换。它们只是在遍历所有点对，彼此没有依赖；有依赖的只有 $k$。

path[i][j] = path[k][j]，不是 = k

path[i][j] 存的是"$i\to j$ 最短路径上，$j$ 的前一个顶点"，不是"某个中转点"。

新路径是 $i⇝k⇝j$，$j$ 的前驱应当取自 $k⇝j$ 这一段，也就是 path[k][j]。只有当 $k\to j$ 恰好是直连边时它才等于 $k$；一旦 $k$ 到 $j$ 还要绕别的点，写成 = k 就把中间顶点丢了，回溯出来的路径是断的。

初始化配套：

#define INF 0x3f3f3f3f      // 取这个值是为了 INF+INF 不溢出 int

int dist[V][V];   // 最短距离矩阵
int path[V][V];   // 前驱矩阵：path[i][j] 是 i→j 最短路径上 j 的前一个顶点

void init(int graph[V][V]) {          // 直接由邻接矩阵得到 D^(-1)
    for (int i = 0; i < V; i++)
        for (int j = 0; j < V; j++) {
            dist[i][j] = graph[i][j];     // 无边处为 INF，对角线为 0
            path[i][j] = (i != j && graph[i][j] < INF) ? i : -1;
        }
}

负权：能处理负权边，不能有负权回路

这是 Floyd 与 Dijkstra 的分水岭：

✅ Floyd 能处理负权边。 上面的正确性推导全程只用了"经不经过 $v_k$"的分类讨论，一次都没用到"边权非负"——而 Dijkstra 的贪心恰恰卡在那一步上。

🔴 但不能有负权回路。 沿着负权回路绕一圈总权就变小，可以无限减下去，最短路径根本不存在——这不是算法不行，是问题无解。判断依据：跑完后若存在 $dist[i][i]<0$，就说明有负权回路。

时间 $O(n^3)$、空间 $O(n^2)$（两个矩阵，不需要 $n^3$ 的滚动数组）。无向图把每条边看成方向相反的两条弧，矩阵对称，算法一字不改。

和"邻接矩阵的幂"别搞混

邻接矩阵那一篇讲过 $A^k[i][j]$ = 长度恰好为 $k$ 的路径条数。它的三重循环和 Floyd 长得一模一样，很容易串：

	矩阵幂 $A^k$	Floyd
内层做什么运算	乘法 + 加法	加法 + 取 $min$
结果的含义	路径条数	路径长度
下标 $k$ 的含义	路径长度恰好为 $k$	允许的中转点上界

结构同源、语义完全不同。 问"$A^2$ 中某元素的含义"答"最短路径"，或者问 Floyd 的 $D^{(2)}$ 答"路径条数"，都是这个混淆造成的。

四顶点有向图的逐轮全表推演（想手动模拟一遍就展开）

初始邻接矩阵（$\mathrm{\infty }$ 表示无弧），即 6 条弧：$0\to 1$ 权 5、$0\to 3$ 权 7、$1\to 2$ 权 4、$2\to 0$ 权 3、$2\to 3$ 权 2、$3\to 2$ 权 1。

	$v_0$	$v_1$	$v_2$	$v_3$
$v_0$	0	5	∞	7
$v_1$	∞	0	4	∞
$v_2$	3	∞	0	2
$v_3$	∞	∞	1	0

$k=0$（允许经过 $v_0$ 中转）——逐格检查 $dist[i][0]+dist[0][j]$：

• $dist[2][1]$：$3+5=8<\mathrm{\infty }$，更新为 8
• $dist[2][3]$：$3+7=10>2$，不更新
• 其余格子的 $dist[i][0]$ 或 $dist[0][j]$ 为 $\mathrm{\infty }$，均不更新

$D^{(0)}$：

	$v_0$	$v_1$	$v_2$	$v_3$
$v_0$	0	5	∞	7
$v_1$	∞	0	4	∞
$v_2$	3	8	0	2
$v_3$	∞	∞	1	0

$k=1$（允许经过 $v_0,v_1$）：

• $dist[0][2]$：$5+4=9<\mathrm{\infty }$，更新为 9
• $dist[0][3]$：$5+\mathrm{\infty }=\mathrm{\infty }\ge 7$，不更新
• $dist[2][0]$、$dist[2][3]$：$8+\mathrm{\infty }=\mathrm{\infty }$，均不更新

$D^{(1)}$：

	$v_0$	$v_1$	$v_2$	$v_3$
$v_0$	0	5	9	7
$v_1$	∞	0	4	∞
$v_2$	3	8	0	2
$v_3$	∞	∞	1	0

$k=2$（允许经过 $v_0,v_1,v_2$）——这一轮改动最多：

• $dist[0][1]$：$9+8=17\ge 5$，不更新
• $dist[0][3]$：$9+2=11\ge 7$，不更新
• $dist[1][0]$：$4+3=7<\mathrm{\infty }$，更新为 7
• $dist[1][3]$：$4+2=6<\mathrm{\infty }$，更新为 6
• $dist[3][0]$：$1+3=4<\mathrm{\infty }$，更新为 4
• $dist[3][1]$：$1+8=9<\mathrm{\infty }$，更新为 9

$D^{(2)}$：

	$v_0$	$v_1$	$v_2$	$v_3$
$v_0$	0	5	9	7
$v_1$	7	0	4	6
$v_2$	3	8	0	2
$v_3$	4	9	1	0

$k=3$（允许全部顶点）：

• $dist[0][2]$：$7+1=8<9$，更新为 8
• 其余格子均无改进

最终 $D^{(3)}$：

	$v_0$	$v_1$	$v_2$	$v_3$
$v_0$	0	5	8	7
$v_1$	7	0	4	6
$v_2$	3	8	0	2
$v_3$	4	9	1	0

最终前驱矩阵与路径还原：

$path[i][j]$	$j=0$	$j=1$	$j=2$	$j=3$
$i=0$	−1	0	3	0
$i=1$	2	−1	1	2
$i=2$	2	0	−1	2
$i=3$	2	0	3	−1

读法是从终点往回倒推。以 $3\to 1$ 为例：$path[3][1]=0$ → 顶点 1 的前驱是 0；$path[3][0]=2$ → 0 的前驱是 2；$path[3][2]=3$ → 2 的前驱是 3，已到起点，停。倒过来即 $3\to 2\to 0\to 1$，验算 $1+3+5=9=dist[3][1]$ ✓。

再验一个 $0\to 2$：$path[0][2]=3$，$path[0][3]=0$，得 $0\to 3\to 2$，长度 $7+1=8=dist[0][2]$ ✓。这里 $path[0][2]=3$ 是在 $k=3$ 那一轮由 path[3][2] 赋来的，而 $3\to 2$ 恰是直连边，所以它就是 3——换成要绕路的情形，写 = k 立刻出错。

每还原一条路径都要验算长度，这是手算里唯一可靠的自检。

只用一个矩阵就地更新为什么安全（想弄清代码里为什么不需要两份 dist 就展开）

代码里只有一个 dist[][]，第 $k$ 轮读到的 dist[i][k]、dist[k][j] 会不会已经在本轮被改过？

不会。要改 dist[i][k] 就得满足 dist[i][k] + dist[k][k] < dist[i][k]，即 dist[k][k] < 0，而这只有存在负权回路时才可能。

所以：无负权回路 ⇒ 对角线恒为 0 ⇒ 第 $k$ 行与第 $k$ 列在第 $k$ 轮"冻结" ⇒ 就地更新与双矩阵滚动完全等价。三件事是同一件事的三种说法，也顺带说明了负权回路为什么让算法失去意义。

何时该改用 n 次 Dijkstra（要在两者之间选型时展开）

对每个顶点各跑一次朴素 Dijkstra 是 $n\times O(n^2)=O(n^3)$，与 Floyd 同阶。差别在三处：

1. 代码量：Floyd 只有三重循环加一个 if；Dijkstra 要维护 visited 与选点循环。
2. 负权边：Floyd 支持，Dijkstra 不支持。
3. 稀疏图：$n$ 次堆优化 Dijkstra 是 $O(ne\log n)$，稀疏时优于 $O(n^3)$。

所以"全源一律用 Floyd"是不对的：稀疏图上跑 $n$ 次堆优化 Dijkstra 更快；但只要图中有负权边，就只能用 Floyd（或 Bellman-Ford 系）。

一组概念	差别	判别依据
支持负权边 vs 不支持负权回路	前者是能力，后者是问题本身无解	问"最短路径存不存在"：负回路下不存在
Floyd vs $n$ 次 Dijkstra	朴素同为 $O(n^3)$；稀疏图上 $n$ 次堆优化更快	先问有没有负权边，再比 $n^3$ 与 $ne\log n$
Floyd vs Dijkstra 的思想	动态规划 vs 贪心	前者枚举中转点做分类讨论，后者每轮"确定"一个顶点

考点速记

三条结论：

1. $k$ 是"允许的中转点上界"，所以必须在最外层；写到内层，在编号逆序的链上会给出 $\mathrm{\infty }$。
2. path[i][j] = path[k][j]，因为 path 记的是终点的前驱，不是中转点。
3. $O(n^3)$ 时间、$O(n^2)$ 空间；支持负权边，不支持负权回路（判断依据：$dist[i][i]<0$）。

这一节在 408 真题里至今不单独成题——下方的「真题练习」是空的，这不是漏挂。Floyd 目前出现的位置有两处，都是"作为对照项"：

• 最短路径算法的选型判断：题目要求"求每一对顶点之间的最短路径"或图中含负权边时，正确答案就是它。选型的第一问是"边权是否全相等"（是则 BFS），第二问是"单源还是全源、有没有负权"（单源非负用 Dijkstra，全源或含负权用 Floyd）。
• 与邻接矩阵幂的区分：$A^k$ 那道大题问的是"长度恰好为 $k$ 的路径条数"，与 Floyd 的三重循环形状相同但语义无关。

复习优先级上，它排在 Dijkstra 与 Prim/Kruskal 之后：把三重循环的次序、path 的更新式、以及"支持负权边不支持负权回路"这三条记住即可，不必花大量时间练手算全表。

易错：$k$ 必须在最外层。 挪到内层在有些图上碰巧还是对的，所以自己出题验证时要构造编号递减的链才能暴露问题。

易错：path[i][j] = path[k][j]，不是 = k。 只有 $k\to j$ 是直连边时两者才碰巧相同。

易错：Floyd 与"邻接矩阵的幂"结构像、含义不同。 一个取 $min$ 算长度，一个做乘加算条数。

教材出处

• 严蔚敏《数据结构（C 语言版）》（第 2 版）印刷 p174，§6.6.2 之 2： "求解每一对顶点之间的最短路径有两种方法：其一是分别以图中的每个顶点为源点共调用 $n$ 次 迪杰斯特拉算法；其二是采用下面介绍的弗洛伊德 (Floyd) 算法。 两种算法的时间复杂度均为 $O(n^3)$，但后者形式上较简单。" 同页给出两个辅助数组：Path[i][j] 为"最短路径上顶点 $v_j$ 的前一顶点的序号"， D[i][j] 记录 $v_i$ 与 $v_j$ 之间的最短路径长度。
• 同书印刷 p174：算法步骤逐层描述"在 $v_i$ 和 $v_j$ 间加入顶点 $v_k$…… 取其中较短者作为 $v_i$ 到 $v_j$ 的中间顶点序号不大于 $k$ 的最短路径"， 并给出方阵序列 $D^{(-1)},D^{(0)},D^{(1)},\dots ,D^{(n-1)}$ 与递推式 $D^{(k)}[i][j]=min\{D^{(k-1)}[i][j],D^{(k-1)}[i][k]+D^{(k-1)}[k][j]\}$—— 本篇的状态定义与转移方程即以此为准。
• 同书印刷 p175：ShortestPath_Floyd 的完整实现， 其中更新时写的正是 Path[i][j] = Path[k][j]，与本篇一致； 同页并给出从 Path 逐级回溯读出路径的示范。

相关知识

Dijkstra 算法（单源、贪心、禁负权，与本篇的对照贯穿全文）｜ BFS 最短路径（无权图，三算法选型表在那一篇）｜ 邻接矩阵（输入输出都是矩阵；矩阵幂与本篇的区分也在那一篇）｜ 图的基本概念（带权路径长度、回路）｜ 矩阵的存储（二维数组的地址计算与遍历代价）

相关文章

• 图的基本概念
• 邻接矩阵
• 邻接表
• 十字链表与邻接多重表
• 广度优先搜索（BFS）
• 深度优先搜索（DFS）
• 最小生成树：Prim
• 最小生成树：Kruskal
• BFS 求无权图最短路径
• Dijkstra 算法
• DAG 描述表达式
• 拓扑排序
• 关键路径

交互体验

前往完整可视化页面 →

真题练习