dijkstra.c

来自「数据结构--c语言」· C语言 代码 · 共 41 行

void dijkstra(mgraph *g,int v1,int n)
{
	int d2[mvnum],p2[mvnum];
	int v,i,w,min;
	enum boolean s[mvnum];
	for(v=1;v<=n;v++){
		s[v]=FALSE;
		d2[v]=g->arcs[v1][v];
		if(d2[v]<maxint)
			p2[v]=v1;
		else
			p2[v]=0;
	}
	d2[v1]=0;s[v1]=TURE;
	for(i=2;i<n;i++){
		min=maxint;
		for(w=1;w<=n;w++)
			if(!s[w] && d2[w]<min)
			{
				v=w;min=d2[w];
			}
			s[v]=TRUE;
			for(w=1;w<=n;w++)
				if(!s[w] &&(d2[v]+g->arcs[v][w]<d2[w]))
				{
					d2[w]=d2[v]+g->arcs[v][w];
					p2[w]=v;
				}
				}
	printf("路径长度     路径\n");
	for(i=1;i<=n;i++){
		printf("%5d",d2[i]);
		printf("%5d",i);v=p2[i];
		while(v!=0){
			printf("<-%d",v);
			v=p2[v];
		}
		printf("\n");
	}
}