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

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

最短路径模板+解析——（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

数据库建立索引常用的规则

数据库建立索引常用的规则数据库建立索引常用的规则如下：1、表的主键、外键必须有索引； 2、数据量…

全栈程序员-站长
2022年7月24日
MyBatis-Spring整合注入SqlSessionTemplate

MyBatis-Spring整合注入SqlSessionTemplateSqlSessionTemplateSqlSessionTemplate是MyBatis-Spring的核心。这个类负责管理MyBatis的SqlSession,调用MyBatis的SQL方法,翻译异常。SqlSessionTemplate是线程安全的。最终要的是让spring获取到SqlSessionTemplate然后注入给工具类，让工具类操作数据库

全栈程序员-站长
2022年5月31日
键盘win键无法使用，win+r不生效、win键没反应、Windows键失灵万能解决方案

键盘win键无法使用，win+r不生效、win键没反应、Windows键失灵万能解决方案Windows键失灵的几种解决方案今早用抹布擦洗键盘，不断拍打键盘，清理完成后发现键盘win键无法使用1、请先按住键盘上的FN键不放，然后按一下win键，即可恢复正常2、有些笔记本是fn+f2，或者是fn+f6锁了win键，导致win键按了没反应，再按一次即可正常3、有些机械键盘的游戏模式会屏蔽win键可以使用fn+有游戏图标的那个键即可恢复正常4、根据不同的键盘和电脑，可能有一些别的特殊按键也会锁定win键，造成无法使用，可以依次尝试fn+某些功能键来解锁5、万能终…

全栈程序员-站长
2022年5月4日
自定义 DataLoader[通俗易懂]

自定义 DataLoader[通俗易懂]自定义DataLoader如数据输入一文所介绍，OneFlow支持两种数据加载方式：直接使用NumPy数据或者使用DataLoader及其相关算子。在大型工业场景下，数据加载容易成为训练的瓶颈。在其它的框架中，数据加载流水线往往作为单独的模块存在，需要针对不同场景进行调整，通用性不高。在OneFlow中，DataLoader及相关预处理算子，与其它普通算子地位等同，可以享受与其它算子一样的流水加速效果，轻松解决大规模数据加载的痛点。在OneFlow中使用DataLoader

全栈程序员-站长
2022年5月23日
Spring、SpringBoot和SpringCloud的关系

Spring、SpringBoot和SpringCloud的关系1、SpringBoot是Spring的一套快速配置脚手架，可以基于SpringBoot快速开发单个微服务。2、SpringCloud是一个基于SpringBoot实现的云应用开发工具。3、SpringBoot专注于快速、方便集成的单个个体，SpringCloud是关注全局的服务治理框架。4、SpringBoot使用了默认大于配置的理念，很多集成方案已经帮你选择好了，能不配置就…

全栈程序员-站长
2022年5月29日
@RequestMapping拦截多个请求

@RequestMapping拦截多个请求

全栈程序员-站长
2021年7月19日

发表回复

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