Floyd算法

1、概念

Floyd算法（罗伯特·弗洛伊德命名）

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

空间复杂度：O（n^2）
时间复杂度：O（n^3）

2、作用

求多源最短路径，求传递闭包

3、算法过程

1.png

先生成图的邻接距阵与路径距阵
用d[i,j]表示i点到j点的最短距离，但i到j可能会经过K个顶点才能找到最短路径

则d[i][j]=d[i][k]+d[k][j],其中的k可能为多个点
历全部顶点，如果出现d[i][j]>d[i][k]+d[k][j],我们就用短的路径替换长的路径，如图中v1->v2直接走为4，用v1->v0->v2==3

即：
d[i][j]=d[i][k]+d[k][j];
p[i][j]=p[i][k];

为了找到全部结点对之间的最短路径,可以在路径计算过程中，取数组p[i][j]=p[i][k]用于记录每次的替换过程;

推算的结果如下图：

2.png

4、代码

/**
 * author: bobo
 * create time: 2018/12/28 5:59 PM
 * email: jqbo84@163.com
 */
public class Floyd {

     //最大值，表示不能直接通过
    public static final int I = 100;

    //邻接距阵
    public static int[][] d = new int[][]{
            {0, 2, 1, 5},
            {2, 0, 4, I},
            {1, 4, 0, 3},
            {5, I, 3, 0}
    };
    //路径
    public static int[][] p=new int[][]{
            {0,1,2,3},
            {0,1,2,3},
            {0,1,2,3},
            {0,1,2,3}
    };

    /**
     * 多源最短路径算法
     */
    public static void floyd(){
        for (int k = 0; k < d.length; k++) {
            for (int i = 0; i < d.length; i++) {
                for (int j = 0; j < d[i].length; j++) {
                    if(d[i][j]>d[i][k] + d[k][j]){
                        d[i][j] = d[i][k] + d[k][j];
                        //记录下每次修改后的路径
                        p[i][j] = p[i][k];
                    }
                }
            }
        }
    }

    /**
     * 打印修改后的矩阵
     */
    public static void printArray(int[][] array){
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array[i].length; j++) {
                System.out.print(array[i][j] + "  ");
            }
            System.out.println();
        }
        System.out.println("------------------------");
    }

    /**
     * 打印每个点到另一个点到最短路径
     */
    public static void printShortPath(){
        int k = 0;
        for (int i = 0; i < d.length; i++) {
            for (int j = 0; j < d[i].length; j++) {
                System.out.println("V" + i +"->V"+j+", weight: "+ d[i][j] + ", path: " + i);
                k = p[i][j];
                while(k!=j){
                    System.out.println("->"+k);
                    k=p[k][j];
                }
            }
            
        }
    }

}

5、测试及结果

@Test
public void main(){
    floyd();
    System.out.println("-------邻接矩阵--------");
    printArray(d);
    System.out.println("-------记录路径数组-----");
    printArray(p);

    System.out.println("-------打印每个节点到另个节点到路径-----");
    printShortPath();
}

结果：
-------邻接矩阵--------
0  2  1  4  
2  0  3  6  
1  3  0  3  
4  6  3  0  
------------------------
-------记录路径数组-----
0  1  2  2  
0  1  0  0  
0  0  2  3  
2  2  2  3  
------------------------
-------打印每个节点到另个节点到路径-----
V0->V0, weight: 0, path: 0
V0->V1, weight: 2, path: 0
V0->V2, weight: 1, path: 0
V0->V3, weight: 4, path: 0
->2
V1->V0, weight: 2, path: 1
V1->V1, weight: 0, path: 1
V1->V2, weight: 3, path: 1
->0
V1->V3, weight: 6, path: 1
->0
->2
V2->V0, weight: 1, path: 2
V2->V1, weight: 3, path: 2
->0
V2->V2, weight: 0, path: 2
V2->V3, weight: 3, path: 2
V3->V0, weight: 4, path: 3
->2
V3->V1, weight: 6, path: 3
->2
->0
V3->V2, weight: 3, path: 3
V3->V3, weight: 0, path: 3