最短路徑實(shí)驗(yàn)報(bào)告

1、實(shí)驗(yàn)最短路徑姓名：班 級(jí)：學(xué)號(hào)：試驗(yàn)時(shí)間：一、從某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑1、問(wèn)題描述本實(shí)驗(yàn)實(shí)現(xiàn)dijkstia算法。圖存儲(chǔ)采用了數(shù)組存儲(chǔ)結(jié)構(gòu)。圖類的定義為第9.1.1節(jié)圖類的 修改，僅保留了與本程序有關(guān)的成員函數(shù)，增添了一個(gè)求單源點(diǎn)最短路徑的成員函數(shù)。2、算法設(shè)計(jì)源程序：template void MGraph: ShoitestPath_DIJ(mt vO.PatliMatrix_ 1 &P,ShoitPathTable &D)用Dijkstra算法求有向網(wǎng)的vO頂點(diǎn)到其余頂點(diǎn)v的最短路徑Pv及帶權(quán)長(zhǎng)度/Dvo若Pvw為true,則w是從vO到v當(dāng)前求得最短路徑上的頂點(diǎn)。finalv為

2、true當(dāng)?shù)﹥H當(dāng)vGS,即己經(jīng)求得從vO到v的最短路徑fmtbool finalMAX_TRTEX_NUM; /輔助矩陣，為真表示該頂點(diǎn)到vO的最短距離 己求出，初值為假fbr(v = O;vmgiaph.vexnum;v+)(finalv = false; / 設(shè)初值Dv = mgiaph.arcsOv.adj; /D存放 vO 到 v 的最短距離，初值為 vO 到 v 的 直接距離for(w = 0; wmgraph. vexiiuni; w+)/設(shè)空路徑(Pvw = false;if(Dvinfinity)/vO到v有直接路徑( _PvvO = Pvv = tine; / 一維數(shù)組pv表

3、示源點(diǎn)vO到v最短路徑通過(guò) 的頂點(diǎn))DvO = 0; / vO 到 vO 距離為 0finalvO = true; / vO 頂點(diǎn)并入 S 集fbr(i = 1 ;imgraph.vexiium;i+)/其余G.vexiium-1個(gè)頂點(diǎn)開(kāi)始主循環(huán)，每次求得vO到某個(gè)頂點(diǎn)v的最短路徑，并將v并入S集 min = infinity; /當(dāng)前所知離vO頂點(diǎn)的最近距離，設(shè)初值為8fbr(w = O;wmgraph.vexiium;w+)/對(duì)所有頂點(diǎn)檢查(if(!fuialw&Dwinui) 在S集之外的頂點(diǎn)中找離vO最近的頂點(diǎn)，并將 其賦給v,距離賦給min(v = w;niin = Dw;)fina

4、lv = tme; /離vO最近的v并入S集fbr(w = O;wmgraph.vexiium;w+)/根據(jù)新并入的頂點(diǎn)，更新不在S集的頂點(diǎn)到vO的距離和路徑數(shù)組(ift!fuialw&nuiimfuuty&mgiapli.aicsv w .adjuifuuty&(mui+mgiapli.aicsv w .adj D w)/w不屬于S集且vOvw的距離v目前vOw的距離(D w = nunmgiaph.aicsv w.adj; / 更新 D wfbr(j = 0 ;j 頂構(gòu)個(gè)結(jié)各儲(chǔ)余雷組魚(yú)蓍(源圖個(gè)w擇擇A八&八八人A八 . - 選選 占 g 12 3青青青青青青主目青青主DC青5y頂2 3

5、5 4 11 : b c d d b C 為 8 a a c b e e 田 有弧鄰8 丸d品占$:占s:占噩 g初bC終終終終終終網(wǎng) vxfcfe% 的頂：、起起起起起起有d 占八 C 頂網(wǎng)的網(wǎng)頂弧弧弧弧弧弧Mh 膏要向個(gè) &3 65辨 網(wǎng)個(gè) 向的-coCOcocococococo3- 1111111a0 0 0010 000 10010 100 0 00單 創(chuàng)建圖（裁組任儲(chǔ)結(jié)構(gòu)） 求富個(gè)源志到址余各個(gè)頂點(diǎn)的最短路徑 纂單項(xiàng):2 徑救組pHHj如下二a到各頂點(diǎn)的最短路徑長(zhǎng)度為;ab: 2a-c ：3a-d: 6Stepl：運(yùn)行程序，屏幕顯示菜單。Step2：運(yùn)行功能選擇。Casel：輸入“1

6、”，選擇菜單項(xiàng)1,進(jìn)入圖的創(chuàng)建操作。1.1根據(jù)屏幕提示，創(chuàng)建有向網(wǎng)。1.2屏幕顯示網(wǎng)信息。Case2：輸入“2”，選擇菜單項(xiàng)2,進(jìn)入求源點(diǎn)到其他各點(diǎn)的距離操作。 屏幕顯示求得源點(diǎn)到其他各點(diǎn)的距離和路徑數(shù)組。Case3:輸入“3”，選擇菜單項(xiàng)3,結(jié)束程序運(yùn)行。二、每一對(duì)頂點(diǎn)之間的最短路徑1、問(wèn)題描述本程序用于驗(yàn)證flovd算法。圖采用了鄰接表存儲(chǔ)。圖類的定義為第9.1.2節(jié)圖類的修 改，僅保留了與本程序用到的基本操作，增添了拓?fù)渑判虺蓡T函數(shù)。2、算法設(shè)計(jì)源程序：template void MGraph: ShortestPatli_FLOYD(PatliMatrix_2 &RDistaiicMa

7、tiix &D)/用Floyd算法求有向網(wǎng)G中各對(duì)頂點(diǎn)v和w之間的最短路徑P vw及其帶權(quán)長(zhǎng)度Dvw /若Pvwu為T(mén)RUE,則u是從v到w當(dāng)前求得最短路徑上的頂點(diǎn)。int u,v,w,i;fbr(v = 0; vmgraph. vexiium; v+)各對(duì)結(jié)點(diǎn)之間初始己知路徑及距離Ifbr(w = 0; wmgraph. vexiiuin; w+)(Dvw = mgraplLaicsvw.adj;/ 頂點(diǎn) v 到頂點(diǎn) w 的直接距離fbr(u = 0 ;umgiaph. vexnum:u+)(Pvwu = false;/ 路徑矩陣初值if(D v winfinity)從V到w有直接路徑(Pv

8、wv = Pvww = tnie;由 v 到 w 的路徑經(jīng)過(guò) v 和 w 兩點(diǎn))fbr(u = 0 ;umgraph. vexiium;u-H-)fbr(v = O;vmgraph.vexnum;v-H-)(fbr(w = O;wmgraph.vexiium;w+)(if(Dvu+DuwDvw)(Dvw=Dvu+Duw;/ 更新最短距離fbr(i = 0: imgraph. vexiium;i+)PVW1 = Pvul|Puwi；)3、運(yùn)行與測(cè)試a G:學(xué)習(xí)四濡結(jié)構(gòu)實(shí) 99.4FLOYDDebugSPat03 5461132菜圖對(duì) 建一出操章直- - - - - - a - 路 9 1 s 0

9、單存間 組之 -11思2 8菜圖對(duì)作 建一出操 創(chuàng)章善-12 3 0 63*高離離離離離 一 n-n-n = n-n-n- s s 3SS S 一勺一乜一乜一一翌翌程 一 2 昏WBSBB取jI-j 二 Ju_ -Ji- LI2,n -0 7 b c a clab r.到到到到到Cb b b Caaaba a 經(jīng)經(jīng)經(jīng)經(jīng)經(jīng)經(jīng) blclacab 陣到到到到.到到 a a b b c C 由由由由由由Stepl：運(yùn)行程序，屏幕顯示菜單。Step2：運(yùn)行功能選擇。Casel：輸入“1”,選擇菜單項(xiàng)1,進(jìn)入圖的創(chuàng)建操作。1.3根據(jù)屏幕提示，創(chuàng)建有向網(wǎng)。1.4屏幕顯示網(wǎng)信息。Case2：輸入“2”，選擇菜單項(xiàng)2,進(jìn)入求各點(diǎn)之間最短距離的操作。 屏幕顯示求得各點(diǎn)之間的最短的距離和路徑。Case3:輸入“3”，選擇菜單項(xiàng)3,結(jié)束程序運(yùn)行。4、思考題閱讀源程序，回答下列問(wèn)題。1）有向圖的單源點(diǎn)問(wèn)題與無(wú)向圖的單源點(diǎn)問(wèn)題求解有何異同？答：將無(wú)向圖中一條無(wú)向邊看作方向任意的一條有向邊，得到一有向圖集合，從而可以將路 徑、循環(huán)等有向圖中的基本