弗洛伊德算法

定义

弗洛伊德算法是求加权图中任意两点间最短路径的算法，其英文全称为 Floyd-Warshall algorithm，中文文献中也有弗洛伊德-沃舍尔算法、插点法等称呼。它解决的是多源最短路径问题(All Pairs Shortest Paths)，也就是一次求解图中所有顶点对之间的最短路径，而不是只求某一个起点到其他所有顶点的最短路径^[1]。

该算法既可以处理有向图，也可以处理无向图，允许边上带有正权值或负权值，但要求图中不存在负权回路，因为存在负权回路时最短路径没有意义。算法在完成全部迭代后，图中任意两点间的最短路径长度都会记录在一个距离矩阵中，若再维护一个记录经由点的矩阵，还可以还原出具体的路径^[1]。

除求最短路径外，弗洛伊德算法与计算传递闭包的沃舍尔算法在本质上相通，把矩阵运算中的取最小值换成逻辑或、把加法换成逻辑与，就可以用来判断有向图中任意两点之间是否存在通路^[2]。

原理

算法的基本想法是动态规划：从所有顶点只能直连开始，逐步放宽允许使用的中间顶点集合。设 $D_{i,j,k}$ 表示从顶点 i 到顶点 j、且中间点只允许取自前 k 个顶点时的最短路径长度，那么它只有两种可能：最短路径不经过顶点 k，长度等于 $D_{i,j,k-1}$；或者最短路径经过顶点 k，长度等于 $D_{i,k,k-1}+D_{k,j,k-1}$。取两者中较小的一个，就得到状态转移方程 $D_{i,j,k}=\min(D_{i,j,k-1},D_{i,k,k-1}+D_{k,j,k-1})$。

实现时通常把图的边权写成邻接矩阵，不相连的两个顶点之间记为无穷大，顶点到自身的距离记为 0。随后用三重循环逐层更新：外层枚举中间点 k，内层枚举起点 i 和终点 j，若 $dist[i][k]+dist[k][j]$ 小于当前的 $dist[i][j]$，就用前者替换后者。这种比较并替换的操作被称为松弛操作^[1]。

由于每一轮迭代可以只在一个二维矩阵上原地进行，不必保存全部历史状态，空间开销从三维降到二维。中间点 k 的循环必须放在最外层，顺序改变会破坏算法的正确性^[3]。

flowchart TD

A[初始化邻接矩阵 dist, 无边记为无穷大, 自身为 0] --> B[枚举中间点 k]

B --> C[枚举起点 i]

C --> D[枚举终点 j]

D --> E{dist[i][k] + dist[k][j] < dist[i][j]}

E -->|是| F[更新 dist[i][j] 并记录经由点]

E -->|否| G[保持原值]

F --> H{k 是否枚举完毕}

G --> H

H -->|否| B

H -->|是| I[输出距离矩阵与路径矩阵]

发展历程

弗洛伊德算法以动态规划的形式在 1962 年由罗伯特·弗洛伊德正式发表，当时以「最短路径」为题刊登在《ACM 通讯》上，这被认为是该算法目前公认的形式^[2]。弗洛伊德是美国计算机科学家，曾在斯坦福大学任教，是 1978 年图灵奖的获得者，该算法也因此以他的姓氏命名^[1]。

不过同一问题在更早时期已有相近的成果。法国学者贝尔纳·罗伊在 1959 年发表过基本相同的算法，斯蒂芬·沃舍尔在 1962 年发表用布尔矩阵求图的传递闭包的方法，其逻辑与弗洛伊德算法一致，这使得该算法在不同文献中也被称为 Roy-Warshall 算法、Roy-Floyd 算法或 WFI 算法^[4]。以三重嵌套循环呈现的现代写法，则是由彼得·英格曼在 1962 年描述的^[1]。

由于算法结构简单而稳定，后续研究多集中在改进其效率上。因为三重循环带来的立方级时间开销在数据量较大时会影响运算速度并占用较多存储，出现了若干简化循环、压缩存储或与其他算法结合的改进版本^[5]。

应用

最直接的应用是求解多源最短路径。管道铺设、线路安装和地图规划等需要比较任意两点间通行代价的场景，都可以用该算法处理，边上的权值可以表示距离，也可以表示耗时或费用^[6]。在铁路客票的经由计算中，点到点之间的代价可以是中转次数、里程、运行时间或票价的加权值，预先算出经由矩阵后，查询只需常数级时间^[7]。

在网络与通信领域，算法被用于在路由中寻找较优路径^[1]。数据中心等环境会周期性地运行该算法生成预计算路由表，在硬件连接出现故障时可以快速给出替代路径^[8]。

算法的另一类用途是计算传递闭包，用于判断有向图中任意两个顶点之间是否存在通路^[2]。把算法中的求和换成取最大边权，还可以求两点之间的最宽路径，并与 Schulze 投票方法等排序问题相关^[4]。

局限

主要限制来自时间复杂度。算法使用三重循环，时间复杂度为 O(n³)，空间复杂度为 O(n²)，当顶点数量很大时运算效率不高且占用存储较多，因此被认为不适合直接处理大规模数据^[1]。它的运行时间只与顶点数有关，与边的数量无关，稀疏图上执行同样的立方级运算并不划算，此时从每个顶点各跑一次单源最短路径算法往往更高效^[8]。

在适用条件上，算法要求图中不存在负权回路，否则最短路径没有定义。若存在负权回路，形式化地讲该算法不再适用，但作为一种附带效果，可以在算法结束后检查距离矩阵的对角线元素，如果某个顶点到自身的距离变成负数，就说明图中存在负权回路^[9]。

算法本身只给出最短路径的长度，不直接返回路径的走向，需要额外维护前驱或后继矩阵，才能还原出顶点序列^[4]。在需要按旅客自选的中转次数、票价区间等条件灵活查询的场合，预先算好的结果不够灵活，往往需要重新计算点到点的代价，而且通常只能给出一条最短路径的推荐^[7]。

参见

• 迪杰斯特拉算法 —— 另一种经典最短路径算法，从单个起点出发求到其余各顶点的最短路径，不能处理负权边。

• 贝尔曼-福特算法 —— 允许负权边的单源最短路径算法，也是判断负权回路的常用方法。

• 传递闭包 —— 弗洛伊德算法经简单改动即可用于计算有向图的传递闭包。

• 动态规划 —— 弗洛伊德算法的基本原理所属的算法设计方法。

• 邻接矩阵 —— 弗洛伊德算法常用的图存储结构，距离矩阵通常由它初始化。

• 最短路径问题 —— 图论中的基础问题，弗洛伊德算法解决的是其中任意两点间的形式。