單源最短路徑 貪心算法.doc

《單源最短路徑 貪心算法.doc》由會員上傳分享，免費在線閱讀，更多相關內容在行業(yè)資料-天天文庫。

1、實驗三單源最短路徑一、實驗目的及要求?掌握貪心算法的基本思想?用c程序實現(xiàn)單源最短路徑的算法?二、實驗環(huán)境?Window下的vc?2010三、實驗內容?1、有向圖與單源點最短路徑?2、按路徑長度非降的次序依次求各節(jié)點到源點的最?短路徑?3、Dijkstra算法四、算法描述及實驗步驟???設給定源點為Vs，S為已求得最短路徑的終點集，開始時令S={Vs}?。當求得第一條最短路徑(Vs?，Vi)后，S為{Vs，Vi}?。根據(jù)以下結論可求下一條最短路徑。?設下一條最短路徑終點為Vj?，則Vj只有：源點到終點有直接的弧?；從Vs?出發(fā)到Vj?的這條最短路徑所經過的所有中間頂點必定在S中。

2、即只有這條最短路徑的最后一條弧才是從S內某個頂點連接到S外的頂點Vj?。???若定義一個數(shù)組dist[n]，其每個dist[i]分量保存從Vs?出發(fā)中間只經過集合S中的頂點而到達Vi的所有路徑中長度最小的路徑長度值，則下一條最短路徑的終點Vj必定是不在S中且值最小的頂點，?即：dist[i]=Min{?dist[k]

3、?Vk∈V-S?}?利用公式就可以依次找出下一條最短路徑。?在程序中c[][]表示帶權鄰接矩陣?，??dist[]表示頂點到源點的最短路徑?，??p[]記錄頂點到源點最短路徑的前驅節(jié)點?，??u源點，函數(shù)Way是遞歸的構造出最短路徑的次序。??五、實驗結果?程序執(zhí)行的結果：六、源

4、代碼#include#includeusingnamespacestd;#defineMAX999voidgetdata(int**c,intn){inti,j;intbegin,end,weight;for(i=1;i<=n;i++){for(j=1;j<=n;j++){if(i==j)c[i][j]=0;elsec[i][j]=MAX;}}do{cout<<"請輸入起點終點權值(-1退出)：";cin>>begin;if(begin==-1)break;cin>>end>>weight;c[begin][end]=weight;}while(begi

5、n!=-1);}voidDijkstra(intn,intv,int*dist,int*prev,int**c){bools[MAX];inti,j;for(i=1;i<=n;i++){dist[i]=c[v][i];//從源點到各點的值s[i]=false;if(dist[i]==MAX)prev[i]=0;//最大值沒有路徑elseprev[i]=v;//前驅為源點}dist[v]=0;s[v]=true;for(i=1;i<=n;i++){inttemp=MAX;intu=v;for(j=1;j<=n;j++)if((!s[j])&&(dist[j]

6、st[j];}//不在集合里，值《temp，選最小值s[u]=true;for(j=1;j<=n;j++){if((!s[j])&&(c[u][j]1;i--){path[i]=pre

7、v[path[i+1]];//構造路徑m--;}for(i=m;i<=end;i++){cout<";//輸出路徑}cout<<"bb"<<""<>n;int*dist=newint[n+1];int*prev=newint[n+1];int**c;c=newint*[n+1];for(i=0;i<=n;i++){c[i]=newint[n+1];}getdata(c,n);//獲取數(shù)據(jù)intbegin=1,end;cout<<"請輸入所求單源路徑的起點終點：

8、";cin>>begin>>end;v=begin;Dijkstra(n,v,dist,prev,c);//計算路徑PrintPath(prev,n,begin,end);//輸出路徑system("pause");}