一、定义

Floyd算法（弗洛伊德算法）是解决任意两点间的最短路径的一种很有代表性的算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。该算法名称以创始人之一，1978年图灵奖**者，斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。该算法也称为Floyd-Warshall算法、Roy-Warshall算法、Roy-Floyd算法或WFI算法。

Floyd算法又称为插点法，是一个经典的动态规划算法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法。所谓多源点是与单源点相对来讲的，单源点是指从一个起始点到其它所有点，多源点是指任意两点之间。

与Dijkstra算法比较1、共同点

都是最短路径算法。

2、不同点

区别

Floyd算法

Dijkstra算法

1

多源点最短路径算法

单源点最短路径算法

2

经典的动态规划算法

本质上是贪心算法

3

可以处理负权

不能回溯，不能处理负权

三、算法描述从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。对于每一对结点 i 和 j，看看是否存在一个结点k 使得从 i 到 k 再到 j 比已知的路径更短，如果是更新它。

从任意结点i到任意结点j的最短路径不外乎两种可能：

直接从i到j；从i经过若干个结点k到j。

所以，我们假设Dis(i,j)为结点i到结点j的最短路径的距离，对于每一个结点k，我们检查Dis(i,k) + Dis(k,j) < Dis(i,j)是否成立，如果成立，证明从i到k再到j的路径比i直接到j的路径短，我们便设置Dis(i,j) = Dis(i,k) + Dis(k,j)，这样一来，当我们遍历完所有结点k，Dis(i,j)中记录的便是i到j的最短路径的距离。所以这实际上将大规模的问题自顶向下划分为了小规模的问题，这就是动态规划思想，状态转移方程是 Dis[i,j]:=min{ Dis[i,k]+Dis[k,j]，Dis[i,j] }。

四、演示例子

题目：求图4-1中各点相互之间的最短距离？

图4-1

第1步，根据加权连通图，创建矩阵S。当任意两点之间不允许经过第三个点时，这些结点之间最短距离就是初始距离，默认没有直接相连的两结点之间初始距离是INF(无穷大)。如图4-2所示。

图4-2

第2步，以结点A为中介点，只允许经过结点A，求任意两点之间的最短距离，应该如何求呢？只需判断S[i][A]+S[A][j]是否比S[i][j]要小即可。S[i][j]表示的是从结点i到结点j之间的距离。S[i][A]+S[A][j]表示的是从结点i先到结点A，再从结点A到结点j的距离之和。伪代码表示如下：

for(i=A; i<=G; i++)for(j=A; j<=G; j++){ if (S[i][j] > S[i][A] + S[A][j]) S[i][j] = S[i][A] + S[A][j];}

更新矩阵S。如图4-3所示。

图4-3

第3步，以结点B为中介点，只允许经过结点A和B，求任意两点之间的最短距离，应该如何求呢？在求得图4-3矩阵S的前提下，只需判断S[i][B]+S[B][j]是否比S[i][j]要小即可。S[i][j]表示的是从结点i到结点j之间的距离。S[i][B]+S[B][j]表示的是从结点i先到结点B，再从结点B到结点j的距离之和。伪代码表示如下：

for(i=A; i<=G; i++)for(j=A; j<=G; j++){ if (S[i][j] > S[i][B] + S[B][j]) S[i][j] = S[i][B] + S[B][j];}

更新矩阵S。如图4-4所示。

图4-4

第4步，以结点C为中介点，只允许经过结点A、B和C，求任意两点之间的最短距离，应该如何求呢？在求得图4-4矩阵S的前提下，只需判断S[i][C]+S[C][j]是否比S[i][j]要小即可。S[i][j]表示的是从结点i到结点j之间的距离。S[i][C]+S[C][j]表示的是从结点i先到结点C，再从结点C到结点j的距离之和。伪代码表示如下：

for(i=A; i<=G; i++)for(j=A; j<=G; j++){ if (S[i][j] > S[i][C] + S[C][j]) S[i][j] = S[i][C] + S[C][j];}

更新矩阵S。如图4-5所示。

图4-5

第5步，依此类推，参考第4步求得的矩阵S，以结点D为中介点，只允许经过结点A、B、C和D，求任意两点之间的最短距离，更新矩阵S。如图4-6所示。

图4-6

第6步，依次类推，参考第5步求得的矩阵S，以结点E为中介点，只允许经过结点A、B、C、D和E，求任意两点之间的最短距离，更新矩阵S。如图4-7所示。

图4-7

第7步，依次类推，参考第6步求得的矩阵S，以结点F为中介点，只允许经过结点A、B、C、D、E和F，求任意两点之间的最短距离，更新矩阵S。如图4-8所示。

图4-8

第8步，以结点G为中介点，只允许经过结点A、B、C、D、E、F和G，求任意两点之间的最短距离，应该如何求呢？在求得图4-8矩阵S的前提下，只需判断S[i][G]+S[G][j]是否比S[i][j]要小即可。S[i][j]表示的是从结点i到结点j之间的距离。S[i][G]+S[G][j]表示的是从结点i先到结点G，再从结点G到结点j的距离之和。伪代码表示如下：

for(i=A ;i<=G ;i++)for(j=A; j<=G; j++){ if (S[i][j] > S[i][G] + S[G][j]) S[i][j] = S[i][G] + S[G][j];}

更新矩阵S。如图4-9所示。

图4-9

最后矩阵S中存储的是任意两结点的最短距离。例如：从矩阵中可看出，

A到各点之间的距离分别为：

d(A,B)=12, d(A,C)=22，d(A,D)=22, d(A,E)=18, d(A,F)=16, d(A,G)=14。

B到各点之间的距离分别为：

d(B,C)=10, d(B,D)=13, d(B, E)=9, d(B,F)=7, d(B,G)=16。

整个算法过程虽然说起来很麻烦，但是伪代码实现却非常简单，核心伪代码只有五行：

for(k=A;k<=G;k++)for(i=A;i<=G;i++)for(j=A;j<=G;j++) if(S[i][j] > S[i][k] + S[k][j]) S[i][j] = S[i][k] + S[k][j];五、优缺点**

与Dijkstra算法对比：

都可以求图中所有点对的最短路径。Floyd算法更简洁；Dijkstra算法必须以图中的每个结点作为源点执行n次。两者时间复杂度都为O(n^3)。Floyd算法适用于APSP(All Pairs Shortest Paths，多源最短路径)，是一种动态规划算法，三重循环，可以处理的边权可正可负；Dijkstra算法本质上是一种贪心算法，无回溯，无法处理负权。对于稠密的图，可以使用Floyd算法，效率要高于Dijkstra算法，也要高于SPFA算法；对于稀疏的图，采用n次Dijkstra比较出色。Floyd算法容易理解，代码编写比Dijkstra简单。六、应用

一切能抽象成图或树的场景，如果要求任意两点间最短路径，Floyd算法可考虑。比如，查找任意两个城市之间的最短路径；在地图中寻找任意两个地点之间的最短路径；在网络连接中为路由器寻找最短的传输路径等。