图解最短路径之弗洛伊德算法(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)


相关推荐

  • J2EE架构师之路[通俗易懂]

    J2EE架构师之路[通俗易懂]不经意的回首,工作进入第五个年头了,发现走过了从Java程序员到J2EE架构师的历程。发现电脑上安装了各种各样的J2EE工具:JBuilder,WSAD,Eclipse,Rose,Together,Weblogic,Jtest,Optimizator,Mysql…发现电脑上保存了各种各样的OpenSource项目:Tomcat,JBoss,Ant,Hibernate,Spr

  • linux下邮件发送服务器日志「建议收藏」

    linux下邮件发送服务器日志「建议收藏」sendsyslog.py //发送邮件调用程序#!/usr/bin/envpython#-*-coding:UTF-8-*-importosimportsyssys.path.append(os.getcwd())importsendlog############sendlog.py//发送邮件配置程序#

  • 二叉树 二叉搜索树_判断二叉树是否是二叉排序树

    二叉树 二叉搜索树_判断二叉树是否是二叉排序树原题链接一棵二叉搜索树可被递归地定义为具有下列性质的二叉树:对于任一结点,其左子树中所有结点的键值小于该结点的键值;其右子树中所有结点的键值大于等于该结点的键值;其左右子树都是二叉搜索树。所谓二叉搜索树的“镜像”,即将所有结点的左右子树对换位置后所得到的树。给定一个整数键值序列,现请你编写程序,判断这是否是对一棵二叉搜索树或其镜像进行前序遍历的结果。输入格式:输入的第一行给出正整数 N(≤1000)。随后一行给出 N 个整数键值,其间以空格分隔。输出格式:如果输入序列是对一棵二叉搜索树或

  • javamethod用法_method

    javamethod用法_methodClass类getMethod()方法getMethod()方法在java.lang包中可用。getMethod()方法用于返回Method对象,这些对象指示该类的给定公共方法或由此Class对象表示的接口。getMethod()方法是一种非静态方法,只能通过类对象访问,如果尝试使用类名称访问该方法,则会收到错误消息。getMethod()方法在返回Method对象时可能会引发异常。NoSuchM…

  • 随 机 数 算 法

    随 机 数 算 法一、随机数概述在password技术中,随机序列是非常重要的,比方密钥产生、数字签名、身份认证和众多的password学协议等都要用到随机序列。所以产生高质量的随机数序列对信息的安全性具有十分关键的数

  • 个人博客网站搭建[通俗易懂]

    个人博客网站搭建[通俗易懂]个人博客网站搭建VuePress介绍本人的个人博客网站,网站地址,是基于VuePress进行搭建。什么是VuePress根据官网:VuePress由两部分组成:第一部分是一个极简静态网站生成

发表回复

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

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