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

SSM框架下一个简单的模糊查询（超级详细)

SSM框架下一个简单的模糊查询（超级详细)引言:模糊查询作为后台常用的一种查询方式，我们可以根据相应的关键字对其检索,从而获得所需要的记录,本次模糊查询我们通过名字的任何一个字段进行匹配查询。另外声明，源码就是以下的部分，直接复制就可以使用了。此外，想要模糊查询，最好学会分页查询，分页查询我用了两种方法，一种是利用的pageHelper，另一种没用到插件.需要源码的，或者demo，在我的资源下载，需要远程帮忙的可以加我QQ…

全栈程序员-站长
2022年5月30日
74
多模态机器学习综述翻译(转载)

多模态机器学习综述翻译(转载)文章：《MultimodalMachineLearning:ASurveyandTaxonomy》多模态机器学习综述【摘要】我们对世界的体验是多模式的-我们看到物体，听到声音，感觉到纹理，闻到气味和尝到味道。模态是指某种事物发生或经历的方式，并且当研究问题包括多种这样的形式时，研究问题被描述为多模态。为了使人工智能在理解我们周围的世界方面取得进展，它需要能够一起解释这种多模信号。多模式机器学习旨在构建可以处理和关联来自多种模态信息的模型。这是一个充满活力的多学科领域，具有越来越重要的意义和非

全栈程序员-站长
2022年6月21日
52
webservice安全策略[通俗易懂]

webservice安全策略[通俗易懂]前些日子公司的应用要和合作方对接，我参与了webservice这块的工作，在访问量很小的情况下基本上完成了功能，但安全这块没有找到合适的方案，所以自己做了些旁门左道的设想，不一定合理和完善，希望能起个

全栈程序员-站长
2022年7月2日
29
python的遍历字符串的方式

python的遍历字符串的方式1）直接进行遍历strs=’abcd’forchinstrs:print(ch)2)利用下标遍历strs=’abcd’forindex,chinenumerate(strs):print(index,end=”)print(ch)3)利用range进行遍历strs=’abcd’forindexin…

全栈程序员-站长
2022年6月22日
49
wordpress自定义搜索

wordpress自定义搜索默认下，wordpress的搜索范围只有文章的标题和文章内容，无法搜索自定义字段中的内容，现实情况是很多情况下我们可能会要搜索自定义字段中的内容。如果只是想搜索一到两个自定义字段中的内容，可以使用wordpress的内置函数meta_query变量。12345678910111213141516171

全栈程序员-站长
2022年7月14日
68
ASP.NET中DropDownList 的使用

ASP.NET中DropDownList 的使用1.如何避免DropDownList下拉框中重复值出现？AppendDataBoundItems：为是否填加重复值。真为添加，假为不填加将DropDownList控件中AppendDataBoundItems属性设置为“False”即可。 2.如何给DropDownList添加项？//1.PreRender事件，在呈现该页前激发protectedvoidDropDow…

全栈程序员-站长
2022年10月17日
0

发表回复

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