当前位置:首页 > 算法 > 正文内容

【算法】最短路径算法——Floyed-Warshell算法

亿万年的星光3年前 (2022-02-06)算法1969

如下图所示,我们把边带有权值的图称为带权图。

边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相怜。最短路径就是指连接两点的这些路径中最短的一条。

【注意】边的权值可以为负。当出现负边权时,有些算法不适用。


Floyed-Warshall算法

    简称Floyed(弗洛伊德)算法,是最简单的最短路径算法,可以计算出图中任意两点间的最短路径。Floyed的时间复杂度是N3,适用于出现负边权的情况。

【算法描述】

(a)初始化:点u、v如果有边相怜,则dis[u][v]=w[u][v]

         如果不相连,则dis[u][v]=0x7fffffff( 即INT_MAX)

  (b) 

for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(dis[i][j]>dis[i][k]+dis[k][j]){
				dis[i][j]=dis[i][k]+dis[k][j] 
			}


(c)算法结束:dis[i][j]得出的就是从i到j的最短路径。


【算法分析】

三层循环,第一层循环中间点k,第二、第三层循环起点终点i,j,算法的思想很容易理解:如果点i到点k的距离加上点k到点j的距离小于原先点i到点j的距离,那么就用这个更短的路径长度来更新原先点i到点j的距离。

在上图中,因为dis[1][3]+dis[3][2]<dis[1][2],所以就用dis[1][3]+dis[3][2]来更新原先1到2的距离。

我们初始化时,把不相连的点之间的距离设为一个很大的数,不妨看作这两点相隔很远,如果两者之间有最短路径的话,就会更新成最短路径的长度。


【算法边形】

    如果是一个没有边的权的图,把相怜的两点间的距离设为dis[i][j]=true,不相连的两点设为dis[i][j]=false,用Floyed算法变形:

for(k=1;k<=n;k++)
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			dis[i][j]=dis[i][j]||(dis[i][k] && dis[k][j])


       

用这个方法可以判断一张图中的两点是否相连。

注意:用来循环中间点的变量k必须放在最外层一层循环。

扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【算法】博弈论——取石子游戏

【题目描述】有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取...

【算法】高精度(2)

五、高精度处理进位与借位    其实也很简单,我们再来模拟一下,1439+887的时候,首先我们最低位相加,得到16,那么答案最低位就是6,再进个1,然后两数的十位相加,...

【算法】前缀和与差分(2)一 一维数组差分

【算法】前缀和与差分(2)一 一维数组差分

一、差分:一维数组的差分可看作是一维数组前缀和的逆运算。二、差分数组首先给定一个原数组a:   a[1]、a[2]、a[3]、......然后构造一个数组b: b[1]、b[2]、...

【贪心】----找零钱问题

一、找零钱问题例题1:有 1 元,5元,10元,20元,100元,200元的钞票无穷多张。现在使用这些钞票支付X元,最少需要多少张钞票。X = 628最佳支付方法:3张200块的,1张20块的,1张5...

【算法】单调栈

一、单调栈单调栈(Monotonic Stack)是一种特殊的栈结构,其核心思想是维护栈内元素的单调性(单调递增或单调递减)。单调栈通常用于解决与元素大小关系相关的问题,例如:找到数组中每个元素的下一...

【算法】二叉树(1):二叉树及其编号

【算法】二叉树(1):二叉树及其编号

0.前言        二叉树(Binary Tree)的递归定义如下:二叉树要么为空,要么由根结点(root)、左子树(left...