單源最短路徑的Dijkstra算法

-.z單源最短路徑的Dijkstra算法：問題描述：給定一個(gè)帶權(quán)有向圖G=〔V，E〕，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其他各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。算法描述：Dijkstra算法是解單源最短路徑的一個(gè)貪心算法。根本思想是：設(shè)置頂點(diǎn)集合S并不斷地做貪心選擇來擴(kuò)大這個(gè)集合。一個(gè)頂點(diǎn)屬于S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長度。初始時(shí)，S中僅含有源。設(shè)u是G的*一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時(shí)對數(shù)組dist做必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長度。源代碼：#include<iostream>#defineMA*1000#defineLEN100intk=0,b[LEN];usingnamespacestd;//-------------------------------------數(shù)據(jù)聲明------------------------------------------------//c[i][j]表示邊(i,j)的權(quán)//dist[i]表示當(dāng)前從源到頂點(diǎn)i的最短特殊路徑長度//prev[i]記錄從源到頂點(diǎn)i的最短路徑上的i的前一個(gè)頂點(diǎn)//---------------------------------------------------------------------------------------------voidDijkstra(intn,intv,intdist[],intprev[],intc[][LEN]){bools[LEN]; //判斷是否已存入該點(diǎn)到S集合中for(inti=1;i<=n;i++) {dist[i]=c[v][i];s[i]=false; //初始都未用過該點(diǎn)if(dist[i]==MA*)prev[i]=0; //表示v到i前一頂點(diǎn)不存在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(luò)距離不在為無窮大 {u=j; //u保存當(dāng)前鄰接點(diǎn)中距離最小的點(diǎn)的temp=dist[j]; }s[u]=true;k++;b[k]=u;cout<<"----------------------------------------------------------"<<endl;cout<<"迭代次數(shù)："<<i<<endl;cout<<"頂點(diǎn)為：";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ū)頂點(diǎn) } }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<<"請輸入頂點(diǎn)個(gè)數(shù):"<<endl;cin>>n;cout<<"請輸入邊的個(gè)數(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<<"請輸入每條邊的權(quán)_格式為：ij權(quán)"<<endl;for(k=1;k<=m;k++) {cin>>i;cin>>j;cin>>c[i][j]; }Dij