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è)班級 信息計算1 班 學(xué) 號 學(xué)生姓名 陳輝騰 指導(dǎo)教師 劉志煌 2016年6月13日圖的最短路徑實(shí)現(xiàn)14信計1班陳輝騰實(shí)驗(yàn)要求：廣東省主要大城市之間的交通圖如下所示，每條邊上的權(quán)值代表從城市A到城市B的路途長度，使用數(shù)據(jù)結(jié)構(gòu)圖的相關(guān)理論編程給出廣州到各個城市的最短路徑，并且輸出經(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表示出來（每個城市看做一個頂點(diǎn)，廣州是v0），然后用c語言實(shí)現(xiàn)書上的迪杰斯特

2、拉算法，求有向網(wǎng)g的v0頂點(diǎn)到其余頂點(diǎn)v的最短路徑保存到Dv，以及途經(jīng)的一個最近新的路徑保存Pathv。最后輸出Dv以及Pathv。構(gòu)造領(lǐng)接矩陣代碼如下（詳細(xì)思路寫在代碼注釋里面）：其中：（v0是廣州；v1是佛山；v2是肇慶；v3是珠海；v4是深圳；v5是南寧；v6是香港）數(shù)據(jù)類型定義：構(gòu)造上述領(lǐng)接矩陣函數(shù)代碼：運(yùn)行結(jié)果如下：求最短距離和路徑函數(shù)如下：其中，PassPath(Path,i,v0)函數(shù)實(shí)現(xiàn)如下：SetName(i)函數(shù)（根據(jù)矩陣的行列數(shù)i，獲得對應(yīng)的城市名）實(shí)現(xiàn)如下：運(yùn)行求解結(jié)果為：總結(jié)：一開始覺得圖的好難，不過，確實(shí)很難啊，圖比樹復(fù)雜多了。其實(shí)還有一部分原因是自己對圖比較陌生的

3、緣故吧。對于這個求最短路徑的算法的難點(diǎn)，個人覺得是在輸出路徑那里，巧妙的用到了遞歸。還有我覺得，怎么把巧妙的吧途經(jīng)最短路徑保存下來？處理這個問題我就覺得是一個難點(diǎn)，把這個問題處理的好，輸出時就比較不用那么麻煩。書本是用一個二維數(shù)組p和一個一維數(shù)組p來處理，兩個數(shù)組名還一樣，個人不太懂最后面一行沒看懂，就是：pw=pv;pww=TRUE;/pw=pv+w,書本也沒有對其路徑的輸出做處理，我也沒有深究下去，而是參考別的資料采用另一種方法來處理（不過都是差不多的吧）?？偟膩碚f，個人覺得輸出路徑的函數(shù)PassPath()很經(jīng)典。另外一開始看不懂書本上的算法就感覺好打擊，后來就分析算法后面的運(yùn)行情況，上

4、機(jī)調(diào)試，慢慢的就基本明白了。算法實(shí)現(xiàn)后，就是要解決給用戶的體驗(yàn)效果了，這個就不難，僅做簡單處理，寫了一個簡單的SetName()函數(shù)（名字取得不太好，應(yīng)該叫GetName()），然后選擇適當(dāng)?shù)臅r候輸出適當(dāng)?shù)脑捇虺鞘忻托辛?。附錄：（代碼）頭文件部分：#include#define INF 1000 /最大值無窮#define MAX_VERTEX_NUM 7 /最大頂點(diǎn)數(shù)typedef enum DG,DN,UDG,UDN GraphKind;/有向圖，有網(wǎng)圖，無向圖，無網(wǎng)圖typedef int InfoType;/ 弧相關(guān)信息類型/弧相關(guān)信息的指針typedef char VertexTy

5、pe; / 頂點(diǎn)數(shù)據(jù)類型typedef int VRType; / 頂點(diǎn)關(guān)系類型。對無權(quán)圖，用0或者1表示是否相鄰。對帶權(quán)圖，直接表示權(quán)值。typedef struct ArcCellVRType adj; / 頂點(diǎn)關(guān)系類型,對無權(quán)圖，用0或者1表示是否相鄰。對帶權(quán)圖，直接表示權(quán)值InfoType *info;/弧相關(guān)信息的指針AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef structVertexType vexsMAX_VERTEX_NUM;/頂點(diǎn)向量AdjMatrix M;/鄰接矩陣int vNum,eNum;/頂點(diǎn)數(shù)弧數(shù)GraphKind k

6、ind;MGraph;int CreateDN(MGraph &g)for(int i=0;iMAX_VERTEX_NUM;i+)for(int j=0;jMAX_VERTEX_NUM;j+)g.Mij.adj=INF;if(i=j)g.Mij.adj=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.vN

7、um=g.eNum=MAX_VERTEX_NUM;char c = #;printf(有向網(wǎng)帶權(quán)鄰接矩陣為（#代表無窮大）：nn);printf( 廣州 佛山 肇慶 珠海 深圳 南寧 香港n);for(int k=0;kg.eNum;k+)for(int l=0;lg.eNum;l+)if(g.Mkl.adj != 1000)printf(%5d,g.Mkl.adj);else printf(%5c,c);printf(n);printf(n);return 1;源文件部分：#include #includeShortestPath.hvoid SetName(int i)switch(i)c

8、ase 0 : printf(廣州);break;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的最短路徑同時途經(jīng)了b和c。而根據(jù)d只能得到一個i（k）/故只能求出c?，F(xiàn)在也要求出b來，只能通過c來求，所以形成了遞歸。void PassPath(int p,in

9、t i,int v)int k = pi;if(k=v)return;/直達(dá)，無路徑。PassPath(p,k,v);/遞歸調(diào)用SetName(k);printf(-);void ShortestPath(MGraph g,int v0)int const MAX = MAX_VERTEX_NUM;int SMAX;/S集-為1時意味著保存了最終v0到v的最短路徑int DMAX;/最短距離int PathMAX;/若Pathi=j,表示v0-vi的最短距離的路徑包含vj。/而且vj一直保持被更新狀態(tài)，輸出路徑時就要用到遞歸。for(int v=0;vg.eNum;+v)/初始化Sv = -1

10、;/S集里面設(shè)為空Dv = g.Mv0v.adj;/矩陣第一行（即v0到其他點(diǎn)的直接距離）賦給D;if(DvINF)Pathv = v0;/路徑設(shè)為空else Pathv = -1;Dv0 = 0;Pathv0 = 0;Sv0 = 1;/v0加入S集/開始主循環(huán)，每次求得v0到其他頂點(diǎn)v的最短路徑，并加v到S集for(int i=1;ig.eNum;i+)int v;int min = INF;/min保存當(dāng)前所知離v0頂點(diǎn)最近的距離for(int w=0;wg.eNum;w+)if(Sw = -1)/w頂點(diǎn)不在S里if(Dwmin)v = w;/記下當(dāng)前最短距離的位置min = Dw;/修改

11、minSv = 1;/加入S集for(int w=0;wg.eNum;w+)if(Sw = -1 & (min + g.Mvw.adj Dw)Dw = min + g.Mvw.adj;/修改當(dāng)前最短距離Pathw = v;/保存下途經(jīng)路徑，并隨時更新/輸出最短距離for(int i=0;ig.eNum;i+)if(Di=1000) printf(廣州到);SetName(i);printf(的最短距離為：無窮大n);else printf(廣州到);SetName(i);printf(的最短距離為：%dn,Di);/輸出Pathprintf( path:);for(int i=0;ig.eNu