POJ1125-Dijkstra算法

人生难得糊涂

浏览: 117384 次

最近访客更多访客>>

anlinko

jw216

zjy_369

zt1102

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

题意：

给出若干个联系人，及每个联系人通知其他联系人所需的时间，求从哪个联系人开始通知所用时间最短，并求出最短时间。

很明显是图论中求最短路径问题，可以用floyd 算法或者Dijkstra算法。我这里分别用两种方法实现。

方法一：Dijkstra算法。

只要遍历每个人，对每个人都以他为起点调用Dijkstra算法，求出最长时间（注意这道题一个联系人可以同时通知多个联系人，所以求出他通知他人的最大时间，则是他通知所以人所用时间）。然后在每个人的“最长时间中”求出最短的那个。即答案。

#include "iostream"
using namespace std;
#define len 110
#define MAXINT 9999999
int map[len][len];
int length[len];//记录v到length[k]的最短路径
int flag[len];//标记某点是否得到最短路径（即处理完毕）
int dis(int v,int num)//此方法即Dijkstra算法
{
	int i;
	int j;
	for ( i=1;i<=num;i++)
	{
		length[i]=map[v][i];//初始化第一组数据
		flag[i]=0;
	}
	length[v]=0;
	flag[v]=1;
	for (i=1;i<num;i++)
	{
		int min=MAXINT;
		int minindex=-1;
		for (j=1;j<=num;j++)//找到本次搜索中距离最小的那个
		{
			if (flag[j]==0&&j!=v)
			if (length[j]<min)
			{
				min=length[j];
				minindex=j;
			}
		}
		if (minindex!=-1)
		{
			flag[minindex]=1;//将本次搜索中最小的那个加入以已处理集合（即已经找到最短路径）
			for (j=1;j<=num;j++)
			{
				if (flag[j]==0)//更新未处理的点
				{
					if (length[j]>length[minindex]+map[minindex][j])
					{
						length[j]=length[minindex]+map[minindex][j];
					}
				}
		}
		}
		
	}
	int max=-1;
	for (i=1;i<=num;i++)
	{
		if (max<length[i])
		{
			max=length[i];
		}
	}
	return max;//返回最大的一条边
}
int main()
{
	int num;
	int i,j;
	while(true)
	{
		scanf("%d",&num);//num表示有几个人
		if (num==0)
		{
			break;
		}
		
		for (i=1;i<=num;i++)
		{
			int n;
			scanf("%d",&n);
			for (j=1;j<=num;j++)
			{
				map[i][j]=MAXINT;//这里不能用memset方法，memset方法只能初始化为0 ，1，-1
			}
			for (j=1;j<=n;j++)
			{
				int  t;
				scanf("%d",&t);
				scanf("%d",&map[i][t]);
			}
		}

		int min=MAXINT;//记录最短的时间
		int mini=1;//记录从哪个联系人开始
		for (i=1;i<=num;i++)//对每个联系人遍历
		{
			if (min>dis(i,num))
			{
				min=dis(i,num);
				mini=i;
			}
		}
		if (min>100)
		{
			printf("disjoint\n");
		}
		else
		{
			printf("%d %d\n",mini,min);
		}
		
	}
	return 0;
}

方法二：floyd算法

floyd算法是用来求图中的两点到两点之间的最短距离.。

其状态转移方程为： dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);dp[i][j]为点i到点j的最短路径，k为中间点.

于是我们可以很简单写出floyd的代码

for (i=1;i<=num;i++)
{
	for (j=1;j<=num;j++)
	{
		for (int k=1;k<=num;k++)
		{
			if (dp[i][j]>dp[i][k]+dp[k][j])
			{
				dp[i][j]=dp[i][k]+dp[k][j];
			}
					
		}
	}
}

那么上述代码有没有问题呢？

下面内容为转载 http://www.cnblogs.com/twjcnblog/archive/2011/09/07/2170306.html

有修改

把检查所有节点X放在最内层，那么结果将是不正确的，为什么呢？因为这样便过早的把i到j的最短路径确定下来了，而当后面存在更短的路径时，已经不再会更新了。

图中红色的数字代表边的权重。如果我们在最内层检查所有节点X，那么对于 A->B，我们只能发现一条路径，就是A->B，路径距离为9。而这显然是不正确的，真实的最短路径是 A->D->C->B，路径距离为6。造成错误的原因就是我们把检查所有节点X放在最内层，造成过早的把A到B的最短路径确定下来了，当确定A->B的最短路径时Dis(AC)尚未被计算。所以，我们需要改写循环顺序，如下：

for (int k=1;k<=num;k++)
{
	for (i=1;i<=num;i++)
	{
		for (j=1;j<=num;j++)
		{			
			if (dp[i][j]>dp[i][k]+dp[k][j])
			{
				dp[i][j]=dp[i][k]+dp[k][j];
			}			
		}
	}
}

那么完整的代码如下：

#include "iostream"
using namespace std;
#define len 110
#define MAXINT 9999999
int map[len][len];
int dp[len][len];
int main()
{
	int num;
	int i,j;
	while(true)
	{
		scanf("%d",&num);//num表示有几个人
		if (num==0)
		{
			break;
		}
		
		for (i=1;i<=num;i++)
		{
			int n;
			scanf("%d",&n);
			for (j=1;j<=num;j++)
			{
				map[i][j]=MAXINT;//这里不能用memset方法，memset方法只能初始化为0 ，1，-1
			}
			for (j=1;j<=n;j++)
			{
				int  t;
				scanf("%d",&t);
				scanf("%d",&map[i][t]);
			}
		}
		for (i=1;i<=num;i++)
		{
			for (j=1;j<=num;j++)
			{
				dp[i][j]=map[i][j];
			}
		}
		for (int k=1;k<=num;k++)
		{
			for (i=1;i<=num;i++)
			{
				for (j=1;j<=num;j++)
				{
					if (dp[i][j]>dp[i][k]+dp[k][j])
					{
						dp[i][j]=dp[i][k]+dp[k][j];
					}
					
				}
			}
		}
		
		int max[len];
		memset(max,-1,sizeof(max));
		int ans=MAXINT;
		int ansi;
		for (i=1;i<=num;i++)//找以i为起点，最大的路径
		{
			for (j=1;j<=num;j++)
			{
				if (i!=j)
					if (max[i]<dp[i][j])
					{
						max[i]=dp[i][j];
					}
			}
			if (ans>max[i])//再每个点的最大路径中找到最小的那个
			{
				ansi=i;
				ans=max[i];
			}
		}
		if (ans==MAXINT)//说明有孤立点
			printf("disjoint\n");	
		else
			printf("%d %d\n",ansi,ans);
		
	}
	return 0;
}