貪心算法實驗(求解最短路徑).doc

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

1、算法分析與設(shè)計實驗報告第五次實驗姓名學(xué)號班級時間12.12上午地點工訓(xùn)樓309實驗名稱貪心算法實驗(求解最短路徑)實驗?zāi)康耐ㄟ^上機(jī)實驗，要求掌握貪心算法的思想，利用Dijkstra算法求解最短路徑并實現(xiàn)。實驗原理設(shè)置頂點集合S并不斷地作貪心選擇來擴(kuò)充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中

2、，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其他頂點之間的最短路徑長度。實驗步驟（1）用鄰接矩陣表示有向圖，并進(jìn)行初始化，同時選擇源點；（2）選取候選集中距離最短的頂點，把其加入終點集合中；（3）以該頂點為新考慮的中間頂點，修改候選集中個頂點距離，若經(jīng)過該點后，各點到達(dá)源點距離比原來距離短，則修改距離；（4）重復(fù)以上2、3步，直到所有候選集中都被加入到終點集中。關(guān)鍵代碼template//參數(shù)分別為頂點個數(shù)n，源結(jié)點v，源結(jié)點到其他結(jié)點的距離數(shù)組dist[]，父結(jié)點數(shù)組prev[]，各結(jié)點

3、之間的距離數(shù)組c[][N+1]voidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]){bools[N+1];//s數(shù)組表示各結(jié)點是否已經(jīng)遍歷for(inti=1;i<=n;i++){dist[i]=c[v][i];//dist[i]表示當(dāng)前從源到頂點i的最短路徑長度s[i]=false;if(dist[i]==M)prev[i]=0;//記錄從源到頂點i的最短路徑的前一個頂點elseprev[i]=v;}dist[v]=0;s[v]=true;for(inti=1;i

4、mp=M;intu=v;//上一個頂點//取出v-s中具有最短路徑長度的頂點ufor(intj=1;j<=n;j++){if((!s[j])&&(dist[j]

5、t

6、工作量，下次要改進(jìn)。實驗心得Dijkstra算法在之前的數(shù)據(jù)結(jié)構(gòu)中就學(xué)過，在當(dāng)時只是學(xué)過這種思想，并沒有去深思這種思想其背后到底是一種怎樣的思想在里面。后來經(jīng)過本門課的學(xué)習(xí)，對于貪心算法有了更深刻的了解，也知道了如何利用貪心算法去解決問題。最開心的是經(jīng)過一定時間的練習(xí)，我的編程能力有了一定的提高，之前看見就很頭疼的問題，現(xiàn)在也能靜下心來去思考，而且實現(xiàn)Dijkstra算法也可以通過一定程度的思考也能寫出來了，感覺還是很開心的。Dijkstra算法求單源最短路徑在很多地方都有應(yīng)用，經(jīng)過一次又一次的練習(xí)，終于能好好的掌握這一算法了，還是希望不要那么快忘記啊

7、。實驗得分助教簽名附錄：完整代碼（貪心法）//貪心算法Dijkstra求單源最短路徑#include#include#include#includeusingnamespacestd;constintN=10;constintM=1000;//定義無限大的值templatevoidDijkstra(intn,intv,Typedist[],intprev[],Typec[][N+1]);//輸出最短路徑，源點v，終點i，prev[]保存父結(jié)點voidTraceb

8、ack(intv,inti,intprev[]);//參數(shù)分別為頂點個數(shù)n，源結(jié)點v，源結(jié)點到