单源最短路径的Dijkstra算法

-.z单源最短路径的Dijkstra算法：问题描述：给定一个带权有向图G=〔V，E〕，其中每条边的权是非负实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到所有其他各顶点的最短路长度。这里路的长度是指路上各边权之和。这个问题通常称为单源最短路径问题。算法描述：Dijkstra算法是解单源最短路径的一个贪心算法。根本思想是：设置顶点集合S并不断地做贪心选择来扩大这个集合。一个顶点属于S当且仅当从源到该顶点的最短路径长度。初始时，S中仅含有源。设u是G的*一个顶点，把从源到u且中间只经过S中顶点的路称为从源到u的特殊路径，并用数组dist记录当前每个顶点所对应的最短特殊路径长度。Dijkstra算法每次从V-S中取出具有最短特殊路长度的顶点u，将u添加到S中，同时对数组dist做必要的修改。一旦S包含了所有V中顶点，dist就记录了从源到所有其他顶点之间的最短路径长度。源代码：#include<iostream>#defineMA*1000#defineLEN100intk=0,b[LEN];usingnamespacestd;//-------------------------------------数据声明------------------------------------------------//c[i][j]表示边(i,j)的权//dist[i]表示当前从源到顶点i的最短特殊路径长度//prev[i]记录从源到顶点i的最短路径上的i的前一个顶点//---------------------------------------------------------------------------------------------voidDijkstra(intn,intv,intdist[],intprev[],intc[][LEN]){bools[LEN]; //判断是否已存入该点到S集合中for(inti=1;i<=n;i++) {dist[i]=c[v][i];s[i]=false; //初始都未用过该点if(dist[i]==MA*)prev[i]=0; //表示v到i前一顶点不存在elseprev[i]=v; }dist[v]=0;s[v]=true;for(inti=1;i<n;i++) {inttemp=MA*;intu=v; for(intj=1;j<=n;j++)if((!s[j])&&(dist[j]<temp))//j不在s中，v到j距离不在为无穷大 {u=j; //u保存当前邻接点中距离最小的点的temp=dist[j]; }s[u]=true;k++;b[k]=u;cout<<"----------------------------------------------------------"<<endl;cout<<"迭代次数："<<i<<endl;cout<<"顶点为：";cout<<v<<"\t";for(inti=1;i<=k;i++)cout<<b[i]<<"\t";cout<<endl;for(intj=1;j<=n;j++)if((!s[j])&&c[u][j]<MA*) {intnewdist=dist[u]+c[u][j];if(newdist<dist[j]) {dist[j]=newdist; //更新distprev[j]=u; //记录前驱顶点 } }cout<<"单源路径分别为："<<endl;for(inti=2;i<=n;i++)if(dist[i]!=MA*)cout<<dist[i]<<"";cout<<endl; }cout<<"----------------------------------------------------------"<<endl;// for(inti=1;i<=n;i++)// t[i]=prev[i];intp[LEN];for(inti=2;i<=n;i++) {cout<<"dist["<<i<<"]="<<dist[i]<<"";cout<<"路径为："<<v<<"\t";/*while(t[i]!=v) { cout<<t[i]<<"\t"; t[i]=prev[t[i]]; }*/intm=prev[i];intk=0;while(m!=v) {k++;p[k]=m;m=prev[m]; }for(int*=k;*>=1;*--)cout<<p[*]<<"\t";cout<<i;cout<<endl; }}intmain(){inti,j,k,m,n,v=1;intdist[LEN],prev[LEN],c[LEN][LEN];cout<<"请输入顶点个数:"<<endl;cin>>n;cout<<"请输入边的个数:"<<endl;cin>>m;for(i=1;i<=n;i++)for(j=1;j<=n;j++) {if(i==j)c[i][j]=0;elsec[i][j]=MA*; }cout<<"请输入每条边的权_格式为：ij权"<<endl;for(k=1;k<=m;k++) {cin>>i;cin>>j;cin>>c[i][j]; }Dij