dijkstra.txt

最短路经的求法

int value[MaxSize][MaxSize];
//下面算法中将不考虑路径的存储，只是求最短距离
int dijkstra(int n,int v)
{
	bool s[MaxSize];//判断是否在集合中
	int i,j;
	int dist[MaxSize];//存放v到各个点的最短距离
	for(i=1;i<=n;i++)
	{
		dist[i]=value[v][i];
		s[i]=false;
	}
	dist[v]=0;
	s[v]=true;

	for(i=1;i<=n;i++)
	{
		int temp=maxint;
		int u=v;
		for(j=1;j<=n;j++)
		{
			if((!s[j])&&(dist[j]<temp))
			{
				u=j;//记录v到点中最小的点
				temp=dist[j];
			}
		}//求出v点到各点的最短距离
		s[u]=true;
		//下面在u点的基础上更新v到各点的距离
		for(j=1;j<=n;j++)
			if((!s[j])&&(value[u][j]<maxint))//未被访问且要有路
			{
				int newdist=dist[u]+value[u][j];//当前v到j点的距离
				if(newdist<dist[j])
					dist[j]=newdist;
			}
	}
	return dist[1];//返回到n点的最短距离
}