shortest.h

各种排序方法源码

//-----------------------------------求最短路径-----------------------------------//
void shortestpath(ALGraph *G,char *sou,char *dest)
{//得到从sou始的所有顶点的最短路径
	int i,v=-1,w,k,j;
	int **p,*final;
	unsigned int  *d;
	unsigned int min;
	int de;
	p=(int **)malloc(G->vexnum*sizeof(int*));  //开辟空间
	for(i=0;i<G->vexnum;++i)
	{
		p[i]=(int *)malloc(G->vexnum*sizeof(int));
	}
	final=(int *)malloc(G->vexnum*sizeof(int));
	d=(unsigned int *)malloc(G->vexnum*sizeof(unsigned int));
	i=locatevex(G,sou);   //起点下标
	de=locatevex(G,dest);  //终点下标
	for(v=0;v<G->vexnum;++v)  //初始化
	{
		final[v]=FALSE;
		d[v]=G->arc[i][v];
		for(w=0;w<G->vexnum;++w)
		{
			p[v][w]=FALSE; //设空路径
		}
		if(d[v]<Maxint){p[v][i]=TRUE;p[v][v]=TRUE;}
		
	}
	
	d[i]=0; //初始化
	final[i]=TRUE;
	//开始主循环，每次求得从i到某个顶点v的最短路径
	for(k=1;k<G->vexnum;++k)
	{
		v=-1;
		min=Maxint;
		for(w=0;w<G->vexnum;++w)
			if(!final[w])
				if(d[w]<min)
				{v=w;min=d[w];}  //w离起点更近
				final[v]=TRUE;
				if(v==-1)continue;//与已经访问的顶点间无路径
				else //有路径,更新
				{
					for(w=0;w<G->vexnum;++w) //更新当前最短路径及最近距离
					{
						if(!final[w]&&((min+G->arc[v][w])<d[w]))
						{
							d[w]=min+G->arc[v][w];
							for(j=0;j<G->vexnum;++j)
							{
								p[w][j]=p[v][j];
								p[w][w]=TRUE;
							}
						}
					}
				}
				if(final[de]==TRUE)break;//已经求得最短路径
	}
	printf("最短路径为:\n");
	printpath(G,i,de,p,d); //输出路径
}