1. 全栈程序员必看首页

最短路径模板+解析——（FLoyd算法）[通俗易懂]

全栈程序员-用户IM • • 未分类

最短路径模板+解析——（FLoyd算法）[通俗易懂]对于无权的图来说：若从一顶点到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。对于带权的图来说：考虑路径上各边上的权值，则通常把…

大家好，又见面了，我是你们的朋友全栈君。

 

最短路径模板+解析——（FLoyd算法）[通俗易懂]

对于无权的图来说：

若从一顶点到另一顶点存在着一条路径，则称该路径长度为该路径上所经过的边的数目，它等于该路径上的顶点数减1。

由于从一顶点到另一顶点可能存在着多条路径，每条路径上所经过的边数可能不同，即路径长度不同，我们把路径长度最短（即经过的边数最少）的那条路径叫做最短路径，其路径长度叫做最短路径长度或最短距离。

 

最短路径模板+解析——（FLoyd算法）[通俗易懂]

对于带权的图来说：

考虑路径上各边上的权值，则通常把一条路径上所经边的权值之和定义为该路径的路径长度或称带权路径长度。

 从源点到终点可能不止一条路径，把带权路径长度最短的那条路径称为最短路径，其路径长度（权值之和）称为最短路径长度或者最短距离。

 

 

Floyd算法

Floyd算法（Floyd-Warshall algorithm）又称为弗洛伊德算法、插点法，是解决给定的加权图中顶点间的最短路径的一种算法，可以正确处理有向图或负权的最短路径问题，同时也被用于计算有向图的传递闭包。该算法名称以创始人之一、1978年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名。

适用范围：无负权回路即可，边权可正可负，运行一次算法即可求得任意两点间最短路。

 

优缺点：

Floyd算法适用于APSP(AllPairsShortestPaths)，是一种动态规划算法，稠密图效果最佳，边权可正可负。此算法简单有效，由于三重循环结构紧凑，对于稠密图，效率要高于执行|V|次Dijkstra算法。

优点：容易理解，可以算出任意两个节点之间的最短距离，代码编写简单

缺点：时间复杂度比较高，不适合计算大量数据。

时间复杂度:O(n^3)；空间复杂度:O(n^2)；

任意节点i到j的最短路径两种可能：

  1. 直接从i到j；
  2. 从i经过若干个节点k到j。

map（i，j）表示节点i到j最短路径的距离，对于每一个节点k，检查map（i，k）+map（k，j）小于map(i，j),如果成立，map（i，j） = map（i，k）+map（k，j）；遍历每个k，每次更新的是除第k行和第k列的数。

步骤：

第1步：初始化map矩阵。
矩阵中map[i][j]的距离为顶点i到顶点j的权值；

如果i和j不相邻，则map[i][j]=∞。

如果i==j，则map[i][j]=0;                                          
第2步：以顶点A(假设是第1个顶点)为中介点，若a[i][j] > a[i][1]+a[1][j]，则设置a[i][j]=a[i][1]+a[1][j]。

最短路径模板+解析——（FLoyd算法）[通俗易懂]

无向图构建最短路径长度邻接矩阵：

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

 

 

核心代码：

最短路径模板+解析——（FLoyd算法）[通俗易懂]

有向图构建最短路径长度邻接矩阵：

最短路径模板+解析——（FLoyd算法）[通俗易懂]

步骤：

最短路径模板+解析——（FLoyd算法）[通俗易懂]

 

 

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

 

最短路径模板+解析——（FLoyd算法）[通俗易懂]

 

最短路径模板+解析——（FLoyd算法）[通俗易懂]

 

最短路径模板+解析——（FLoyd算法）[通俗易懂]

最短路径模板+解析——（FLoyd算法）[通俗易懂]

核心代码：

最短路径模板+解析——（FLoyd算法）[通俗易懂]

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

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

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

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

赞 (0)
全栈程序员-用户IM全栈程序员-用户IM
0 0


相关推荐

  • mysql insert sql

    mysql insert sql

    mysql insert sql

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年3月4日
  • .NET API for RabbitMQ and ActiveMQ

    .NET API for RabbitMQ and ActiveMQ

    .NET API for RabbitMQ and ActiveMQ

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年1月15日
  • windows10查看端口被占用_win10端口被占用怎么解决

    windows10查看端口被占用_win10端口被占用怎么解决

    windows10查看端口被占用_win10端口被占用怎么解决1、查看windows所有端口进程同时按下Win+R，接着在对话框中输入“cmd”，按下回车键打开命令提示符窗口，然后在窗口中输入netstat-ano按下回车键，之后就会显示所有的端口占用情况。2、如果是要查询指定的端口占用情况的话，可以在命令提示符窗口中继续输入netstat-aon|findstr”提示的端口”这里的提示的端口假设为8080，那么就输入命令netstat-aon|findstr”8080″按下回车键之后就可以看见列表中的PID然后.

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年7月27日
  • php 5.0 与7.0有什么区别

    php 5.0 与7.0有什么区别

    php 5.0 与7.0有什么区别

    全栈程序员-用户IM 全栈程序员-用户IM
    2021年9月25日
  • SSDP协议_固态硬盘两种协议

    SSDP协议_固态硬盘两种协议

    SSDP协议_固态硬盘两种协议SSDP，即简单服务发现协议（SSDP，SimpleServiceDiscoveryProtocol），是一种应用层协议，是构成通用即插即用(UPnP)技术的核心协议之一。 实现简单服务发现协议是在HTTPU和HTTPMU的基础上实现的协议。按照协议的规定，当一个控制点（客户端）接入网络的时候，它可以向一个特定的多播地址的SSDP端口使用M-SEARCH方法发送“ssdp:…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月11日
  • 守护线程和非守护线程_java守护线程的作用

    守护线程和非守护线程_java守护线程的作用

    守护线程和非守护线程_java守护线程的作用Java中有两类线程：UserThread(用户线程)、DaemonThread(守护线程)用户线程即运行在前台的线程，而守护线程是运行在后台的线程。守护线程作用是为其他前台线程的运行提供便利服务，而且仅在普通、非守护线程仍然运行时才需要，比如垃圾回收线程就是一个守护线程。当VM检测仅剩一个守护线程，而用户线程都已经退出运行时，VM就会退出，因为没有如果没有了被守护这，也就没有继续运行程…

    全栈程序员-用户IM 全栈程序员-用户IM
    2022年10月15日

发表回复

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

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