int i,j,k,m; //j记录dist的下标

m=start;

for(i=0;i<Num;i++) //初始化

{

dist[i]=Adj[m*Num+i];

prev[i]=m; //记录源点到顶点的最短路径上，本顶点的前一顶点

s[i]=0; //顶点i不在s域中

}

prev[m]=-1; //m是源点 前一顶点不存在

s[m]=1;//源点在s域中

for(i=0;i<Num-1;i++) //差Num-1个顶点需处理

{

int min; //最小权

for(k=0;k<Num;k++) if(!s[k])break; //找到仍在顶点V-S域中的第一个顶点

min=dist[k];

j=k;

for(k=j+1;k<Num;k++) //找最小权值的边

if(!s[k]&&dist[k]<min)

{

min=dist[k];

j=k;

}

s[j]=1; //放进s域中

for(k=0;k<Num;k++) //更新最短路径值

if(!s[k]&&dist[j]+Adj[j*Num+k]<dist[k])

{

dist[k]=dist[j]+Adj[j*Num+k]; //记录最短路径

prev[k]=j; //记录路径 即本顶点k的前驱顶点j }

}

ofstream output("output.txt",ios::out);

if(output==NULL)exit(0);

for(k=0;k<Num;k++) //输出打印

if(k!=m)

{

if(dist[k]>=MaxNum)

{

output<<"源点"<<start<<"到顶点"<<k<<"不存在相通的路径"<<endl<<endl;

}

else

{

output<<"源点"<<start<<"到顶点"<<k<<"的最小花费为:"<<dist[k]<<endl; //输

出最小权值

j=k;