40.弗洛伊德（Floyd）算法

概述

我们此前拆解过迪杰斯特拉（Dijkstra）算法，与它一样，弗洛伊德（Floyd）算法也是用于寻找给定的加权图中顶点间最短路径的算法。该算法是1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德及其团队发现的，以主要创始人弗洛伊德命名。
迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点的最短路径，而弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每一个顶点到其他顶点的最短路径。

分析

设置顶点vi到顶点vk的最短路径已知为Lik，顶点vk到vj的最短路径已知为Lkj，顶点vi到vj的路径为Lij，则vi到vj的最短路径为: min((Lik+Lkj),Lij)，vk的取值为无向图中所有顶点，则可获得vi到vj的最短路径。
至于vi到vk的最短路径Lik或者vk到vi的最短路径Lkj，是以同样的方式获得。

我们还是回到“郝乡长”的政绩工程——得胜乡的七村修路问题

首先是对于各个顶点之间举例的初始化
在这里插入图片描述
对于前驱关系也是我们在算法开始之前需要明晰的

在第一轮循环中，以A（下标：0）作为中间顶点，距离表和前驱关系会更新为：

在这里插入图片描述
以A为中间节点的可能性全部遍历，就会得到更新的距离表和前驱关系。

（无向图）将A作为中间节点情况有：

分析距离表的替换：

• C-A-G 距离 7+2 = 9； --------> CG (N) ------>CG(9)
• C-A-B 距离 7+5 = 12； --------> CB(N) ------>CB(12)
• G-A-B 距离 2+5 = 7； --------> GB(3) 因为7>3所以不做替换！

分析前驱关系表的替换：

• C通过A到G，故前驱关系表中，C行G列的前驱节点替换为A；
• G通过A到C，故前驱关系表中，G行C列的前驱节点替换为A；
• C通过A到B，故前驱关系表中，C行B列的前驱节点替换为A；
• B通过A到C，故前驱关系表中，B行C列的前驱节点替换为A；

如何将A作为中间节点的情况都考虑到?

中间顶点数组{A,B,C,D,E,F,G} 取A（k[0]）—> …
出发顶点数组{A,B,C,D,E,F,G} 取A (i[0]) —>取B（i[1]）
终点数组{A,B,C,D,E,F,G} 遍历 (j=1,2,3,…) —>(j=1,2,3,…)
时间复杂度： O(n3),较高

代码实现

public class FloydAlgorithm {public static void main(String[] args) {char[] vertex = {'A','B','C','D','E','F','G'};//创建邻接矩阵int [][] matrix = new int[vertex.length][vertex.length];final int N = 65535;matrix[0] = new int[]{0,5,7,N,N,N,2};matrix[1] = new int[]{5,0,N,9,N,N,3};matrix[2] = new int[]{7,N,0,N,8,N,N};matrix[3] = new int[]{N,9,N,0,N,4,N};matrix[4] = new int[]{N,N,8,N,0,5,4};matrix[5] = new int[]{N,N,N,4,5,0,6};matrix[6] = new int[]{2,3,N,N,4,6,0};//创建图Graph graph = new Graph(vertex.length, matrix, vertex);graph.floyd();graph.show();}
}//图
class Graph{private char[] vertex;//存放顶点的数组private int [][] dis;//保存，从各个顶点出发到其它顶点的距离，最后的结果，也是保留在该数组private int [][] pre;//保存到达目标顶点的前驱顶点/*** @param length 大小* @param matrix 邻接矩阵* @param vertex 顶点数组*/public Graph(int length,int [][] matrix,char[]vertex) {this.vertex = vertex;this.dis = matrix;this.pre = new int[length][length];//对pre进行初始化，注意存放的是前驱顶点的下标for (int i = 0; i < length; i++) {Arrays.fill(pre[i],i);}}//显示pre数组和dis数组public void show(){char[] vetex = {'A','B','C','D','E','F','G'};for (int k = 0; k < dis.length; k++) {//先将pre数组输出的一行for (int i = 0; i < dis.length; i++) {System.out.print(vetex[pre[k][i]] + " ");}System.out.println();//输出dis数组的一行数据for (int i = 0; i < dis.length; i++) {System.out.print("("+vertex[k]+"到"+vertex[i]+"的最短路径"+dis[k][i]+") ");}System.out.println();System.out.println();}}//弗洛伊德算法public void floyd(){int len = 0 ;//变量保存//对中间顶点的遍历， k 就是中间顶点的下标for (int k = 0; k < dis.length; k++) {//从i顶点开始出发 [ A,B,C,D,E,F,G ]for (int i = 0; i < dis.length; i++) {//到达j顶点  [ A,B,C,D,E,F,G ]for (int j = 0; j < dis.length; j++) {len = dis[i][k]+dis[k][j];//求出i顶点出发，经过k中间顶点，到达j顶点距离if (len<dis[i][j]){//如果len < 两点的直连距离dis[i][j] = len;//更新距离pre[i][j] =pre[k][j];//更新前驱节点}}}}}
}