cpp1.cpp

用普里姆算法借助堆排序实现最短路径的查找

#include "stdio.h"
#define max 50
#define maxism 99999
#include "string.h"
void main( )
{
 int vertexnum,edgnum;
 int GE[max][max],lowcost[max],teend[max];
 int x,y,num,mincost;
 int v,k,j,i,sum=0,t;
 char result[100],temp[20],*str;
 for( i=0;i<100;i++)
	 result[i]=0;
     str=result;
printf("mts\n");
scanf(" %d %d",&vertexnum,&edgnum);
 for (i=1;i<=vertexnum;i++)//初始化
	 for (int j=1;j<=vertexnum;j++)
		 GE[i][j]=maxism;
	 lowcost[1]=0;
     teend[1]=1;
for(i=0;i<edgnum;i++)//读入邻接表
{
    scanf(" %d %d %d",&x,&y,&num);
	GE[x][y]=num;
	GE[y][x]=num;
}
for(i=2;i<=vertexnum;i++)//初始化辅助数组
{
	teend[i]=1;
	lowcost[i]=GE[1][i];
}
for (i=1;i<vertexnum;i++)
{
    mincost=maxism;
  	v=2;//用v找完所有的点
	while(v<=vertexnum)
	{     
		if((mincost>lowcost[v]) && (lowcost[v]!=0))
			{mincost=lowcost[v];k=v;}
        v=v+1;
	}
         x=teend[k];
        if(x>k)
		   sprintf(temp,"%d %d %d \n",k ,x, GE[x][k]);
		else
           sprintf(temp,"%d %d %d \n",x,k, GE[x][k]);
		str=strcat(str,temp);
	   sum+=GE[x][k];
		lowcost[k]=0;
	   for(j=1;j<=vertexnum;j++)//更新lowcost[v]
		  if(GE[k][j]<lowcost[j])
		  {
			lowcost[j]=GE[k][j];
			teend[j]=k;
		  }

}
  printf("Cost:%d\n%s",sum,result); 
}