最短路问题 Floyd+Dijkstra+SPFA

时间：2022-09-19 19:50:02

参考博客：https://blog.csdn.net/qq_35644234/article/details/60875818

题目来源：http://acm.hdu.edu.cn/showproblem.php?pid=2544

例题  hdu 2544

解法1.Dijkstra

复杂度为o(n*n)   n为点的个数

从1点开始贪心地寻找最佳距离

可以求出1号点到其它点的最短距离

核心：拿出某个点时，它得到了最短路径

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int maxn=105;

const int INF=1e9+10;

bool ins[maxn];

int ma[maxn][maxn];

int dis[maxn];

int n,m;

void dijkstra()

{

	memset(ins,0,sizeof(ins));

	for(int i=2;i<=n;i++)

		dis[i]=ma[1][i];

	dis[1]=0;

	ins[1]=1;

	while(1)

	{

		int minn=INF,index;

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

		{

			if(ins[i]==0&&dis[i]<minn)

			{

				minn=dis[i];index=i;

			}

		}

		if(minn==INF)break;

		ins[index]=1;

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

		{

			if(ins[i]==0&&ma[index][i]+dis[index]<dis[i])

				dis[i]=ma[index][i]+dis[index];

		}

	}

	printf("%d\n",dis[n]);

}

int main()

{

	while(scanf("%d %d",&n,&m)==2)

	{

		if(n==0&&m==0)break;

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

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

			ma[i][j]=INF;

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

		{

			int a,b,c;

			scanf("%d %d %d",&a,&b,&c);

			ma[a][b]=min(c,ma[a][b]);

			ma[b][a]=min(c,ma[b][a]);

		}

		dijkstra();

	}

	return 0;

}

　　

解法2.Floyd

复杂度o(n*n*n)

每次插入1个点，更新整个矩阵

可以求出两两之间的最短路径

#include<iostream>

#include<cstdio>

using namespace std;

const int INF=1e9+10;

const int maxn=105;

int ma[maxn][maxn];

int n,m;

void floyd()

{

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

	{

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

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

				ma[j][k]=min(ma[j][k],ma[j][i]+ma[i][k]);

	}

    printf("%d\n",ma[1][n]);

}

int main()

{

	while(scanf("%d %d",&n,&m)==2)

	{

		if(n==0&&m==0)break;

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

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

				ma[i][j]=INF;

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

		{

			int a,b,c;

			scanf("%d %d %d",&a,&b,&c);

			ma[a][b]=min(ma[a][b],c);

			ma[b][a]=min(ma[b][a],c);

		}

		floyd();

	}

	return 0;

}

　　

解法3.SPFA

复杂度o(n*v)  v为图中边的个数

贪心从1点寻找最短距离

优点是可以计算带有负边的图，缺点，复杂度高

核心：拿出某个点时，它不一定是最优，但可能会松弛其它点

注意：spfa函数中最好使用普通队列，优先队列反而更慢，因为根本是多此一举，每个弹出来的点不一定就是最短的了，所以它可能还是会进入队列

#include<iostream>

#include<cstdio>

#include<queue>

using namespace std;

const int maxn=110;

const int INF=1e9+10;

int ma[maxn][maxn],dis[maxn];

bool ins[maxn];

int n,m;

struct Node{

	int x;

	bool	operator < (const Node &a)const

	{

		return dis[x]<dis[a.x];

	}

	Node(int a)

	{

		x=a;

	}

};

void spfa()

{

	for(int i=1;i<=n;i++)ins[i]=0;

    queue<Node>que;

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

		dis[i]=INF;

	dis[1]=0;

	que.push(Node(1));

	while(que.size())

	{

		int x=que.front().x;

		que.pop();

		ins[x]=0;

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

		{

			if(dis[i]>dis[x]+ma[x][i])

			{

				dis[i]=dis[x]+ma[x][i];

				if(ins[i]==0)

				{

					ins[i]=1;

					que.push(Node(i));

				}

			}

		}

	}

	printf("%d\n",dis[n]);

}

int main()

{

	while(scanf("%d %d",&n,&m)==2)

	{

		if(n==0&&m==0)break;

		for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)ma[i][j]=INF;

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

		{

			int a,b,c;

			scanf("%d %d %d",&a,&b,&c);

			ma[a][b]=min(ma[a][b],c);

			ma[b][a]=min(ma[b][a],c);

		}

		spfa();

	}

	return 0;

}

　　

相关文章