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

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

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

小明加密通道进入_门禁系统跟闸机通道的区分是什么？功能是一样吗

小明加密通道进入_门禁系统跟闸机通道的区分是什么？功能是一样吗门禁系统属于一卡通系统的范畴。它是以中央处理器为核心，由控制器、信息采集器和电控锁组成的控制网络系统。通过系统的信息读取和处理，实现了各种门锁开关的自动控制。根据信息阅读的方式可以分为：插卡式、感应式、图像检测式、双眼虹膜识别式等。他们的技术含量和体系工程预算顺序先后提高。且融合三辊闸、摆闸、翼闸等多种入口处监管设施，保持更智能。门禁用到ID和IC两种卡片，IC门禁有加密功能，存贮容量也大，广泛用…

全栈程序员-站长
2022年6月11日
65
oracle数据文件恢复步骤_oracle数据库文件扩展名

oracle数据文件恢复步骤_oracle数据库文件扩展名1、基于linux操作系统文件恢复条件：1、误强制删除linux下的数据文件（rm-rf）。2、未重启数据库或操作系统。3、数据库是归档模式恢复原理：句柄恢复文件–因为我们的操作系统是linux，当数据文件从操作系统级别被rm掉，但之前打开该文件的进程仍然持有相应的文件句柄，所以指向的文件仍然可以读写，并且该文件的文件描述符可以从/proc目录中获得。…

全栈程序员-站长
2022年9月23日
4
[转]搭建Windows下Java Web开发环境

[转]搭建Windows下Java Web开发环境

全栈程序员-站长
2021年8月16日
56
maven快速入门_maven如何使用

maven快速入门_maven如何使用企业级架构框架图之前我们关注的是前端的解决方案（涉及到的技术有H5、CSS3、JavaScript，CSS升级为Bootstrap再升级到ElementUI，JavaScript升级到jQuery再升级到Vue+NodeJS）现在开始我们开始关注后端的解决方案，也就是服务器端到底干了什么，哪些技术来支持（SpringBoot、Maven、SpringMVC、Spring、Mybatis）。这样前后端都学习完，整个软件项目所需要的基本技术就全线贯通，就可以自己独立完成企业级项目的开发了。下面我们来描

全栈程序员-站长
2022年8月22日
6
Anaconda 安装python第三方库的各类方法

Anaconda 安装python第三方库的各类方法Anaconda安装python第三方库的各类方法之前的文章讲了有关anaconda的一些介绍和安装，第三方源也介绍了，本文介绍Anaconda安装python第三发库的各类方法第一种：1.双击打开AnacondaNavigator，选择Environments界面2.然后选择Notinstall，在右边搜索框进行搜索需要的库包名字，选择需要的库包，选择apply进行安装第二种1.双击打开AnacondaPrompt（Anaconda3）（打开系统菜单找到anaconda就能看到）

全栈程序员-站长
2022年10月14日
4
SDL2来源分析3：渲染（SDL_Renderer）

SDL2来源分析3：渲染（SDL_Renderer）

全栈程序员-站长
2022年1月11日
52

发表回复

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