算法类学习笔记 —— Floyd路径规划算法理解笔记

算法类学习笔记 —— Floyd路径规划算法理解笔记

引用

CSDN

1.

https://m.blog.csdn.net/qq_42957717/article/details/139779878

Floyd算法是一种用于计算图中所有顶点对之间最短路径的算法。与Dijkstra算法不同，Floyd算法通过将每个顶点作为中间点，逐步更新所有顶点对之间的最短路径。本文将通过详细的示例拆解和邻接矩阵的更新过程，帮助读者深入理解Floyd算法的工作原理。

介绍

Floyd算法是Floyd在研究用于求解带权图中所有结点对之间的最短路径算法，又称为差点法。在算法求解的过程中，每个结点轮流作为源点，重复执行N次Dijkstra算法。其基本思想是通过一个图的权值矩阵求出的它的每两点间的最短路径矩阵。首先，从任意一条单边路径开始，所有两点之间的距离是边的权，如果两边之间没有边相连，则权为无穷大。然后，对于每一对顶点 u 和 v 查看是否存在一个顶点w，使得从u 到 w 再到 v比已知路径更短，则进行更新。

该算法的核心思路是通过一个图的权值矩阵求出该图中任意两个结点之间的最短路径。若图的带权邻接矩阵为A = [ a ( i , j ) ] n × n A=[a(i,j)]_{n \times n}A=[a(i,j)]n×n ，由此开始进行n次递归并更新，即由矩阵D ( 0 ) = A D(0)=AD(0)=A，按照一个公式建立矩阵D ( 1 ) D(1)D(1)；相同的，由D ( 1 ) D(1)D(1)构造出D ( 2 ) D(2)D(2)，直到由D ( n − 1 ) D(n-1)D(n−1)构造出D ( n ) D(n)D(n)。矩阵D ( n ) D(n)D(n)的第i行第j列元素，是从i号结点到j号结点的最短路径长度。D ( n ) D(n)D(n)称为图的距离矩阵。

算法的基本过程是：用邻接矩阵A来表示一个图，若从v i v_ivi 到v j v_jvj 有路可达，则A [ i , j ] = d A[i,j] = dA[i,j]=d，d表示该路段的长度，否则A [ i , j ] A[i,j]A[i,j]为空。定义矩阵D，记录的是所插入的点的信息。D [ i , j ] D[i,j]D[i,j]表示从v i v_ivi 到v j v_jvj 需要经过的点，初始化D [ i , j ] = j D[i,j] = jD[i,j]=j。把各个顶点插入土中，比较插点后的距离与原来的距离，A [ i , j ] = min ⁡ ( A [ i , j ] , A [ i , k ] + A [ k , j ] ) A[i,j] = \min(A[i,j], A[i,k]+A[k,j])A[i,j]=min(A[i,j],A[i,k]+A[k,j])，如果A [ i , j ] A[i,j]A[i,j]的值变小，则D [ i , j ] = k D[i,j] = kD[i,j]=k

示例拆解

初始状态

网络结点的邻接矩阵如下表：

邻接矩阵
A B C D E F
A 0 1 2 3 INF INF
B 1 0 INF INF INF 6
C 2 INF 0 3 1 4
D 3 INF 3 0 4 INF
E INF INF 1 4 0 2
F INF 6 4 INF 2 0

第一轮处理

将A结点作为原点进行更新计算。按照上述的规则进行更新。

1. AB之间距离为1，与之前AB保持一致，无需更新；
2. AC之间距离为2，与之前AC保持一致，无需更新；
3. AD之间距离为3，与之前AD保持一致，无需更新；
4. AE之间无路径，与之前AE保持一致，无需更新；
5. AF之间无路径，与之前AF保持一致，无需更新；
6. BAC之间距离为3，小于之前BC之间无路径，需要更新；
7. BAD之间距离为4，小于之前BD之间无路径，需要更新；
8. BE之间无路径，与之前BE保持一致，无需更新；
9. BF之间距离为6，与之前BF保持一致，无需更新；
10. CD之间距离为3，与之前CD保持一致，无需更新；
11. CE之间距离为1，与之前CE保持一致，无需更新；
12. CF之间距离为4，与之前CF保持一致，无需更新；
13. DE之间距离为4，与之前DE保持一致，无需更新；
14. DF之间无路径，与之前DF保持一致，无需更新；
15. EF之间距离为2，与之前EF保持一致，无需更新。

则邻接矩阵可更新为:

A作为原点邻接矩阵
A B C D E F
A 0 1 2 3 INF INF
B 1 0 3 4 INF 6
C 2 3 0 3 1 4
D 3 4 3 0 4 INF
E INF INF 1 4 0 2
F INF 6 4 INF 2 0

第二轮处理

将B结点作为原点进行更新计算。按照上述的规则进行更新。

1. AB之间无新路径，无需更新；
2. AC之间无新路径，无需更新；
3. AD之间无新路径，无需更新；
4. AE之间无路径，与之前AE保持一致，无需更新；
5. ABF之间距离为7，小于之前AF无路径，需要更新；
6. BC之间无新路径，无需更新；
7. BD之间无新路径，无需更新；
8. BE之间无路径，与之前BE保持一致，无需更新；
9. BF之间无新路径，无需更新；
10. CD之间无新路径，无需更新；
11. CE之间无新路径，无需更新；
12. CF之间无新路径，无需更新；
13. DE之间无新路径，无需更新；
14. DF之间无新路径，无需更新；
15. EF之间无新路径，无需更新；

则邻接矩阵可更新为:

B作为原点邻接矩阵
A B C D E F
A 0 1 2 3 INF 7
B 1 0 3 4 INF 6
C 2 3 0 3 1 4
D 3 4 3 0 4 INF
E INF INF 1 4 0 2
F 7 6 4 INF 2 0

第三轮处理

将C结点作为原点进行更新计算。按照上述的规则进行更新。

1. AB之间无新路径，无需更新；
2. AC之间无新路径，无需更新；
3. AD之间无新路径，无需更新；
4. ACE之间距离为3，小于之前AE无路径，需要更新；
5. ACF之间距离为6，小于之前ABF路径，需要更新；
6. BC之间无新路径，无需更新；
7. BACD之间距离为6，大于之前BD路径，无需更新；
8. BACE之间距离为4，小于之前BE无路径，需要更新；
9. BACF之间距离为7，小于之前BF路径，无需更新；
10. CD之间无新路径，无需更新；
11. CE之间无新路径，无需更新；
12. CF之间无新路径，无需更新；
13. DCE之间距离为4，与之前DE保持一致，无需更新；
14. DCF之间距离为7，小于之前DF无路径，需要更新；
15. ECF之间距离为5，大于之前EF路径，无需更新。

则邻接矩阵可更新为:

C作为原点邻接矩阵
A B C D E F
A 0 1 2 3 3 6
B 1 0 3 4 4 6
C 2 3 0 3 1 4
D 3 4 3 0 4 7
E 3 4 1 4 0 2
F 6 6 4 7 2 0

第四轮处理

将D结点作为原点进行更新计算。按照上述的规则进行更新。

1. AB之间无新路径，无需更新；
2. ADC之间距离为6，大于之前AC路径，无需更新；
3. AD之间无新路径，无需更新；
4. ADE之间距离为3，大于之前AE路径，无需更新；
5. ADCF之间距离为10，ADEF之间距离为9，均大于之前AF路径，无需更新；
6. BC之间无新路径，无需更新；
7. BD之间无新路径，无需更新；
8. BADE之间距离为8，大于之前BE路径，无需更新；
9. BADCF之间距离为11，BADEF之间距离为10，大于之前BF路径，无需更新；
10. CD之间无新路径，无需更新；
11. CDE之间距离为7，大于之前CE路径，无需更新；
12. CDEF之间距离为9，大于之前CF路径，无需更新；
13. DE之间无新路径，无需更新；
14. DF之间无新路径，无需更新；
15. EDCF之间距离为11，大于之前EF路径，无需更新。

则邻接矩阵可更新为:

D作为原点邻接矩阵
A B C D E F
A 0 1 2 3 3 6
B 1 0 3 4 4 6
C 2 3 0 3 1 4
D 3 4 3 0 4 7
E 3 4 1 4 0 2
F 6 6 4 7 2 0

第五轮处理

将E结点作为原点进行更新计算。按照上述的规则进行更新。

1. AB之间无新路径，无需更新；
2. AC之间无新路径，无需更新；
3. AD之间无新路径，无需更新；
4. AE之间无新路径，无需更新；
5. ACEF之间距离为5，小于之前AF路径，选哟更新；
6. BC之间无新路径，无需更新；
7. BD之间无新路径，无需更新；
8. BE之间无新路径，无需更新；
9. BADCEF之间距离为6，与之前BF保持一致，无需更新；
10. CED之间距离为5，大于之前CD路径，无需更新；
11. CE之间无新路径，无需更新；
12. CEF之间距离为3，小于之前CF路径，需要更新；
13. DE之间无新路径，无需更新；
14. DEF之间距离为6，小于之前DF路径，需要更新；
15. EF之间无新路径，无需更新；

则邻接矩阵可更新为:

E作为原点邻接矩阵
A B C D E F
A 0 1 2 3 3 5
B 1 0 3 4 4 6
C 2 3 0 3 1 3
D 3 4 3 0 4 6
E 3 4 1 4 0 2
F 5 6 3 6 2 0

第六轮处理

将F结点作为原点进行更新计算。
按照上述的规则进行更新。

1. AB之间无新路径，无需更新；
2. AC之间无新路径，无需更新；
3. AD之间无新路径，无需更新；
4. AE之间无新路径，无需更新；
5. AF之间无新路径，无需更新；
6. BFC之间距离为10，大于之前BC路径，无需更新；
7. BFED之间距离为12，大于之前BD路径，无需更新；
8. BFE之间距离为8，大于之前BE路径，无需更新；
9. BF之间无新路径，无需更新；
10. CD之间无新路径，无需更新；
11. CE之间无新路径，无需更新；
12. CF之间无新路径，无需更新；
13. DE之间无新路径，无需更新；
14. DF之间无新路径，无需更新；
15. EF之间无新路径，无需更新；

则邻接矩阵可更新为:

F作为原点邻接矩阵
A B C D E F
A 0 1 2 3 3 5
B 1 0 3 4 4 6
C 2 3 0 3 1 3
D 3 4 3 0 4 6
E 3 4 1 4 0 2
F 5 6 3 6 2 0

总结

Floyd算法是动态规划算法的一种，适用于APSP(All Pairs Shortest Paths)。若用在稠密图中计算最有路ing，效果良好，而且对边的权重正负关系没有特殊要求。该算法简单有效，结构紧凑，因为含有三种循环，作用域稠密图效率要比执行n次Dijkstra算法高。算法的基本原理容易理解，算法的执行过程也相对简单，而且能够计算出任意两个结点之间的最短距离。但是由于其时间复杂度高，不适用于计算大量数据。

相比于Dijkstra算法是计算图中某一顶点到其它顶点的最短路径。Dijkstra算法通过选定的被访问顶点，算出从出发访问顶点到其它顶点的最短路径。Floyd算法是计算图中各顶点到其它顶点之间的最短路径。Floyd算法中每一个顶点都是出发访问点，所以需要将每一个顶点看作被访问顶点，从而算出从每一个顶点到其他它顶点的最短路径。