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

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

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

2、2、3步，直到所有候選集點都被加入到終點集中。關(guān)鍵代碼voidDijkstra(intn,intv,intdist[J,intprev[J){bools[maxint];for(inti=l;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=l;i〈n;i++){inttemp=maxint;intu二v;for(intj=l;j<=n;j++){if((!s[j]

3、)&&(dist[j]〈temp)){U=j;temp二dist[j];}}s[u]=true;for(intj=l;j<=n;j++){intnewdist二dist[u]+c[u][j];if(nowdist

4、100061000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010001000100010000100031000100010001000010007100008100010001000測試結(jié)果請輸入源點:11到1的最短路徑為：1到2的最短路徑為:1到3的最短路徑為：1到4的最短路徑為:1到5的最短路徑為:1到6的最短路徑為:1到7的最短路徑為:1到8的最短路徑

5、為:1到9的最短路徑為:0425791211151到10的最短路徑為:15隨機數(shù)產(chǎn)卞圖的權(quán)值:請輸人頂點數(shù):5請輸入潦點:1路徑=0421000351100001000251000100010000100061000100046010001000281000100001到1的最短路徑為：01到2的最短路徑為：291到3的最短路徑為：811到4的最短路徑為：351到5的最短路徑為：1請輸入頂點數(shù):6請輸入漏點:2tea：0100010003610001000400291000491000100010000231215100025100003410001000100010001000010

6、00271000100010003302到1的最短路徑為：402到2的最廻路徑為：02到3的最短路徑為：292到4的最短路徑為：522到5的最短路徑為:412到6的最短路徑為：44通過這次實驗，我回顧了回溯法求解最短路徑問題，在其中加入了舍伍德隨機化取值過程，使數(shù)據(jù)分布更加均勻，讓我熟悉了隨機化算法，也讓結(jié)果更加公平可靠。實驗心得本次實驗在書本有詳細(xì)的算法，很容易實現(xiàn)了上血的圖形，但是為了改進算法，實現(xiàn)取隨機數(shù)組成一個圖，在取隨機數(shù)組成的權(quán)值時冇點小麻煩，由于剛開始時只考慮到某些頂點不聯(lián)通，要把部分隨機數(shù)取成較人的無效值，示又發(fā)現(xiàn)沒有考慮到圖的雙向問題，分別給兩個方向都取了隨機值，于是

7、結(jié)來出現(xiàn)差錯，于是增加了一個判斷條件使圖成為一個單向圖，通過手動輸入起點的方式實現(xiàn)最短路徑搜索。通過這次實驗，不僅掌握了貪心算法，還掌握了隨機產(chǎn)生一個圖并計算具最愆路徑的算法，讓我覺得收獲頗大。實驗得分助教簽名附錄：完整代碼#include#include#include^definemaxint1000intc[200][200]={0};voidDijkstra(intn,intv,in