图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」概述Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法是一种在具有正或负边缘权重(但没有负环)的加权图中找到最短路径的算法,即支持负权值但不支持负权环。弗洛伊德算法采用的是动态规划思想,其状态转移方程如下:其中matrix[i,j]表示i到j的最短距离,k是穷举i到j之间可能经过的中间点,当中间点为k时,……

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全家桶1年46,售后保障稳定

概述

Floyd算法又称为插点法,是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法,与Dijkstra算法类似。该算法是一种在具有正或负边缘权重(但没有负环)的加权图中找到最短路径的算法,即支持负权值但不支持负权环。弗洛伊德算法采用的是动态规划思想,其状态转移方程如下: 

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

其中matrix[i,j]表示i到j的最短距离,k是穷举i到j之间可能经过的中间点,当中间点为k时,对整个矩阵即从i到j的路径长度进行更新,对所有可能经过的中间点进行遍历以得到全局最优的最短路径。算法的单个执行将找到所有顶点对之间的最短路径长度,与迪杰斯特阿拉算法的计算目标有一些差异,迪杰斯特拉计算的是单源最短路径,而弗洛伊德计算的是多源最短路径,其时间复杂度为O(n³)。虽然它不返回路径本身的细节,但是可以通过对算法的简单修改来重建路径,我们利用这个思想,通过递归的方式访问每条路径经过的中间节点,对最终的路径进行输出。

算法描述

在有向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到V钟任意两点之间的路径长度最小值。

算法流程

本节将对算法流程进行模拟,设置Graph为包含7个顶点和9条边的有向无环图,Graph如下:

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

弗洛伊德算法选取某个节点k作为i到j需要经过的中间节点,通过比较d(i,k)+d(k,j)和现有d(i,j)的大小,将较小值更新为路径长度,对k节点的选取进行遍历,以得到在经过所有节点时i到j的最短路径长度,通过不断加入中间点的方式更新最短路径。同时在path数组中存储i到j所经过的中间节点k,用于最后递归调用输出路径结果。

算法步骤如下:

1、初始化矩阵。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

2、选取0号节点作为中间点,初始化矩阵。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

3、选取1号节点作为中间点,更新矩阵,通过两层循环计算(i->1),(1->j)的路径是否比目前i到j的路径长度更短。此时可以将矩阵数值看作是将0、1作为中间点获得的多源最短路径长度。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

4、选取2号节点作为中间点,更新矩阵,通过两层循环计算(i->2),(2->j)的路径是否比目前i到j的路径长度更短。此时可以将矩阵数值看作是将0、1、2作为中间点获得的多源最短路径长度。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

5、选取3号节点作为中间点,更新矩阵,通过两层循环计算(i->3),(1->3)的路径是否比目前i到j的路径长度更短。此时可以将矩阵数值看作是将0、1、2、3为中间点获得的多源最短路径长度。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

6、选取4号节点作为中间点,更新矩阵,通过两层循环计算(i->4),(4->j)的路径是否比目前i到j的路径长度更短。此时可以将矩阵数值看作是将0、1、2、3、4作为中间点获得的多源最短路径长度。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

7、选取5号节点作为中间点,更新矩阵,通过两层循环计算(i->5),(5->j)的路径是否比目前i到j的路径长度更短。此时可以将矩阵数值看作是将0、1、2、3、4、5作为中间点获得的多源最短路径长度。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

8、选取6号节点作为中间点,更新矩阵,通过两层循环计算(i->6),(6->j)的路径是否比目前i到j的路径长度更短。此时可以将矩阵数值看作是将所有节点作为中间点获得的多源最短路径长度,遍历结束,得到最后结果。

图解最短路径之弗洛伊德算法(Java实现)「建议收藏」

算法实现

public class FloydAlgorithm {
    public static int MaxValue = 100000;
    public static int[][] path;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入顶点数和边数:");
        //顶点数
        int vertex = input.nextInt();
        //边数
        int edge = input.nextInt();

        int[][] matrix = new int[vertex][vertex];
        //初始化邻接矩阵
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = MaxValue;
            }
        }

        //初始化路径数组
        path = new int[matrix.length][matrix.length];

        //初始化边权值
        for (int i = 0; i < edge; i++) {
            System.out.println("请输入第" + (i + 1) + "条边与其权值:");
            int source = input.nextInt();
            int target = input.nextInt();
            int weight = input.nextInt();
            matrix[source][target] = weight;
        }

        //调用算法计算最短路径
        floyd(matrix);
    }

    //非递归实现
    public static void floyd(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                path[i][j] = -1;
             }
        }

        for (int m = 0; m < matrix.length; m++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
                        matrix[i][j] = matrix[i][m] + matrix[m][j];
                        //记录经由哪个点到达
                        path[i][j] = m;
                    }
                }
            }
        }

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (i != j) {
                    if (matrix[i][j] == MaxValue) {
                        System.out.println(i + "到" + j + "不可达");
                    } else {
                        System.out.print(i + "到" + j + "的最短路径长度是:" + matrix[i][j]);
                        System.out.print("最短路径为:" + i + "->");
                        findPath(i, j);
                        System.out.println(j);
                    }
                }
            }
        }
    }

    //递归寻找路径
    public static void findPath(int i, int j) {
        int m = path[i][j];
        if (m == -1) {
            return;
        }

        findPath(i, m);
        System.out.print(m + "->");
        findPath(m, j);
    }
}

Jetbrains全家桶1年46,售后保障稳定

样例输入:

7 10

0 1 6

1 2 5

0 3 2

3 1 7

3 4 5

1 2 5

1 5 3

5 2 3

5 4 2

4 6 1

Q&A

问:算法中的三层for循环,每一层分别控制什么?

答:第一层循环设置中间点k,第二层循环设置起始点i,第三层循环设置结束点j。

问:为什么弗洛伊德算法支持负权值?

答:因为路径更新是根据新值和旧值比较获得的,最终的结果都是在最后一次迭代过程中对全局进行更新而得到的,中间的每次迭代只是一次局部调整而非最终结果。而不像迪杰斯特拉采用的贪心策略,每一次迭代都确定出一条最短路径,负权的出现使得不能保证每次迭代都是最优解。

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/234084.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 常见的关系型数据库和非关系型数据及其区别是什么_mysql数据库数据类型

    常见的关系型数据库和非关系型数据及其区别是什么_mysql数据库数据类型&#13; 一、关系型数据库&#13;&#13; &#13;关系型数据库最典型的数据结构是表,由二维表及其之间的联系所组成的一个数据组织优点:1、易于维护:都是使用表结构,格式一致;2、使用方便:SQL语言通用,可用于复杂查询;3、复杂操作:支持SQL,可用于一个表以及多个表之间非常复杂的查询。缺点:1、读写性能比较差,尤其是海量数据的高效率读写;2、固定的表结构,灵活…

    2022年10月23日
  • Java常用代码_计算机植入木马程序

    Java常用代码_计算机植入木马程序1.字符串有整型的相互转换Stringa=String.valueOf(2);//integertonumericstringinti=Integer.parseInt(a);//numericstringtoanint2.向文件末尾添加内容BufferedWriterout=null;try{out=newBu…

  • Office2010序列号_序列号被更换能升级吗

    Office2010序列号_序列号被更换能升级吗Office2010修改|更改|更换序列号的办法http://blog.csdn.net/microtong佟强2010年9月27日Office2010安装的时候,填了个序列号,安装成功了。但是后来激活没有成功。怎么更换序列号呢?进入控制面板,选择程序和功能,找到Office2010,点击右键,选择更改,参看下图。

  • dubbo负载均衡策略(XML、注解、SpringBoot配置)「建议收藏」

    dubbo负载均衡策略(XML、注解、SpringBoot配置)「建议收藏」本示例是在上一篇文章中搭建的实例来讲解,详情先查看:SpringBoot集成dubbo最新实战教程:dubbo-spring-boot-starter一.简介在集群负载均衡时,Dubbo提供了多种均衡策略,默认为random随机调用。二.负载均衡策略1.RandomLoadBalance随机,按权重设置随机概率。 在一个截面上碰撞的概率高,但调用量越大分布越均…

  • 微型计算机原理与接口技术第六版周荷琴课后答案_微机原理与接口技术第五版周荷琴

    微型计算机原理与接口技术第六版周荷琴课后答案_微机原理与接口技术第五版周荷琴微型计算机原理与接口技术第六版课后答案【内容简介】本书是为中国科学技术大学工科电子类专业本科生学习“微型计算机原理与系统”课程而编写的教材。微型计算机原理与接口技术第六版周荷琴答案从初版开始至每次修订再版,都是作者在参考国内外大量文献、资料的基础之上,吸取各家之长,并结合教学团队多年教学和应用研究的经验,精心组织编写而成的,可谓自成一体。全书内容丰富,图文并茂,讲述深入浅出,通俗易懂,并附有大量的实例和习题,部分习题还给出了解题提示,既可用作教材,也适合于自学,先后被列入“普通高等教育*规划教材”和“

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号