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

全栈程序员-站长 • 2022年4月20日上午6:00 • 未分类 • 阅读 68

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

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

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

对于无权的图来说：

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

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

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

对于带权的图来说：

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

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

Floyd算法

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

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

优缺点：

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

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

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

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

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

直接从i到j；
从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算法）[通俗易懂]

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

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

赞 (0)

全栈程序员-站长

0 0

嵌入式软件架构设计

嵌入式软件架构设计摘要在开发中一直觉得好的软件架构可以做到事半功倍而且可以做到代码复用和移植但是如果没有架构或者说架构很差那么移植将是很痛苦的事特别是对不熟悉改功能的人来讲还不如自己写呢移植不对那将是很头疼的事所以随着开发越来越多渐渐的发现我们考虑问题应该从广度和深度来考虑做新项目的时候更应该考虑到以后出现的可能性比如说需求变更底层变更所以这个时候软件的架构和程序模块化就很重要

全栈程序员-站长
2025年8月10日
2
emWin专题——emWin简介及模拟器的使用「建议收藏」

emWin专题——emWin简介及模拟器的使用「建议收藏」一、emWin简介1、emWin和ucGUI的关系记得刚上大学的时候接触到单片机领域的一个图形界面叫ucGUI，也是跑在STM32上的，后来过了没多久网上查资料发现大家都是用的emWIn了，了解了一下它们之间的关系，其实是同一个东西。emWIn是在ucGUI的基础上发展起来的，两者同属一家公司（SEEGER）开发，没错就是咱买的JLINK调试器的那家公司，以前旧版本的ucGUI是开源的，后…

全栈程序员-站长
2022年10月14日
3
ftp上传工具如何下载和使用像详细教程

ftp上传工具如何下载和使用像详细教程在学习网站搭建的过程中，我们必定会用到ftp上传工具，那么ftp工具是什么呢，我们该如何下载和使用呢？FTP（FileTransferProtocol），简称是文件传输的协议，我们可以用这个协议在互联网上做文件的双向传输，让我们用自己的计算机，可以链接到世界各地具有文件传输协议的ftp服务器进行连接，从而可以访问，传输下载大量的共享文件。同样我们可以从网站空间服务器中下载拷贝需要的文件到自己的…

全栈程序员-站长
2022年5月22日
39
CUDA性能优化—-kernel调优(nvprof工具的使用)

CUDA性能优化—-kernel调优(nvprof工具的使用)1、引言本文主要介绍并行分析，涉及掌握nvprof的几个metrics参数，所用的例子是CUDA性能优化—-线程配置一文中所提到的sumMatrix2D.cu例子。接下来本文会做一些列的试验，测试环境：TeslaM2070一块，CUDA6.0，操作系统：RedHat4.1.2-50，gccversion4.1.220080704首先回顾一下sumMatrix2D的kern…

全栈程序员-站长
2022年6月11日
32
优先队列「建议收藏」

优先队列「建议收藏」优先队列比如现实生活中的排队，就符合这种先进先出的队列形式，但是像急诊医院排队，就不可能按照先到先治疗的规则，所以需要使用优先队列。实现优先队列其实都是基于下面这些实现的：可以看出来实现优先队列最

全栈程序员-站长
2022年7月3日
24
9b9t服务器显示连接超时,在WebRTC中ICE连接失败

9b9t服务器显示连接超时,在WebRTC中ICE连接失败我们正在尝试将浏览器(客户端)与aiortc库(服务器，发送单个视频流)连接起来。目前，连接已成功建立(onsignalingstatechange稳定)。但是，媒体连接从未建立，因为ICE连接失败。这两台主机在同一个局域网上，并且已经验证了直接连接。使用的STUN服务器是STUN.l。谷歌：19302.在服务器上的日志如下：DEBUG:asyncio:Usingselector:Epol…

全栈程序员-站长
2022年5月22日
45

发表回复

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