⼀，基本介绍
1）和Dijkstra算法⼀样，弗洛伊德(Floyd)算法也是⼀种⽤于寻给定的加权图中顶点最短路径的算法。 该算法名称⼀创始⼈之⼀，1978年图灵奖获得者，斯坦福⼤学计算机科学系教授罗伯特.弗洛伊德命名；
图灵奖2）弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径；
3）迪杰斯特拉算法⽤于计算图中某⼀个顶点到其他顶点的最短路径；
4）弗洛伊德算法VS迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径；弗洛伊德算法中每⼀个顶点都是出发访问点，所以需要将每⼀个顶点看做被访问顶点，求出从每⼀个顶点到其他顶点的最短路径。
⼆，思路分析
1）设置顶点vi到顶点vk的最短路径为Lik，顶点vk到顶点vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为：
min((Lik + Lkj),Lij)，vk的取值为图中所有顶点，则可以获得vi到vj的最短路径；
2）⾄于vi到vk的最短路径Lik或者vk到vj
三，思路图解
泛域名
这⾥N表⽰很⼤的数，表⽰两个点距离⼤到⼀定程度我们就可以把他当作没有路；
初始顶点前驱顶点都指向⾃⼰。
1）第⼀轮循环中，以A(下标为：0)作为中间顶点【即把A作为中间顶点的所有情况都进⾏遍历，就会 更新距离表和前驱关系】，距离表和前驱关系更新为：
以A作为中间顶点的有(⽆向图，不考虑⽅向)：
B - A -
C [5 + 7 = 12] < B - C [N] => B - C [12] 修改距离 B - A - G [5 + 2 = 7] > B - G[4] 不修改距离 C - A - G [7 + 2 = 9] < C -G[N] => C - G [9] 修改距离 注意，这⾥C到A，B到A，A到G的距离不⼀定是直接连接，如果B - G - A如果连通，也算为这⾥的 B - A 更新后为：
这⾥B - C 就连通了，C - G也连通了，就可以作为下⾯循环的⼀个条件。
2）第⼆轮循环中，以B(下标为：1)作为中间顶点【即把B作为中间顶点的所有情况都进⾏遍历，就会更新距离表和前驱关系】，距离表和前驱关系更新为：
以B作为中间顶点的有(⽆向图，不考虑⽅向)：
A -
B - D [5 + 9 =14] < A - D [N] => A - D [14] A - B - G [5 + 4 = 9] > A - G [2]
C - B -
D [12 + 9 = 21] < C - D [N] => C - D
[21] C - B - G [12 + 4 = 16] > C - G [9] D - B - G [9 + 4 = 13] < D - G [N] => D - G [13] 更新后为：
3）第三轮循环中，以C(下标为：2)作为中间顶点【即把C作为中间顶点的所有情况都进⾏遍历，就会更新距离表和前驱关系】，距离表和前驱关系更新为：湖北师范学院学报
以C作为中间顶点的有(⽆向图，不考虑⽅向)：
A - C -
B [7 + 12 = 19] > A - B [5]
A - C - D [7 + 21 = 28] > A - D [13]
A - C - E [7 + 8 = 15] < A - E [N] => A - E [15] A - C - G [7 + 9 = 16] > A - G [2]
B -
C -
D [12 + 21 = 33] > B - D [9] B - C - E
[12 + 8 = 20] < B - E [N] => B - E [20] B - C - G [12 + 9 = 21] > B - G [4] D - C - E [21 + 8 = 29] < D - E [N] => D- E [29] D -
C - G [21 + 9 = 30] >
D - G [13]
E - C - G [8 + 9 = 17] > E - G [4] 更新后为：
4）第四轮循环中，以D(下标为：3)作为中间顶点【即把D作为中间顶点的所有情况都进⾏遍历，就会更新距离表和前驱关系】，距离表和前驱关系更新为：
以D作为中间顶点的有(⽆向图，不考虑⽅向)：
A - D -
B [14 + 9 = 23] > A - B [5]
A - D - C [14 + 21 = 35] > A - C [7]
A - D - E [14 + 29 = 43] > A - E [15]
A - D - F [14 + 4 = 18] < A - F[N] => A - F[18] A - D - G [14 + 13 = 27] > A - G [2]
地质剖面图
B - D -
C [9 + 21 = 30] > B - C [12] B -
D -
E [9 + 29 = 38] > B - D [20] B - D -
F [9 + 4 = 13] > B - F [N] => B - F [13] B - D -
氢氧化铜
G [9 + 13 = 22] > B - G [4] C - D - E [21 + 29 = 50] > C - E [8] C - D - F [21 + 4 = 25] < C - F [N] => C - F [25] C - D - G [21 + 13 = 34] > C - G [9] E - D - F [29 + 4 = 33] > E - F [5] E - D - G [29 + 13 = 42] > E - G [4] F - D - G [4 + 13 = 17] > F - G [6] 更新后为：
5）第五轮循环中，以E(下标为：4)作为中间顶点【即把E作为中间顶点的所有情况都进⾏遍历，就会更新距离表和前驱关系】，距离表和前驱关系更新为：
以E作为中间顶点的有(⽆向图，不考虑⽅向)：
A - E -
B [15 + 20 = 35] > A - B [5]
A - E - C [15 + 8 = 23] > A - C [7]
A - E - D [15 + 29 = 44] > A - D [14]
A - E - F [15 + 5 = 20] > A - F [18]
A - E - G [15 + 4 = 19] > A - G [20]
B - E -
C [20 + 8 = 28] > B - C [12]
B - E - D [20 + 29 = 49] > B - D [9]
B - E - F [20 + 5 = 25] > B - F [13]
B - E - G [20 + 4 = 24] > B - G [4]
C - E -
D [8 + 29 = 37] > C - D [21]
C - E - F [8 + 5 = 13] < C - F [25] => C - F [13] C - E - G [8 + 4 = 12] > C - G [9]
D -
E -
F [29 + 5 = 34] > D - F [4] D - E - G
[29 + 4 = 33] > D - G [13] F - E - G [5 + 4 = 9] > F - G [6] 更新后为：
6）第六轮循环中，以F(下标为：5)作为中间顶点【即把E作为中间顶点的所有情况都进⾏遍历，就会更新距离表和前驱关系】，距离表和前驱关系更新为：
以F作为中间顶点的有(⽆向图，不考虑⽅向)：
A - F -
B [18 + 13 = 31] > A - B [5]
A - F - C [18 + 13 = 31] > A - C [7]
A - F - D [18 + 4 = 22] > A - D [14]
A - F - E [18 + 5 = 23] > A - E [15]
A - F - G [18 + 6 = 24] > A - G [2]
B - F -
C [13 + 13 = 26] > B - C [12]
B - F - D [13 + 4 = 17] > B - D [9]
B - F - E [13 + 5 = 18] < B - E [20] = > B - E [18] B - F - G [13 + 6 = 19] > B - G [4]
C - F -
D [13 + 4 = 17] < C - D [21] => C - D [17] C - F -
E [13 + 5 = 18] > C - E [8] C -
F -
G [13 + 6 = 19] > C - G [9] D - F - E [4 + 5 = 9] < D - E [29] => D - E [9] D -F - G [4 + 6 = 10] < D - G [13] => D - G [10] E - F - G [5 + 6 = 11] > E - G [4] 更新后为： 7）第七轮循环中，以G(下标为：6)作为中间顶点【即把E作为中间顶点的所有情况都进⾏遍历，就会更新距离表和前驱关系】，距离表和前驱关系更新为： 以G作为中间顶点的有(⽆向图，不考虑⽅向)： A - G - B [2 + 4 = 6] > A - B [5] A - G - C [2 + 9 = 11] > A - C [7] A - G - D [2 + 10 = 12] < A - D [14]=> A - D [12] A - G - E [2 + 4 = 6] < A - E [15] => A - E [6] A - G - F [2 + 6 = 8] < A - F [17] => A - F [8] B - G - C [4 + 9 =13] > B - C [12] B - G - D [4 + 10 = 14] > B - D [9] B - G - E [4 + 4 = 8] < B - E [18] => B - E [8] B - G - F [4 + 6 = 10] < B - F
[13] => B - F [10] C - G - D [9 + 10 = 19] > C - D [17] C - G - E [9 + 4 = 13] > C - E [8] C - G - F [9 + 6 = 15] > C - F [15] D -G - E [10 + 4 = 14] > D - E [9] D - G - F [10 + 6 = 16] > D - F [4] E - G - F [4 + 6 = 10] > E - F [5] 更新后为：
四，代码实现package ;import Arrays ;public class FloydAlgorithm { public static void main (String [] args ) { char [] vertex = {'A','B','C','D','E','F','G'}; final int N = 65536; //创建邻接矩阵 int [][] matrix = new int [][]{ {0,5,7,N ,N ,N ,2}, {5,0,N ,9,N ,N ,4}, {7,N ,0,N ,8,N ,N }, {N ,9,N ,0,N ,4,N }, {N ,N ,8,N ,0,5,4}, {N ,N ,N ,4,5,0,6}, {2,4,N ,N ,4,6,0} }; //创建Graph 对象1
2
3
4
5
6
7
8
电力系统运行与控制9
10
11
12
13
14
15
16
17
18
19
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议