[置顶] 数据结构之 迪杰斯特拉最短路径算法

void printfPath(int path[],int a)
{
	int statck[maxSize],top=-1;
	while(path[a]!=-1)
	{
		statck[++top]=a;
		a=path[a];
	}
	statck[++top]=a;
	while(top!=-1)
	{
		cout<<statck[top--]<<" ";
	}
	cout<<endl;
}

//迪杰斯特拉 最短路径算法
void dijKstra(MGraph g,int v,int dist[],int path[])
{
	int set[maxSize];
	int min,i,j,u;
	for(i=1;i<=g.n;i++)
	{
		dist[i]=g.edges[v][i];
		set[0]=0;
		if(g.edges[v][i]<INFINITY)
			path[i]=v;
		else
			path[i]=-1;
	}
	set[v]=1;
	path[v]=-1;
	for(i=1;i<=g.n;i++)
	{
		min=INFINITY;
		for(j=1;j<=g.n;j++)
		{
			if(set[j]==0&&dist[j]<min)
			{
				u=j;
				min=dist[j];
			}
		}
		set[u]=1;
		for(j=1;j<=g.n;j++)
		{
			if(set[j]==0&&dist[u]+g.edges[u][j]<dist[j])
			{
				dist[j]=dist[u]+g.edges[u][j];
				path[j]=u;
			}
		}
	}
}