弗洛伊德算法 订阅
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 [1] 展开全文
Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。 [1]
信息
空间复杂度
O(n^2)
作    用
求多源最短路径,求传递闭包
别    名
Roy-Warshall算法
中文名
弗洛伊德算法
时间复杂度
O(n^3)
外文名
Floyd(Floyd-Warshall)
Floyd算法简介
在计算机科学中,Floyd-Warshall算法是一种在具有正或负边缘权重(但没有负周期)的加权图中找到最短路径的算法。算法的单个执行将找到所有顶点对之间的最短路径的长度(加权)。 虽然它不返回路径本身的细节,但是可以通过对算法的简单修改来重建路径。 该算法的版本也可用于查找关系R的传递闭包,或(与Schulze投票系统相关)在加权图中所有顶点对之间的最宽路径。Floyd-Warshall算法是动态规划的一个例子,并在1962年由Robert Floyd以其当前公认的形式出版。然而,它基本上与Bernard Roy在1959年先前发表的算法和1962年的Stephen Warshall中找到图形的传递闭包基本相同,并且与Kleene的算法密切相关 在1956年)用于将确定性有限自动机转换为正则表达式。算法作为三个嵌套for循环的现代公式首先由Peter Ingerman在1962年描述。该算法也称为Floyd算法,Roy-Warshall算法,Roy-Floyd算法或WFI算法。 [2] 
收起全文
精华内容
下载资源
问答
  • 弗洛伊德算法

    万次阅读 2021-04-07 13:53:37
    思路分析 代码实现 ... import java.util.Arrays; ...public class FloydAlgorithm { public static void main(String[] args) { ... char[] vertex={'A','B','C','D','E','F','G'};... int[][] matrix

    思路分析

    在这里插入图片描述
    在这里插入图片描述

    在这里插入图片描述

    代码实现

    package com.atguigu.floyd;
    
    import java.util.Arrays;
    
    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 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[] 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(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++) {//[A, B, C, D, E, F, G]
                //从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];//更新前驱顶点
                        }
                    }
                }
    
            }
    
        }
    
    
    
    
    }
    
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,741
精华内容 2,696
关键字:

弗洛伊德算法