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

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

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

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

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

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<<"請輸入起點(diǎn)終點(diǎn)權(quán)值(-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];//從源點(diǎn)到各點(diǎn)的值s[i]=false;if(dist[i]==MAX)prev[i]=0;//最大值沒有路徑elseprev[i]=v;//前驅(qū)為源點(diǎn)}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]];//構(gòu)造路徑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<<"請輸入所求單源路徑的起點(diǎn)終點(diǎn)：

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