贪心算法求单元最短路径.docxVIP

#includestdio.h#includeiostream#includefstream#includestringusingnamespacestd;

constintN=5;constintM=1000;

ifstreamfin(4d5.txt);

templateclassType

voidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]);

voidTraceback(intv,inti,intprev[]);//输出最短途径v源点，i终点

intmain()

{

intv=1;//源点为1

intdist[N+1],prev[N+1],c[N+1][N+1];

cout有向图权的矩阵为：endl;for(inti=1;i=N;i++)

{

for(intj=1;j=N;j++)

{

finc[i][j];

coutc[i][j];

}

coutendl;

}

Dijkstra(N,v,dist,prev,c);

for(inti=2;i=N;i++)

{

cout源点1到点i的最短途径长度为:dist[i]，其途径为;Traceback(1,i,prev);

coutendl;

}

return0;

}

templateclassType

voidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1])

{

bools[N+1];

for(inti=1;i=n;i++)

{

dist[i]=c[v][i];//dist[i]表达目前从源到顶点i的最短特殊途径长度

s[i]=false;

if(dist[i]==M)

{

prev[i]=0;//统计从源到顶点i的最短途径i的前一种顶点

}

else

{

prev[i]=v;

}

}

dist[v]=0;s[v]=true;

for(inti=1;in;i++)

{

inttemp=M;

intu=v;//上一顶点

//取出V-S中含有最短特殊途径长度的顶点ufor(intj=1;j=n;j++)

{

if((!s[j])(dist[j]temp))

{

u=j;

temp=dist[j];

}

}

s[u]=true;

//根据作出的贪心选择更新Dist值for(intj=1;j=n;j++)

{

if((!s[j])(c[u][j]M))

{

Typenewdist=dist[u]+c[u][j];if(newdistdist[j])

{

dist[j]=newdist;prev[j]=u;

}

}

}

}

}

//输出最短途径v源点，i终点

voidTraceback(intv,inti,intprev[])

{

if(v==i)

{

couti;return;

}

Traceback(v,prev[i],prev);cout-i;

}

运行成果：