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

MFC中数据格式转化：CString转换String、String转换CString、int转换CString……「建议收藏」

MFC中数据格式转化：CString转换String、String转换CString、int转换CString……

全栈程序员-站长
2022年2月7日
58
Oracle中文全文索引[通俗易懂]

环境Oracle9.0.2 Oracle全文索引的基本知识一、历史背景Oracle数据库的全文检索技术已经非常完美，OracleText使Oracle9i具备了强大的文本检索能力和智能化的文本管理能力。OracleText是Oracle9i采用的新名称，在Oracle8/8i中它被称作OracleinterMediaText，在Oracle8以前它的名称是Oracle

全栈程序员-站长
2022年4月11日
33
Postman报错Unsupported Media Type

Postman报错Unsupported Media Type报错信息如下：{“timestamp”:”2018-12-06T01:37:11.184+0000″,”status”:415,”error”:”UnsupportedMediaType”,”message”:”Contenttype’text/plain;charset=UTF-8’notsupported”,”path”:”/testgu/ycyzha…

全栈程序员-站长
2022年5月9日
225
实战：springboot整合rabbitMQ「建议收藏」

实战：springboot整合rabbitMQ「建议收藏」一、RabbitMQ简述与其docker安装这里主要讲解实战整合rabbitMQ，了解RabbitMQ简述与其docker安装请点击：传送门二、springboot整合rabbitMQ1.新建springboot项目2.pom:主要添加以下两个依赖<dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-

全栈程序员-站长
2022年5月14日
39
真实揭露：一段激情视频裸聊被骗的经历

真实揭露：一段激情视频裸聊被骗的经历故事发生前几天放假的时候，那天我正在海边散步，有个人加我微信，备注了求助信息。当我通过了他的好友验证请求，他给我发来这样一段话。出于对luo聊诈骗套路的好奇，我对他的这段经历进行深入的了解。本文已获得受害者本人的授权，将这段视频luo聊被骗经历改编成故事发出来，希望能警醒更多的人。扒一扒视频luo聊受骗的经历只是无聊打发时间，在uki上和陌生人玩假扮情侣聊天。碰到个人，一上来就莫名…

全栈程序员-站长
2022年5月15日
29
mqttnet 详解_mqttnet3.0用法

mqttnet 详解_mqttnet3.0用法1///开源库地址：https://github.com/chkr1011/MQTTnet2///对应文档：https://github.com/chkr1011/MQTTnet/wiki/Client34usingMQTTnet;5usingMQTTnet.Client;6usingMQTTnet.Client.Options;7usingSystem;8usingSystem.T…

全栈程序员-站长
2022年6月25日
48

发表回复

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