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

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

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

 

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

对于无权的图来说:

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

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

 

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

对于带权的图来说:

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

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

 

 

Floyd算法

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

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

 

优缺点:

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

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

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

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

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

  1. 直接从i到j;
  2. 从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算法)[通俗易懂]

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

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/124830.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • Redis 在windows中启动

    Redis 在windows中启动

    2021年10月16日
  • Spring Security CAS认证

    Spring Security CAS认证13.7CAS认证13.7.1概述JA-SIG生产一种称为CAS的企业级单点登录系统。与其他计划不同,JA-SIG的中央身份验证服务是开源的,广泛使用的,易于理解,独立于平台,并支持代理功能。SpringSecurity完全支持CAS,并提供从SpringSecurity的单应用程序部署到企业级CAS服务器保护的多应用程序部署的轻松迁移路径。您可以在https://www.ape…

  • gbk编码表_河北十一选五五码基本分布图

    gbk编码表_河北十一选五五码基本分布图1.GBK码位分布图2.GBK码位说明GBK亦採用双字节表示,整体编码范围为8140-FEFE,首字节在81-FE之间,尾字节在40-FE之间,剔除xx7F一条线。总计23940

  • C++ VS2012 内存泄露检测

    在VS2012中添加部分代码,可以起到检测内存泄露的作用。今天刚刚收到的解决办法,原理还不是很清楚。先分享出来1.头文件中添加以下代码2.main函数中添加程序在DEBUG模式下运行时,就

    2021年12月25日
  • Google 地图切片URL地址解析

    Google 地图切片URL地址解析一、Google地图切片的投影方式及瓦片索引机制1.地图投影Google地图采用的是Web墨卡托投影(如下图),为了方便忽略了两极变形较大的地区,把世界地图做成了一个边长等于赤道周长的正方形(赤道半径为6378137米),原点在正方形中心,即经纬度为(0,0)处。Web墨卡托投影的X,Y坐标取值范围为:[-20037508.3427892,20037508.3427892]…

  • 数组转集合集合转数组_集合转json

    数组转集合集合转数组_集合转json一、数组转集合:String[]array={“1″,”2″,”3″,”4”};List<String>list=Arrays.asList(array);ListarrList=newArrayList(list);arrList.add(“5”);二、集合转数组:…

发表回复

您的电子邮箱地址不会被公开。

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