ldijkstra.h

来自「《数据结构-使用C语言》第三版」· C头文件 代码 · 共 46 行

//邻接表存储结构
void DijkstraL(AdjLGraph G, int v0, int distance[], int path[])
{
	int n=G.numOfVerts;
	int *s=(int *)malloc(sizeof(int)*n);
	int minDis, i, j, u;
	int d;
	
	for(i=0;i<n;i++)
	{
		d = GetDistance(G, v0, i);
		if(d==-1)distance[i] = MaxWeight;
		else distance[i] = d;
		s[i] = 0;
		if(i!=v0 && distance[i]<MaxWeight) path[i]=v0;
		else path[i] = -1;
	}
	
	s[v0]=1;
	
	for(i=1;i<n;i++)
	{
		minDis = MaxWeight;
		for(j=0;j<n;j++)
			if(s[j]==0 && distance[j] < minDis)
			{
				u = j;
				minDis = distance[j];
			}
			
		if(minDis==MaxWeight) return ;
		
		s[u]=1;
		for(j=0;j<n;j++)
		{
			d = GetDistance(G, u, j);
			if(d==-1)d=MaxWeight;
			if(s[j]==0 && d < MaxWeight && distance[u]+d < distance[j])
			{
				distance[j] = distance[u] + d;
				path[j] = u;
			}
		}
	}
}