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];//更新前驱节点
                    }
                }
            }
        }
    }
}