最短路徑實驗報告

實驗最短路徑

姓名：班級：學(xué)號：試驗時間：一、從某個源點到其余各頂點的最短路徑1、問題描述本實驗實現(xiàn)dijkstia算法。圖存儲采用了數(shù)組存儲結(jié)構(gòu)。圖類的定義為第9.1.1節(jié)圖類的修改，僅保留了與本程序有關(guān)的成員函數(shù)，增添了一個求單源點最短路徑的成員函數(shù)。2、算法設(shè)計源程序：template<classT>voidMGraph<T>::ShoilestPath_DIJ(mtvO.PatliMatiix_1&P,ShoitPathTable&D)〃用Dijkstra算法求有向網(wǎng)的vO頂點到其余頂點v的最短路徑P[v]及帶權(quán)長度//D[v]o若P[v][w]為true,則w是從vO到v當(dāng)前求得最短路徑上的頂點。//fiiial[v]為true當(dāng)且僅當(dāng)vGS,即已經(jīng)求得從vO到v的最短路徑{mtv,w,i,j,nuii;boolfinal[MAX_\TRTEX_NUM];//輔助矩陣，為真表示該頂點到vO的最短距離己求出，初值為假for(v=O;v<mgiaph.vexnum;v++){final[v]=false;//設(shè)初值D[v]=mgiaph.arcs[\O][v].adj;〃D□存放vO到v的最短距離，初值為vO到v的直接距離fbr(w=0;w<mgraph.vexiium;w++)//設(shè)空路徑{P[v][w]=false;}if(D[v]<infiiuty)//vO到v有直接路徑{_P[v][vO]=P[v][v]=tme;//―維數(shù)組p[v]口表示源點vO到v最短路徑通過的頂點}}D[vO]=0;//vO到vO距離為0final[\O]=true;〃vO頂點并入S集for(i=1;i<mgraph.vexiium;i++)〃其余G.vexiium-1個頂點〃開始主循環(huán)，每次求得vO到某個頂點v的最短路徑，并將v并入S集min=nifuuty；//當(dāng)前所知離vO頂點的最近距離，設(shè)初值為8fbr(w=O;w<mgraph.vexiium;w++)//對所有頂點檢查{if(!fuial[w]&&D[w]<inui)〃在S集之外的頂點中找離vO最近的頂點，并將其賦給v,距離賦給min{v=w;niin=D[w];}final[v]=tme;//離vO最近的v并入S集fbr(w=O;w<mgraph.vexiium;w++)//根據(jù)新并入的頂點，更新不在S集的頂點到vO的距離和路徑數(shù)組{ift!fuial[w]&&nuii<mfuuty&&mgiapli.aics[v][w].adj<uifuuty&&(mui+mgiapli.aics[v][w].adj<D[w]))〃w不屬于S集且vO—v—w的距離<目前vO—w的距離{D[w]=min+mgraph.aics[v][w].adj;//更新D[w]for(j=0;j<mgiapli.vexiiumj++)//修改P[w],vO到w經(jīng)過的頂點包括vO到v經(jīng)過的頂點再加上頂點W{P[W]|J]=P[V]|J]；}P[w][w]=true;}}}3、運行與測試程序運行如圖所示。

■?G:\學(xué)習(xí)謂湊結(jié)構(gòu)實\9.4\DLI\Debug\SPath_DU.exe-)頂構(gòu)個結(jié)各儲余組到警(源圖個創(chuàng)^擇擇人人兀人人人人人、???選選占小123主冃青主冃主冃青主冃主冃青主冃主冃青5■?G:\學(xué)習(xí)謂湊結(jié)構(gòu)實\9.4\DLI\Debug\SPath_DU.exe-)頂構(gòu)個結(jié)各儲余組到警(源圖個創(chuàng)^擇擇人人兀人人人人人、???選選占小123主冃青主冃主冃青主冃主冃青主冃主冃青5y頂235411:bcddbC為8aacbee辟有弧鄰85,d占竄占I:占篇諭苓bC終終終終終終網(wǎng)理楓點%b竄占第占竄向加的頂.:起起起起起起有衣項網(wǎng)的網(wǎng)頂弧弧弧弧弧弧弧b需要向個淺25鍔網(wǎng)個向的-coCOcocoCOco3-弓111111a01010單x創(chuàng)建圖（數(shù)組匠儲結(jié)構(gòu)）

求魯個源蓋到苴余各個頂點的最短路徑

變單項：2

徑數(shù)組pliHjl^n下二0000801000001002到各頂點的最短路徑長度為;a~b:2a-c：3a-d:6Stepl：運行程序，屏幕顯示菜單。Step2：運行功能選擇。Casel：輸入T,選擇菜單項1,進入圖的創(chuàng)建操作。1.1根據(jù)屏幕提示，創(chuàng)建有向網(wǎng)。1.2屏幕顯示網(wǎng)信息。Case2：輸入“2”，選擇菜單項2,進入求源點到其他各點的距離操作。屏幕顯示求得源點到其他各點的距離和路徑數(shù)組。Case3:輸入“3”，選擇菜單項3,結(jié)束程序運行。二、每一對頂點之間的最短路徑1、問題描述本程序用于驗證flovd算法。圖采用了鄰接表存儲。圖類的定義為第9.1.2節(jié)圖類的修改，僅保留了與本程序用到的基本操作，増?zhí)砹送負(fù)渑判虺蓡T函數(shù)。2、算法設(shè)計源程序：template<classT>voidMGraph<T>::ShortestPatli_FLOYD(PatliMatrix_2&RDistaiicMatiix&D)//用Floyd算法求有向網(wǎng)G中各對頂點v和w之間的最短路徑P[v][w]及其帶權(quán)長度D[v][w]//若P[v][w][u]為TRUE,則u是從v到w當(dāng)前求得最短路徑上的頂點。{intu,v,wj;fbr(v=0;v<mgraph.vexiium;v++)〃各對結(jié)點之間初始已知路徑及距離{for(w=0;w<mgraph.vexiiuin;w++){D[v][w]=mgraplLaics[v][w].adj;//頂點v到頂點w的直接距離fbr(u=0;u<mgiaph.vexnum:u++){P[v][w][u]=false;//路徑矩陣初值}if(D[v][w]<mfinity)〃從V到w有直接路徑{P[v][w][v]=P[v][w][w]=tine;〃由v到w的路徑經(jīng)過v和w兩點}}}for(u=0;u<mgraph.vexiium;u-H-){fbr(v=O;v<mgraph.vexnum;v-H-){fbr(w=O;w<mgraph.vexiium;w++){if(D[v][u]+D[u][w]<D[v][w]){D[v][w]=D[v][u]+D[u][w];//更新最短距離fbr(i=0:i<mgraph.vexiium;i++)P[V][W][1]=P[v][u][l]||P[u][w][i]；}3、運行與測試a°G:\學(xué)習(xí)謂濡結(jié)構(gòu)賣跪\g_^\9?4\FLOYD\Debug\：SP￡th_FLO￥D?exy興徑1路組之7Xrl無向網(wǎng)CL》05461132菜圖對?建一岀操畐貫口二二一亍<?「迤衆(zhòng)aaaasa捌I??-II點123主冃主冃土冃主冃主冃主冃主冃主冃主冃主冃M兩IIbacaCabacbbc喙唆1種點ab占養(yǎng)占竄向的11的頂：，起起起起起星??網(wǎng)的網(wǎng)頂弧弧弧弧弧弧G作向要向個WWWb4電一一一一一￡a...?...xaaaaaa^t>-■<0數(shù)網(wǎng)A.—向的有弧壬網(wǎng)鄰X傕—路91S0單存間組之7\-11翼2

8菜圖對作建一岀操創(chuàng)每退疊-1230離離離離離離一n--n--n=n--n--n-ss3SSs馬一CH=Ee=s_?ES_-20曇5SBB取」」二-J二」「-」n-07bcacabr.到到到到到aa■■■■rj■過經(jīng)經(jīng)經(jīng)經(jīng)經(jīng)經(jīng)bacab陣到到到到到到aabbcc由由由由由由Stepl：運行程序，屏幕顯示菜單。Step2：運行功能選擇。Casel：輸入“1”，選擇菜單項1,進入圖的創(chuàng)建操作。1.3根據(jù)屏幕提示，創(chuàng)建有向網(wǎng)。1.4屏幕顯示網(wǎng)信息。Case2：輸入“2”，選擇菜單項2,進入求各點之間最短距離的操作。屏幕顯示求得各點之間的最短的距離和路徑。Case3:輸入“3”，選擇菜單項3,結(jié)束程序運行。4、思考題閱讀源程序，回答下列問題。1）有向圖的單源點問題與無向圖的單源點問題求解有何異同？答：將無向圖中一條無向邊看作方向任意的一條有向邊，得到一有