算法之Floyd-Warshall算法【c++】【图论】【最短路】

我们作为刚学图论的小蒟蒻，先接触到的算法一定是图上最短路径算法。而最短路算法中最简单的当属Floyd-Warshall算法。下面是一些基本介绍：

该算法可以计算图上任意两点间的最短路径

时间复杂度：O(n^3)

适用情况：适用出现负边权的情况

算法伪代码：

弗洛伊德算法的基本思想是动态规划，我们枚举每一个点，并以其为中间节点更新任意两点间的最小距离，伪代码：

#define maxn 最大节点数

#define inf 0x7fffffff-2

long long val[maxn][maxn];

long long dis[maxn][maxn];

inline void floyd(){

    for(int i=1;i<=maxn;i++)

    	for(int j=1;j<=maxn;j++)

    		if(val[i][j])

    			dis[i][j]=val[i][j];

			else

				dis[i][j]=inf;

	for(int k=1;k<=maxn;k++)

		for(int i=1;i<=maxn;i++)

			for(int j=1;j<=maxn;j++)

				if(dis[i][j]>dis[i][k]+dis[k][j])

					dis[i][j]=dis[i][k]+dis[k][j];

}

此时，dis[i][j]就是从i节点到j节点的最短路径。

算法分析&&思路讲解

初始化：我们在初始化时，将有边相连的节点间distance更新为边权值，无边相连直接设为极大值。
动态规划：对于每个节点，我们都让它做一次中间节点（k），然后分别枚举另外两个节点（i，j），如果当前从i到j的最短路大于从i到k的最短路加上从j到k的最短路，即从i到j如果经过k点会路径更短，那么我们更新从i到j的最短路。
算法结束，我们得到了所有的最短路。

需要强调的一点是，floyd中k的循环必须写在最外层，否则会导致动态规划状态转移发生错误！

例题讲解：Luogu P2935

传送门

不难发现，题目是让我们求所有牧场到喜欢的牧场的最短路，这就是所谓的多源最短路问题。对于这道题思路如下：

用floyd求出所有最短路。
枚举每个点，求出最小平均距离。

该题数据较小，这种思路完全可以通过。

代码：

#include<bits/stdc++.h>

using namespace std;

#define inf 0x3fffffff

int n,m,f,u,v,t;

int square[501][501];

long long dis[501][501];

int like[501];

int main(){

	scanf("%d %d %d",&n,&f,&m);

	for(int i=1;i<=n;i++){

		for(int j=1;j<=n;j++){

			dis[i][j]=inf;

		}

		dis[i][i]=0;

	}//预处理。

	for(int i=1;i<=f;i++){

		scanf("%d",&like[i]);

	}//输入每个喜欢的牧场

	for(int i=1;i<=m;i++){

		scanf("%d %d %d",&u,&v,&t);

		dis[u][v]=t;

		dis[v][u]=t;

	}//输入牧场距离并预处理

	for(int k=1;k<=n;k++){

		for(int i=1;i<=n;i++){

			for(int j=1;j<=n;j++){

				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);//裸的floyd板子

			}

		}

	}

	int ans,maxx=inf,sum=0;

	for(int i=1;i<=n;i++){

		sum=0;

		for(int j=1;j<=f;j++){

			sum+=dis[i][like[j]];//统计从该节点到所有喜欢的牧场的总最短距离

		}

		if(sum<maxx){

			ans=i;

			maxx=sum;

		}

        //这里注意一下，题目说让我们求的是平均距离最小，但其实喜欢的牧场个数固定，我们就只需要求总最短路径最小就行了，不用再取平均值。

	}

	cout<<ans;//输出牧场序号

	return 0;

}

拓展延伸：算法变形

floyd算法在一些情况下可以变形，用途是判断图上任意两点间连通性。

伪代码：

#define maxn 最大节点数

bool val[maxn][maxn];

bool dis[maxn][maxn];

inline void floyd(){

    for(int i=1;i<=maxn;i++)

    	for(int j=1;j<=maxn;j++)

    		if(val[i][j])

    			dis[i][j]=1;//相邻两点间距离设为ture

			else

				dis[i][j]=0;//不相邻设为false

	for(int k=1;k<=maxn;k++)

		for(int i=1;i<=maxn;i++)

			for(int j=1;j<=maxn;j++)

				dis[i][j]=dis[i][j]||(dis[i][k]&&dis[k][j]);

                //原理：若i与k联通，k与j联通，则i与j联通

}

完结撒花

巴特西

算法之Floyd-Warshall算法【c++】【图论】【最短路】

算法伪代码：

算法分析&&思路讲解

例题讲解：Luogu P2935

拓展延伸：算法变形

最新文章

热门文章