DIJKSTRA算法的C语言实现

#includestdafx.h#includestdio.h#includestdlib.h#defineN6#defineMAX9999voidPath(int*p,intv,inti){intque[N];intt=v;que[t++]=i;inttmp=p[i];while(tmp!=v){que[t]=tmp;t++;tmp=p[tmp];}que[t]=v;for(intk=t;k=1;--k)if(k!=1)printf(%d--,que[k]);else{printf(%d,que[k]);printf(\n);}}intmain(){intcost[N][N]={{MAX,MAX,MAX,MAX,MAX,MAX},{MAX,MAX,10,MAX,30,100},{MAX,MAX,MAX,50,MAX,MAX},{MAX,MAX,MAX,MAX,MAX,10},{MAX,MAX,MAX,20,MAX,60},{MAX,MAX,MAX,MAX,MAX,MAX}};intS[N];intdist[N];intp[N];inti,j,u,min;for(i=1;iN;i++){S[i]=0;dist[i]=cost[1][i];if(dist[i]==MAX)p[i]=0;elsep[i]=1;}S[1]=1;for(i=2;iN;i++){min=MAX;for(j=1;jN;j++){if(!S[j]&&dist[j]min){u=j;min=dist[j];}}S[u]=1;for(j=1;jN;j++)if(!S[j]&&min+cost[u][j]dist[j]){dist[j]=min+cost[u][j];p[j]=u;}}for(i=2;iN;i++){printf(theshortestline1---%d:%d,i,dist[i]);printf(顶点遍历:);Path(p,1,i);}system(pause);}