简介Floyd算法

⽬录

1. 定义

Floyd算法是⼀种⽤于寻找给定的加权图中顶点间最短路径，是经典的多源最短路径算法，可以有效地处理有向图或负权的最短路径问题，同时也被⽤于计算有向图的传递闭包。

Floyd算法的时间复杂度为 O(N3)，空间复杂度为 O(N2)。

2. 优缺点

优点：

容易理解，可以算出任意两个节点之间的最短距离，代码编写简单。缺点：

时间复杂度⽐较⾼，不是和计算⼤量数据。

3. 基本思想

Floyd算法属于动态规划算法，即寻找节点 i 到节点 j 的最短路径。

Step 1: 初始距离

定义 n 节点⽹络的邻接矩阵 An×n ，矩阵中的元素为 ai,j 为节点 i 到节点 j 的⼀步的直线距离。令 A(0)=A，其初始元素为 ai(0),j则该距离有如下三种情况：

ai(0),j=0, i=j

∞, i,j不相连

(0)

其中，节点 i, j 之间有直线连接时，则 ai(0),j 为其距离值 ci,j；节点 i 到⾃⾝的距离为 0；节点 i, j 之间没有直线连接时，则 ai,j 则为 ∞，如下

{ci,j, i,j相连

图：

则该初始邻接矩阵 A为：

即节点0与节点0⾃⾝距离值为0，即 A[0][0]=0；

节点0与节点1之间有直线连接，距离值为5，即 A[0][1]=5；

节点0与节点2之间没有直线连接，则距离值为 ∞，即 A[0][2]=∞；节点0与节点3之间有直线连接，距离值为7，即 A[0][3]=7 ……其他节点间的初始距离可依次写出，即为该邻接矩阵 A。

Step 2: 借中转节点迭代找最短路径

节点 i, j 间⼀步达不到时，则需要在两节点之间通过其他节点（如节点 k）作连接：在 A 矩阵上做 n 次迭代，k=1,⋯,n，第 k 次迭代

k−1k−1k−1

aki,j=min(ai,j,ai,k+ak,j)

即在节点 i 和节点 j 之间找到⼀条最短距离的路径，如下图：

图中的节点 i 到节点 j之间的直线距离 (i→j) 为 6，但经过节点 k 作中转后，节点 i 到节点 j之间的直线距离 (i→k→j) 为 2+3=5，因此 aki,j=min(6,5)=5。

运算过程中的 k 从 1 开始，⽽节点 i, j 则分别从 1 到 n 遍历所有的值，然后 k 加1，直到 k 等于 n 时停⽌。Step 3: 得到所有节点的最短路径

遍历所有的节点，最后得到矩阵 A，其中 ai,j 便存储了任意节点 i 到节点 j 顶点的最短路径的距离。

4. 算法过程⽰例

基于上述的基本思想，定义两个⼆维矩阵：

邻接矩阵 A 记录节点间的最短距离

例如：A[0][3]=10，即表⽰节点 0 与节点 3 之间最短距离为10

路径矩阵 P 记录节点间最短路径中的中转节点

例如：P[0][3]=1，即表⽰节点 0 与节点 3 之间的最短路径轨迹为：(0→1→3)

采⽤上⾯的节点图

Step 1: 初始的邻接矩阵 A 和路径矩阵 P 分别为：

路径矩阵 P 还未开始查找，默认为 −1

Step 2: 开始迭代

T1: 节点 0 做中转节点：

过程：

节点 1 到节点 2：{1,2}：⽐较 A[1][2]>(A[1][0]+A[0][2]) ?节点 1 到节点 3：{1,3}：⽐较 A[1][3]>(A[1][0]+A[0][3]) ?节点 2 到节点 1：{2,1}：⽐较 A[2][1]>(A[2][0]+A[0][1]) ?节点 2 到节点 3：{2,3}：⽐较 A[2][3]>(A[2][0]+A[0][3]) ?节点 3 到节点 1：{3,1}：⽐较 A[3][1]>(A[3][0]+A[0][1]) ?节点 3 到节点 2：{3,2}：⽐较 A[3][2]>(A[3][0]+A[0][2]) ?

→4>(∞+∞) ?→A[1][2]=4 不变→2>(∞+7) ?→A[1][2]=2 不变→3>(3+5) ?→A[1][2]=3 不变→2>(3+7) ?→A[1][2]=2 不变→∞>(∞+5) ?→A[3][1]=∞ 不变→1>(∞+∞) ?→A[3][2]=1 不变

T2: 节点 1 做中转节点：

过程：

节点 0 到节点 2：{0,2}：⽐较 A[0][2]>(A[0][1]+A[1][2]) ?节点 0 到节点 3：{0,3}：⽐较 A[0][3]>(A[0][1]+A[1][3]) ?节点 2 到节点 0：{2,0}：⽐较 A[2][0]>(A[2][1]+A[1][0]) ?节点 2 到节点 3：{2,3}：⽐较 A[2][3]>(A[2][1]+A[1][3]) ?节点 3 到节点 0：{3,0}：⽐较 A[3][0]>(A[3][1]+A[1][0]) ?节点 3 到节点 2：{3,2}：⽐较 A[3][2]>(A[3][1]+A[1][2]) ?

→9>(5+4) ?→A[0][2]=9 更改：经过节点 1→7>(5+2) ?→A[0][3]=7 不变→3>(3+∞) ?→A[2][0]=3 不变→2>(3+2) ?→A[2][3]=2 不变→∞>(∞+∞) ?→A[3][0]=∞ 不变→1>(∞+4) ?→A[3][2]=1 不变

T3: 节点 2 做中转节点：

过程：

节点 0 到节点 1：{0,1}：⽐较 A[0][1]>(A[0][2]+A[2][1]) ?节点 0 到节点 3：{0,3}：⽐较 A[0][3]>(A[0][2]+A[2][3]) ?节点 1 到节点 0：{1,0}：⽐较 A[1][0]>(A[1][2]+A[2][0]) ?节点 1 到节点 3：{1,3}：⽐较 A[1][3]>(A[1][2]+A[2][3]) ?节点 3 到节点 0：{3,0}：⽐较 A[3][0]>(A[3][2]+A[2][0]) ?节点 3 到节点 1：{3,1}：⽐较 A[3][1]>(A[3][2]+A[2][1]) ?

→5>(9+3) ?→A[0][1]=5 不变→7>(9+2) ?→A[0][3]=7 不变

→∞>(4+3) ?→A[1][0]=7 改变：经过节点 2→2>(4+2) ?→A[1][3]=2 不变

→∞>(1+3) ?→A[3][0]=4 改变：经过节点 2→∞>(1+3) ?→A[3][1]=4 改变：经过节点 2

T4: 节点 3 做中转节点：

过程：

节点 0 到节点 1：{0,1}：⽐较 A[0][1]>(A[0][3]+A[3][1]) ?节点 0 到节点 2：{0,2}：⽐较 A[0][2]>(A[0][3]+A[3][2]) ?节点 1 到节点 0：{1,0}：⽐较 A[1][0]>(A[1][3]+A[3][0]) ?节点 1 到节点 2：{1,2}：⽐较 A[1][2]>(A[1][3]+A[3][2]) ?节点 2 到节点 0：{2,0}：⽐较 A[2][0]>(A[2][3]+A[3][0]) ?节点 2 到节点 1：{2,1}：⽐较 A[2][1]>(A[2][3]+A[3][1]) ?Step 3: 得到所有节点的最短路径最终的邻接矩阵 A 和路径矩阵 P为：

从上图可知：

从邻接矩阵 A4 可知节点 1 到节点 0 (1→0)的最短路径距离为 6

从路径矩阵 P4 可知节点 1 到节点 0 (1→0)的最短路径为 1→3→2→0

→5→9→7→4→3→3

>(9+4) ?>(7+1) ?>(2+4) ?>(2+1) ?>(2+4) ?>(2+4) ?

→A[0][1]=5 不变

→A[0][2]=8 改变：经过节点 3→A[1][0]=6 改变：经过节点 3→A[1][2]=3 改变：经过节点 3→A[2][0]=3 不变→A[2][1]=3 不变

5. ⼩结

Floyd算法采⽤中转节点的⽅式，逐步对⽐得到各个路径的最短距离。

Processing math: 100%