用貪心算法解單源最短路徑問題

《用貪心算法解單源最短路徑問題》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、廣東金融學(xué)院實(shí)驗(yàn)報(bào)告課程名稱：算法設(shè)計(jì)與分析課程設(shè)計(jì)實(shí)驗(yàn)編號(hào)及實(shí)驗(yàn)名稱實(shí)驗(yàn)六用貪心算法解單源最短路徑問題系別應(yīng)用數(shù)學(xué)系姓名許夏夢(mèng)學(xué)號(hào)071612117班級(jí)0716121實(shí)驗(yàn)地點(diǎn)新電605實(shí)驗(yàn)日期2009-11-4實(shí)驗(yàn)時(shí)數(shù)4指導(dǎo)教師駱世廣同組其他成員獨(dú)立完成成績(jī)一、實(shí)驗(yàn)?zāi)康募耙?、明確單源最短路徑問題的概念；2、用貪心算法解決單源最短路徑問題；3、通過本例熟悉貪心算法在程序設(shè)計(jì)中的應(yīng)用方法。二、實(shí)驗(yàn)環(huán)境及相關(guān)情況（包含使用軟件、實(shí)驗(yàn)設(shè)備、主要儀器及材料等）使用軟件：C++軟件；使用實(shí)驗(yàn)設(shè)備：計(jì)算機(jī)：Intel（R）;Pentium（R）4CPU2.

2、80GHz;2.79GHz,0.99GB的內(nèi)存；使用系統(tǒng)：MicrosoftWindowsXP;Professional;版本2002；ServicePack2.三、實(shí)驗(yàn)內(nèi)容及步驟（包含簡(jiǎn)要的實(shí)騎步驟流程）實(shí)驗(yàn)內(nèi)容：求網(wǎng)（帶權(quán)有向圖）屮從一個(gè)頂點(diǎn)到其余各頂點(diǎn)間的最短路徑。一個(gè)有向圖G,它的每條邊都有一個(gè)非負(fù)的權(quán)值c[i,j],“路徑長(zhǎng)度"就是所經(jīng)過的所有邊的權(quán)值之和。對(duì)于源點(diǎn)需要找出從源點(diǎn)出發(fā)到達(dá)其他所有結(jié)點(diǎn)的最短路徑。■

3、BZ5-aUX.X3A>?A?五號(hào)?刃貼!SQ

4、：=?

5、=??計(jì)潭淒Xr

6、■?■■it:=?■IM*>r；FilesMicro

7、softVisualStudioMyProjects11Debu<11.mc*from1to2fth?shortestwayis45far：2<**■4

8、x??11"

9、iieroc*CPro(raAaBI魚ec1見改樣式3Hicroso...?S}Uicroioft石單Q勸可1四、實(shí)驗(yàn)結(jié)果（包括程序或圖表、結(jié)論陳述、數(shù)據(jù)記錄及分析等，可附頁）如下圖所示，編程實(shí)現(xiàn)求從任一頂點(diǎn)出發(fā)到其它頂點(diǎn)的最短路徑長(zhǎng)度。（圖見附錄四-1）實(shí)驗(yàn)結(jié)果如下（程序見附錄四-2）：入戻聞希用引用鄰件3?聞進(jìn)Pleaseinputnumberofpoint:6Nowinputlengthitoj：oseiee45ooo15e1Go26ge15oo020ee35G0003605000366Nouinputupoint(0

10、:1五、實(shí)驗(yàn)總結(jié)（包括心得體會(huì)、問題回答及實(shí)驗(yàn)改進(jìn)意見，可附頁）通過在計(jì)算機(jī)實(shí)現(xiàn)用貪心算法解單源最短路徑問題，對(duì)貪心算法有了更進(jìn)一步的理解。“學(xué)精于勤而荒于嬉”，在專業(yè)技能上還需多學(xué)、多看、多練，實(shí)踐是不斷取得進(jìn)步的基礎(chǔ)。我要通過實(shí)踐不斷的鍛煉自己，提高自己解決實(shí)際問題的能力。六、教師評(píng)語附四-1附四-2程序代碼：#inelude#include〈conio.h>intn=0,/*結(jié)點(diǎn)個(gè)數(shù)*/prev[100],/*記錄最短路徑到i的前一個(gè)頂點(diǎn)*/s[101];floata[100][100],/*記錄邊的權(quán)值*/dist[100

11、];/*記錄從源點(diǎn)到i的相應(yīng)最短路徑*/#defineMAXVALUE100000.0voiddijkstra(intv){inti,j;if(v

12、

13、v>n)return;for(i=l;i<=n;i++)/*初始設(shè)置*/{/*初始時(shí)從源點(diǎn)到i的最短路徑設(shè)為從源點(diǎn)到i的權(quán)值*/s[i]=l;/*s[i]二false*/if(dist[i]==MAXVALUE)prev[i]=0;/*從源點(diǎn)到i沒有通路*/elseprev[i]=v;/*從源點(diǎn)到i有通路時(shí)，最短路徑前一個(gè)結(jié)點(diǎn)設(shè)為源點(diǎn)*/}dist[v]=O;/*源點(diǎn)到源點(diǎn)的最短路徑為0*/s[v

14、]二0;/*s[v]二true*//*為卜?面循環(huán)中源點(diǎn)不參加比較做準(zhǔn)備*/for(i=l;i

15、j++)/*找出通過U點(diǎn)是否有更短的路徑*/if((s[j]==l)&&(a[u][j]