單源最短路徑(貪心法)實(shí)驗(yàn)報(bào)告

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

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

2、2、3步，直到所有候選集點(diǎn)都被加入到終點(diǎn)集中。關(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;}〃找到第一個(gè)可行源點(diǎn)s[]標(biāo)志，記錄prev[]前一個(gè)點(diǎn)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測(cè)試結(jié)果請(qǐng)輸入源點(diǎn):11到1的最短路徑為：1到2的最短路徑為:1到3的最短路徑為：1到4的最短路徑為:1到5的最短路徑為:1到6的最短路徑為:1到7的最短路徑為:1到8的最短路徑

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

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

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