單源最短路徑(貪心法)實驗報告.docx

《單源最短路徑(貪心法)實驗報告.docx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、算法分析與設(shè)計實驗報告第5次實驗姓名學(xué)號班級時間12.12下午地點四合院實驗名稱貪心法求最短路徑實驗?zāi)康耐ㄟ^上機實驗，掌握貪心算法的思想，利用Dijkstra算法求解最短路徑并實現(xiàn)。實驗原理使用貪心法求出給定圖各點的最短路徑，并計算算法的執(zhí)行時間，分析算法的有效性。已知一個有向網(wǎng)絡(luò)G=(V,E)和源點V1，如上所示，求出從源點出發(fā)到圖中其余頂點的最短路徑。實驗步驟1用鄰接矩陣表示有向圖，并進行初始化，同時選擇源點；2選取候選集中距離最短的頂點，把其加入終點集合中；3以該頂點為新考慮的中間頂點，修改候選集中各頂點距離，若經(jīng)過該點后，各點到達源點距離比原來距離短，則修改距離；4重復(fù)以上2、

2、3步，直到所有候選集點都被加入到終點集中。關(guān)鍵代碼voidDijkstra(intn,intv,intdist[],intprev[]){bools[maxint];for(inti=1;i<=n;i++){dist[i]=c[v][i];s[i]=false;if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;}//找到第一個可行源點s[]標(biāo)志，記錄prev[]前一個點dist[v]=0;s[v]=true;for(inti=1;i

3、)&&(dist[j]

4、在取隨機數(shù)組成的權(quán)值時有點小麻煩，由于剛開始時只考慮到某些頂點不聯(lián)通，要把部分隨機數(shù)取成較大的無效值，后又發(fā)現(xiàn)沒有考慮到圖的雙向問題，分別給兩個方向都取了隨機值，于是結(jié)果出現(xiàn)差錯，于是增加了一個判斷條件使圖成為一個單向圖，通過手動輸入起點的方式實現(xiàn)最短路徑搜索。通過這次實驗，不僅掌握了貪心算法，還掌握了隨機產(chǎn)生一個圖并計算其最短路徑的算法，讓我覺得收獲頗大。實驗得分助教簽名附錄：完整代碼#include#include#include#definemaxint1000intc[200][200]={0};voidDijkstra(i

5、ntn,intv,intdist[],intprev[]){bools[maxint];for(inti=1;i<=n;i++){dist[i]=c[v][i];s[i]=false;if(dist[i]==maxint)prev[i]=0;elseprev[i]=v;}//找到第一個可行源點s[]標(biāo)志，記錄prev[]前一個點dist[v]=0;s[v]=true;for(inti=1;i

6、[u]=true;for(intj=1;j<=n;j++){intnewdist=dist[u]+c[u][j];if(newdist

7、

8、(c[j][

9、i]==1000))c[i][j]=rand()%100+1;elsec[i][j]=1000;if(c[i][j]>50)c[i][j]=1000;}}}printf("請輸入源點：");scanf("%d",&v);intdist[n+1],prev[n+1];printf("路徑：");for(inti=1;i