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

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

3、(int n,int v,Type dist,int prev,Type cN+1)bool sN+1; /s數(shù)組表示各結點是否已經遍歷for(int i=1;i<=n;i+)disti=cvi;/disti表示當前從源到頂點i的最短路徑長度si=false;if(disti=M)previ=0;/記錄從源到頂點i的最短路徑的前一個頂點elseprevi=v;distv=0;sv=true;for(int i=1;i<n;i+)int temp=M;int u=v;/上一個頂點/取出v-s中具有最短路徑長度的頂點ufor(int j=1;j<=n;j+)if(!sj)&

4、;&(distj<temp)/如果distj比最小值temp小并且沒有在集合s中u=j;temp=distj;/更新最小值tempsu=true;/根據(jù)做出的貪心選擇更新dist的值for(int j=1;j<=n;j+)/當加入S集合后，更新dist的值if(!sj)&&(cuj<M)Type newdist=distu+cuj;if(newdist<distj)distj=newdist;prevj=u;測試結果輸入較小的有向帶權圖結果： 輸入較大的有向帶權圖結果： 實驗分析在實驗中輸入了兩個有向帶權圖，一組是結點較少，貪心判斷會少一點，另一

5、組的結點稍微多一點，貪心判斷會多一些，通過上面的圖和下面的結果的比較，我們可以發(fā)現(xiàn)結果是正確的，說明程序設計沒有問題。觀察兩個圖所用的時間的多少，我們發(fā)現(xiàn)這兩個結點所用的時間是相對接近的，并沒有很大的差距。不過這一個程序有一個問題就是每一次都需要我們手動的去輸入一個圖的鄰接矩陣，對于結點很多的圖顯然是不合適，所以我們可以通過讀文件來減少工作量，下次要改進。實驗心得Dijkstra算法在之前的數(shù)據(jù)結構中就學過，在當時只是學過這種思想，并沒有去深思這種思想其背后到底是一種怎樣的思想在里面。后來經過本門課的學習，對于貪心算法有了更深刻的了解，也知道了如何利用貪心算法去解決問題。最開心的是經過一定時間

6、的練習，我的編程能力有了一定的提高，之前看見就很頭疼的問題，現(xiàn)在也能靜下心來去思考，而且實現(xiàn)Dijkstra算法也可以通過一定程度的思考也能寫出來了，感覺還是很開心的。Dijkstra算法求單源最短路徑在很多地方都有應用，經過一次又一次的練習，終于能好好的掌握這一算法了，還是希望不要那么快忘記啊。實驗得分助教簽名附錄：完整代碼（貪心法）/貪心算法 Dijkstra求單源最短路徑#include<iostream>#include<string>#include<time.h>#include<iomanip>using namespace std

7、;const int N=10;const int M=1000; /定義無限大的值template<class Type>void Dijkstra(int n,int v,Type dist,int prev,Type cN+1);/輸出最短路徑，源點v，終點i，prev保存父結點void Traceback(int v,int i,int prev);/參數(shù)分別為頂點個數(shù)n，源結點v，源結點到其他結點的距離數(shù)組dist，父結點數(shù)組prev，各結點之間的距離數(shù)組cN+1template<class Type>void Dijkstra(int n,int v,Typ

8、e dist,int prev,Type cN+1)bool sN+1; /s數(shù)組表示各結點是否已經遍歷for(int i=1;i<=n;i+)disti=cvi; /disti表示當前從源到頂點的最短路徑長度si=false;if(disti=M)previ=0; /記錄從源到頂點i的最短路徑的前一個頂點elseprevi=v;distv=0;sv=true;for(int i=1;i<n;i+)int temp=M;int u=v; /上一個頂點/取出v-s中具有最短路徑長度的頂點ufor(int j=1;j<=n;j+)if(!sj)&&(distj&l

9、t;temp)/如果distj比最小值temp小并且j沒有在s集合中u=j;temp=distj; /更新最小值tempsu=true;/根據(jù)做出的貪心選擇更新dist的值for(int j=1;j<=n;j+) /當¡加入S集合后，更新dist的值if(!sj)&&(cuj<M)Type newdist=distu+cuj;if(newdist<distj)distj=newdist;prevj=u;/輸出最短路徑，v源點，i終點，prev為父結點數(shù)組void Traceback(int v,int i,int prev)if(v=i)cout&l

10、t;<i;return;Traceback(v,previ,prev); /回溯輸出最短路徑cout<<"->"<<i;int main()int i,j;int v=1; /源點為1int distN+1,prevN+1,cN+1N+1;cout<<"有向圖權的矩陣為："<<endl;for(i=1;i<=N;i+) /輸入鄰接矩陣for(j=1;j<=N;j+)cin>>cij;clock_t start,end,over; /計算程序運行時間的算法start=clock();end=clock();over=end-start;start=clock(); Dijkstra(N,v,dist,prev,c); /調用dijkstra算法函數(shù)for(i=2;i<=N;i+)cout<<"源點1到點"<<i<<"的最短路徑長度為："<<disti<<"，其路徑為：" /輸出最短路徑長度Traceback