弗洛伊德算法求两个任意顶点的最短路径

Bertha 。 2021-07-24 11:22 388阅读 0赞

# 一 弗洛伊德算法介绍 #

![2021040717424125.png][]

和Dijkstra算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径。

迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。

# 二 弗洛伊德算法 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 的最短路径 Lkj，是以同样的方式获得。

# 四 弗洛伊德(Floyd)算法图解 #

## 1 初始各顶点之间距离表 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70][]

## 2  初始顶点前驱关系 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1][]

## 3 第一轮循环中，以A(下标为:0)作为中间顶点，距离表和前驱关系更新情况 ##

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2][]

## 4 分析 ##

## 4.1 以 A 顶点作为中间顶点 ##

B->A->C的距离为12

C->A->B的距离为12

C->A->G的距离为9

G->A->C的距离为9

## 4.2 更换中间顶点，循环执行操作，直到所有顶点都作为中间顶点更新后，计算结束。 ##

# 五 实战 #

## 1 要求 ##

![20210407174432353.png][]

1 胜利乡有7个村庄(A, B, C, D, E, F, G)

2 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5公里

问：如何计算出各村庄到 其它各村庄的最短距离?

## 2 代码 ##

package com.atguigu.floyd;
    
    import java.util.Arrays;
    
    /**
    * @className: FloydAlgorithm
    * @description: 弗洛伊德算法
    * @date: 2021/4/7
    * @author: cakin
    */
    public class FloydAlgorithm {
        /**
         * 功能描述：弗洛伊德算法测试
         *
         * @param args 命令行
         * @author cakin
         * @date 2021/4/7
         */
        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 graph = new Graph(vertex.length, matrix, vertex);
            // 调用弗洛伊德算法
            graph.floyd();
            graph.show();
        }
    }
    
    /**
    * @className: Graph
    * @description: 图
    * @date: 2021/4/7
    * @author: cakin
    */
    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 数组
         *
         * @author cakin
         * @date 2021/4/7
         */
        public void show() {
            char[] vertex = {'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(vertex[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();
            }
        }
    
        /**
         * 功能描述：弗洛伊德算法
         *
         * @author cakin
         * @date 2021/4/7
         */
        public void floyd() {
            int len; // 变量保存距离
            // 对中间顶点遍历， k 就是中间顶点的下标 [A, B, C, D, E, F, G]
            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]
                            dis[i][j] = len; // 更新距离
                            pre[i][j] = pre[k][j]; // 更新前驱顶点
                        }
                    }
                }
            }
        }
    }

## 3 测试 ##

A A A F G G A
    (A到A的最短路径是0) (A到B的最短路径是5) (A到C的最短路径是7) (A到D的最短路径是12) (A到E的最短路径是6) (A到F的最短路径是8) (A到G的最短路径是2)
    
    B B A B G G B
    (B到A的最短路径是5) (B到B的最短路径是0) (B到C的最短路径是12) (B到D的最短路径是9) (B到E的最短路径是7) (B到F的最短路径是9) (B到G的最短路径是3)
    
    C A C F C E A
    (C到A的最短路径是7) (C到B的最短路径是12) (C到C的最短路径是0) (C到D的最短路径是17) (C到E的最短路径是8) (C到F的最短路径是13) (C到G的最短路径是9)
    
    G D E D F D F
    (D到A的最短路径是12) (D到B的最短路径是9) (D到C的最短路径是17) (D到D的最短路径是0) (D到E的最短路径是9) (D到F的最短路径是4) (D到G的最短路径是10)
    
    G G E F E E E
    (E到A的最短路径是6) (E到B的最短路径是7) (E到C的最短路径是8) (E到D的最短路径是9) (E到E的最短路径是0) (E到F的最短路径是5) (E到G的最短路径是4)
    
    G G E F F F F
    (F到A的最短路径是8) (F到B的最短路径是9) (F到C的最短路径是13) (F到D的最短路径是4) (F到E的最短路径是5) (F到F的最短路径是0) (F到G的最短路径是6)
    
    G G A F G G G
    (G到A的最短路径是2) (G到B的最短路径是3) (G到C的最短路径是9) (G到D的最短路径是10) (G到E的最短路径是4) (G到F的最短路径是6) (G到G的最短路径是0)

[2021040717424125.png]: /images/20210724/8549a9d2e5e64c288b8e73a44fd042b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70]: /images/20210724/0e4d5a1447d5482fb81b78862259f9f6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 1]: /images/20210724/91cd3cca2b2a42acb0262e27c00e14c9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2NoZW5ncWl1bWluZw_size_16_color_FFFFFF_t_70 2]: /images/20210724/34051874b3064ede8a6bc903c400a6e8.png
[20210407174432353.png]: /images/20210724/06459ba13f3e4d33af3b0053d7b482db.png