單源最短路徑的Dijkstra算法

-.z單源最短路徑的Dijkstra算法：問題描述：給定一個帶權有向圖G=〔V，E〕，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源。現(xiàn)在要計算從源到所有其他各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。算法描述：Dijkstra算法是解單源最短路徑的一個貪心算法。根本思想是：設置頂點集合S并不斷地做貪心選擇來擴大這個集合。一個頂點屬于S當且僅當從源到該頂點的最短路徑長度。初始時，S中僅含有源。設u是G的*一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist做必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。源代碼：#include<iostream>#defineMA*1000#defineLEN100intk=0,b[LEN];usingnamespacestd;//-------------------------------------數(shù)據(jù)聲明------------------------------------------------//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<<"迭代次數(shù)："<<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; //記錄前驅(qū)頂點 } }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<<"請輸入頂點個數(shù):"<<endl;cin>>n;cout<<"請輸入邊的個數(shù):"<<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