數(shù)據(jù)結(jié)構(gòu)圖的最短路徑實(shí)現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)課程名稱數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)題目名稱圖的最短路徑實(shí)現(xiàn)學(xué)生學(xué)院應(yīng)用數(shù)學(xué)學(xué)院專業(yè)班級信息計(jì)算1班學(xué)號3114008104學(xué)生姓名陳輝騰指導(dǎo)教師劉志煌2016年6月13日圖的最短路徑實(shí)現(xiàn)14信計(jì)1班一陳輝騰一3114008104實(shí)驗(yàn)要求：廣東省主要大城市之間的交通圖如下所示，每條邊上的權(quán)值代表從城市A到城市B的路途長度，使用數(shù)據(jù)結(jié)構(gòu)圖的相關(guān)理論編程給出廣州到各個(gè)城市的最短路徑，并且輸出經(jīng)過的路徑。實(shí)驗(yàn)?zāi)康模哼M(jìn)一步了解數(shù)據(jù)結(jié)構(gòu)中對圖的各種操作，以及求最短路徑的算法。實(shí)驗(yàn)內(nèi)容：編程求解上述題目（實(shí)驗(yàn)要求）思路：首先把圖用帶權(quán)鄰接矩陣g表示出來（每個(gè)城市看做一個(gè)頂點(diǎn)，廣州是v0）,然后用c語言實(shí)現(xiàn)書上

2、的迪杰斯特拉算法，求有向網(wǎng)g的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑保存到Dv,以及途經(jīng)的一個(gè)最近新的路徑保存Pathv。最后輸出Dv以及Pathv。構(gòu)造領(lǐng)接矩陣代碼如下（詳細(xì)思路寫在代碼注釋里面）：其中:（v0是廣州；v1是佛山；v2是肇慶；v3是珠海；v4是深圳；v5是南寧；v6是香港）數(shù)據(jù)類型定義：全局的圉）vCreate-DNfMGrapSinclude<stdlih.h）INF1000"最大值無交ifdefineHAX.VE艮tEXJO7最大頂點(diǎn)數(shù)Qiypedefenuff）GD5fUDG,皿用Gt叩hKind;"有向圖，有網(wǎng)圖，無向圖，無網(wǎng)圖1ypedefstIn

3、foType：7弧相關(guān)信息變型“融相關(guān)信息的指鐘-typedefcharVeHei<Typ&/頂點(diǎn)費(fèi)據(jù)類理iypedefirtVRTyp引“頂點(diǎn)關(guān)系類型。時(shí)無權(quán)圖，用。或者1表示是否相郃。對帝權(quán)圖，直接表示權(quán)值。三type品fstructArcCellTRTypeadj;頂點(diǎn)關(guān)器類型，對無權(quán)圖，用?；蛘?表示是否相鄰對帶松圖，直掩表示權(quán)值InfoType朽.時(shí)。強(qiáng)相關(guān)信息的指針ElAdjUatrisMAX_VERTEK_MUlffW_VERTEK_IOI：-typedefstructITertesTypew菖MA:訕RTEXJiim頂點(diǎn)向里AdjustrixM:鄰楚施隧int5k

4、皿eJTina:“頂點(diǎn)數(shù)范數(shù)aphKindkiitd;EllMGraph;構(gòu)造上述領(lǐng)接矩陣函數(shù)代碼:FintGreateDNWraphFortini=0：1<M<_VERTEK_MUM：1+4)(foitint三口：j<MX_VERTEX_NIIN：j+)ff.Hljadj=IMF:MijLadj=0:s.Wl0l.adj=10D；c,I0.adj200；s,I03,ad>200；g.I13.adj=&0；g.M14,adj=1E0;gJT23.adj=100;g.I25.adj=150：e.I34.adj=inO：e,I35,adj=360：g.M4S.adj

5、=lED；g.M64.adj=400；.ME6.adj=E00;eNwiL=UlX_VERTEX_NUM;charc=r#r;psnlfC有向網(wǎng)帚板鄰接矩陣為t,取代襄無究大：pnntf-廣州佛山擎慶珠海聚圳南寧香港5")；for(inik=0;k<eNum;k+)for(int1=0;l<gkeNiin;1+)if(S.M|>1.adj1=1000)printfC%5dn,g.15k1.adj)；gL占號prirrtfC憤5cg);printErn；printfrnn；return1;廣州佛山8100it運(yùn)行結(jié)果如下:C:Windowssystm32cmdEewe

6、有向網(wǎng)帶權(quán)鄰接矩陣為（代表無窮大），肇慶珠海深圳南寧香港2002S0ttittt50tt350Ittt1S0ii430tt請按任意鍵繼續(xù)求最短距離和路徑函數(shù)如下:全局范勖-voidShorteitPath(HCr3phi,iritvO)intcotMAX=1M_VERTEX_NUM：intSMAX>3I時(shí)意底著保存了最終M至必的最短路徑intDUUK："最短距離intPrthEMAX:若F3rthi=>表示vO->e的最短距離的施役包含受力而且行一直保持軾更新狀態(tài)，輸出路徑時(shí)就要用到潴歸。£1(intB。；*g.gNum;+%)/初帕比SM=T;S集里面設(shè)

7、為空Dv=酊肌婭利.冢；“姮陡篥一行(即vO到其他點(diǎn)的直接距離)麟給DU;if(Dv<rNF)Pa±hv=式!：，/，速為空elsePatliv=11Dv3=O;Path.vO=0;SvO=1;/旬加入二集“開始主循環(huán)每次求得訶到其他頂點(diǎn)守的最?yuàn)窂?，并加唔膽隼for(ifft1-1;J-g.tNum;t-M")liftv;mtnin=INF；/7min保存當(dāng)前所知離M頂點(diǎn)最近的距離for(mtw=0；¥<g.sKujil;w+)if(SM=T)/7吶頂點(diǎn)不在S里ifw5in)v=w；/記下當(dāng)前最短距離的位置in=Dw修改肌in)SM=l；M入瞧fcr

8、(intt=0:v<g»&Kuji:w+)if<Svl=-1也量(min十g.Hfvw*adj<Dv)Dw=min.+g,Mvw,ad：</修改當(dāng)H辰短距離PathM=也"保存下途經(jīng)路徑，并隨時(shí)更新|輸出最想即離i.=0：iQ.eNu：T-I-+)if(Di=1000)ptintf(“廣州至I")-mi):psntf的最?yuàn)嚯x為；無窮大tn");elsep嵋出廣州到U；Set:pH毗的量也題離為：塌5二?！究谏陷敵鯬rthprintft“path：").ior(Lnti=0;ig,eNum;i+)prijitfC

9、JSSd"jPathfil);prirrtffVi"):輸出路輕fortinti=0：iCg.elluin：i+)ifCSCil=l廉i>=rO)printfC從廣州到");SetFaae(i);printf("的最短距離的路徑為：廣州-二)二"起點(diǎn)FassPathffath,:"經(jīng)路徑|SetJIame(i)：printfCXn"):終點(diǎn)«i''ir其中，PassPath(Path,i,v0)函數(shù)實(shí)現(xiàn)如下：日輸出路徑困數(shù)如公式的最短路徑途經(jīng)C，而7。的最短路徑途經(jīng)h那其實(shí)的最短路徑同時(shí)途經(jīng)b

10、和h而根據(jù)d只能蹲到一個(gè)i(HI"靛只能求出G?，F(xiàn)在也要求出b來，只能通過G來束，所以形成了遞歸。v&idPa?Fath(intpjinXLintv)inti=Pi.Ilf(k=v)return;"直達(dá)，無SS徑，F(xiàn)assPath(pJkJv);遞歸i局用SetName(k);prizrtfC-*);1SetName(i)函數(shù)(根據(jù)矩陣的行列數(shù)i,獲得對應(yīng)的城市名)實(shí)現(xiàn)如下:L-voidSeiNametinti)ETitch(i)case0：riutf("廣州breal;case1:r工iritf("佛山")；br巧疝:case2:衛(wèi)r

11、irrtfC"肇慶：brgik:case3:printf(")：brealt：case4:pzrintf("深Ull');break;case5:j)rintfCMT");breaJ?;esseS:pidzutfCSS)；運(yùn)行求解結(jié)果為:tt港清海如II-珠深南深>>77一一二山慶山山慶山im>>>>>>-tut1-JrJ-JJ-zJ71-JrJ/廣廣廣廣廣廣0000004H133S二sa01212342KSS8ES為為為為為為為士離離離離離離-一置局離離一&何-n-n-rl-Ln=n-n-

12、一巨巨巨巨巨巨1nsninTKnxRnfnxR-.江-r-r-.o絲H一0f®>>ft-口瞽譬瞽瞽國曾取0的的的的的的的的的的的的山慶海圳矗®州山灰海/,-IIE0嚏聿或深南寮廣羹笠林目-日到意j撲撲力外撲升任廣廣廣州X廣廣廣廣廣廣技總結(jié)：一開始覺得圖的好難，不過，確實(shí)很難啊，圖比樹復(fù)雜多了。其實(shí)還有一部分原因是自己對圖比較陌生的緣故吧。對于這個(gè)求最短路徑的算法的難點(diǎn)，個(gè)人覺得是在輸出路徑那里，巧妙的用到了遞歸。還有我覺得，怎么把巧妙的吧途經(jīng)最短路徑保存下來？處理這個(gè)問題我就覺得是一個(gè)難點(diǎn)，把這個(gè)問題處理的好，輸出時(shí)就比較不用那么麻煩。書本是用一個(gè)二維數(shù)組p田和

13、一個(gè)一維數(shù)組p來處理，兩個(gè)數(shù)組名還一樣，個(gè)人不太懂一最后面一行沒看懂，就是：pw=pv;pww=TRUE;/pw=pv+w,書本也沒有對其路徑的輸出做處理，我也沒有深究下去，而是參考別的資料采用另一種方法來處理（不過都是差不多的吧）?？偟膩碚f，個(gè)人覺得輸出路徑的函數(shù)PassPath()很經(jīng)典。另外一開始看不懂書本上的算法就感覺好打擊，后來就分析算法后面的運(yùn)行情況，上機(jī)調(diào)試，慢慢的就基本明白了。算法實(shí)現(xiàn)后，就是要解決給用戶的體驗(yàn)效果了，這個(gè)就不難，僅做簡單處理，寫了一個(gè)簡單的SetName()函數(shù)(名字取得不太好，應(yīng)該叫GetName(),然后選擇適當(dāng)?shù)臅r(shí)候輸出適當(dāng)?shù)脑捇虺鞘忻托辛?。附錄?代

14、碼)頭文件部分：#include<stdlib.h>#defineINF1000/最大值無窮#defineMAX_VERTEX_NUM7/最大頂點(diǎn)數(shù)typedefenumDG,DN,UDG,UDNGraphKind;/有向圖，有網(wǎng)圖，無向圖，無網(wǎng)圖typedefintInfoType;/弧相關(guān)信息類型弧相關(guān)信息的指針typedefcharVertexType;/頂點(diǎn)數(shù)據(jù)類型typedefintVRType;/頂點(diǎn)關(guān)系類型。對無權(quán)圖，用?；蛘?表示是否相鄰。對帶權(quán)圖，直接表示權(quán)值。typedefstructArcCellVRTypeadj;/頂點(diǎn)關(guān)系類型，對無權(quán)圖，用?；蛘?表示是否

15、相鄰。對帶權(quán)圖，直接表示權(quán)值InfoType*info;/弧相關(guān)信息的指針AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefstructVertexTypevexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrixM;/鄰接矩陣intvNum,eNum;/頂點(diǎn)數(shù)弧數(shù)GraphKindkind;MGraph;intCreateDN(MGraph&g)for(inti=0;i<MAX_VERTEX_NUM;i+)for(intj=0；j<MAX_VERTEX_NUM；j+)g.M皿.adj=INF;if(i=j)g.Mij.adj

16、=0;g.M01.adj=100;g.M02.adj=200;g.M03.adj=200;g.M13.adj=50;g.M14.adj=150;g.M23.adj=100;g.M25.adj=150;g.M34.adj=100;g.M35.adj=350;g.M46.adj=150;g.M54.adj=400;g.M56.adj=500;g.vNum=g.eNum=MAX_VERTEX_NUM;charc='#'printf("有向網(wǎng)帶權(quán)鄰接矩陣為(#代表無窮大)：nn");printf("廣州佛山肇慶珠海深圳南寧香港n");for(in

17、tk=0;k<g.eNum;k+)for(intl=0;l<g.eNum;l+)if(g.Mkl.adj!=1000)printf("%5d",g.Mkl.adj);elseprintf("%5c",c);printf("n");printf("n");return1;源文件部分：#include<stdio.h>#include"ShortestPath.h"voidSetName(inti)switch(i)case0:printf("廣州");b

18、reak;case 1 :printf("佛山");break;case 2 :printf("肇慶");break;case 3 :printf("珠海");break;case 4 :printf("深圳");break;case 5 :printf("南寧");break;case 6 :printf("香港”)；/輸出路徑函數(shù)，如a->d的最短路徑途經(jīng)c,而a->c的最短路徑途經(jīng)b,那其實(shí)a->d的最短路徑同時(shí)途經(jīng)了b和co而不g據(jù)d只能得到一個(gè)i(k)/故只

19、能求出Co現(xiàn)在也要求出b來，只能通過c來求，所以形成了遞歸。voidPassPath(intp,inti,intv)intk=pi;if(k=v)return;/直達(dá)，無路徑。PassPath(p,k,v);/遞歸調(diào)用SetName(k);printf("->");voidShortestPath(MGraphg,intv0)intconstMAX=MAX_VERTEX_NUM;intSMAX;/S集-，為1時(shí)意味著保存了最終v0到v的最短路徑intDMAX;/最短距離intPathMAX;/若Pathi=j,表示v0->vi的最短距離的路徑包含vj。/而且vj

20、一直保持被更新狀態(tài)，輸出路徑時(shí)就要用到遞歸。for(intv=0;v<g.eNum;+v)/初始化Sv=-1;/S集里面設(shè)為空Dv=g.Mv0v.adj;/矩陣第一行(即v0到其他點(diǎn)的直接距離)賦給D口;elsePathv=-1;Dv0=0;Pathv0=0;Sv0=1;/v0加入S集開始主循環(huán)，每次求得v0到其他頂點(diǎn)v的最短路徑，并加v到S集for(inti=1;i<g.eNum;i+)intv;intmin=INF;/min保存當(dāng)前所知離v0頂點(diǎn)最近的距離for(intw=0;w<g.eNum;w+)if(Sw=-1)/w頂點(diǎn)不在S里if(Dw<min)v=w;/記下當(dāng)前最短距離的位置min=Dw;/修改min)Sv=1;/加入S集for(