《數(shù)據(jù)結(jié)構(gòu)課程設(shè)計》最短路徑問題實驗報告.

1、一、 概述1二、系統(tǒng)分析 1三、概要設(shè)計2四、詳細(xì)設(shè)計54.1建立圖的存儲結(jié)構(gòu) 54.2單源最短路徑64.3任意一對頂點之間的最短路徑 7五、運行與測試 812參考文獻(xiàn)11附錄交通咨詢系統(tǒng)設(shè)計（最短路徑問題）一、概述在交通網(wǎng)絡(luò)日益發(fā)達(dá)的今天，針對人們關(guān)心的各種問題，利用計算機(jī)建立一個交通咨詢系統(tǒng)。在系統(tǒng)中采用圖來構(gòu)造各個城市之間的 聯(lián)系，圖中頂點表示城市，邊表示各個城市之間的交通關(guān)系，所帶權(quán) 值為兩個城市間的耗費。這個交通咨詢系統(tǒng)可以回答旅客提出的各種 問題，例如：如何選擇一條路徑使得從 A城到B城途中中轉(zhuǎn)次數(shù)最少； 如何選擇一條路徑使得從 A城到B城里程最短；如何選擇一條路徑使 得從A城到B

2、城花費最低等等的一系列問題。二、系統(tǒng)分析設(shè)計一個交通咨詢系統(tǒng)，能咨詢從任何一個城市頂點到另一城市 頂點之間的最短路徑（里程）、最低花費或是最少時間等問題。對于不 同的咨詢要求，可輸入城市間的路程、所需時間或是所需費用等信息。針對最短路徑問題，在本系統(tǒng)中采用圖的相關(guān)知識，以解決在實 際情況中的最短路徑問題，本系統(tǒng)中包括了建立圖的存儲結(jié)構(gòu)、 單源 最短問題、對任意一對頂點間最短路徑問題三個問題， 這對以上幾個 問題采用了迪杰斯特拉算法和弗洛伊德算法。并未本系統(tǒng)設(shè)置一人性 化的系統(tǒng)提示菜單，方便使用者的使用。二、概要設(shè)計可以將該系統(tǒng)大致分為三個部分： 建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)； 解決單源最短路徑問題

3、； 實現(xiàn)兩個城市頂點之間的最短路徑問題。交通咨詢系統(tǒng)1 T立的儲構(gòu) 建圖存結(jié)義迪杰斯特拉算法（單源最短路徑）費洛依 德算法（任意 頂點對 間最短 路徑）迪杰斯特拉算法流圖:弗洛伊德算法流圖:四、詳細(xì)設(shè)計4.1建立圖的存儲結(jié)構(gòu)定義交通圖的存儲結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點之間相鄰關(guān) 系的矩陣。設(shè)G=(V,E)是具有n個頂點的圖，貝S G的鄰接矩陣是具有 如下定義的n階方陣。Wj，若(Vi,Vj)或 Vi,Vj=E E(G)Ai,j“0或%其他情況注：一個圖的鄰接矩陣表示是唯一的！其表示需要用一個二維數(shù) 組存儲頂點之間相鄰關(guān)系的鄰接矩陣并且還需要用一個具有n個元素的一維數(shù)組來存儲頂點信息(下標(biāo)為i

4、的元素存儲頂點Vi的信息)。 鄰接矩陣的存儲結(jié)構(gòu)：#define MVNum 100 / 最大頂點數(shù)typedef structVertexType vexsMVNum;頂點數(shù)組，類型假定為 char型Adjmatrix arcsMVNumMVNum;鄰接矩陣，假定為 int 型MGraph;注：由于有向圖的鄰接矩陣是不對稱的，故程序運行時只需要輸入所有有向邊及其權(quán)值即可。4.2單源最短路徑單源最短路徑問題：已知有向圖（帶權(quán)），期望找出從某個源點S V到G中其余各頂點的最短路徑。迪杰斯特拉算法即按路徑長度遞增產(chǎn)生諸頂點的最短路徑算法。算法思想：設(shè)有向圖G=（V,E），其中V=1,2 ,n, c

5、ost是表 示G的鄰接矩陣，costij表示有向邊i,j的權(quán)。若不存在有向邊 i,j，則costij 的權(quán)為無窮大（這里取值為32767）。設(shè)S是一個集合， 集合中一個元素表示一個頂點，從源點到這些頂點的最短距離已經(jīng)求 出。設(shè)頂點Vi為源點，集合S的初態(tài)只包含頂點M。數(shù)組dist記錄 從源點到其它各頂點當(dāng)前的最短距離，其初值為disti= costij , i=2 ,n。從S之外的頂點集合 V-S中選出一個頂點 w,使distw的值最小。于是從源點到達(dá) w只通過S中的頂點，把w加入集合S中，調(diào)整dist中記錄的從源點到V-S中每個頂點v的 距離：從原來的distv和distw+costwv中選

6、擇較小的值作為新的distv。重復(fù)上述過程，直到S中包含V中其余頂點的最短路 徑。最終結(jié)果是：S記錄了從源點到該頂點存在最短路徑的頂點集合， 數(shù)組dist記錄了從源點到V中其余各頂點之間的最短路徑，path是 最短路徑的路徑數(shù)組，其中pathi表示從源點到頂點i之間的最短 路徑的前驅(qū)頂點。4.3任意一對頂點之間的最短路徑任意頂點對之間的最短路徑問題，是對于給定的有向網(wǎng)絡(luò)圖G=(V,E),要對G中任意一對頂點有序?qū)?，“V,W(VmW)”找出V到W 的最短路徑。而要解決這個問題，可以依次把有向網(wǎng)絡(luò)圖中每個頂點 作為源點，重復(fù)執(zhí)行前面的迪杰斯特拉算法n次，即可求得每對之間 的最短路徑。費洛伊德算法的

7、基本思想：假設(shè)求從 V到V的最短路徑。如果存在一條長度為arcsij的路徑，該路徑不一定是最短路徑，還需要進(jìn)行n次試探。首先考慮路徑Vi,Vi和Vi,Vj是否存在。如果存 在，則比較路徑Vi.V j和Vi,Vi,Vj的路徑長度，取長度較短者為當(dāng) 前所求得。該路徑是中間頂點序號不大于1的最短路徑。其次，考慮從Vi到Vj是否包含有頂點V2為中間頂點的路徑VVi,v 2,Vj,若 沒有，則說明從Vi到Vj的當(dāng)前最短路徑就是前一步求出的；若有， 那么Vi ,V 2,V j 可分解為VVi ,V 2和VV2,V j ，而這兩條路 徑是前一次找到的中間點序號不大于 1的最短路徑，將這兩條路徑長 度相加就得

8、到路徑VVi,V 2,Vj的長度。將該長度與前一次中求得 的從Vi到Vj的中間頂點序號不大于1的最短路徑比較，取其長度較 短者作為當(dāng)前求得的從Vi到Vj的中間頂點序號不大于2的最短路徑。 依此類推直至頂點Vn加入當(dāng)前從Vi到Vj的最短路徑后，選出從Vi到Vj的中間頂點序號不大于n的最短路徑為止。由于圖G中頂點序 號不大于n,所以Vi到Vj的中間頂點序號不大于n的最短路徑，已考 慮了所有頂點作為中間頂點的可能性，因此，它就是Vi到Vj的最短路徑五、運行與測試徐州實例1運行結(jié)果: NW算耳直耳個數(shù)和邊數(shù)八哄廠仙11 短短 蟲H 有帀 到個 市兩 _任1源點=12-3-13-1路徑長04513911

9、36711?請選擇記或2,選擇曬退出=15-4-7-1&-2-3-1723687,1385 76,1385薩選擇江或2,詵擇印艮出: 希徑嚼嚴(yán).醫(yī)徑長&丄2SG6957042018227413S5一任 kuK 習(xí)習(xí)2-3-1314-16-3-17-4-1卜em求城 幣 之 間 最短 路徑h青選擇或趴選擇回退岀:XX XX XX XX XX XX求城市之I El耳貳短E備彳仝XXXXXXXXKXXXt i 曇取 市間 城之 有市 MB 到個 市兩 WS g 一任 f請選擇=i或z,選擇退岀二誡松馳鰲一7徑路長度沁3*求城市之間最邁路徑*W*eHHf1 短短 中可 城之 有帀 飾城 到個 市兩 $

10、 一任 1請選擇二1或2,選擇陌退出：2輸入源點（或起點）和終點3叭？朋戲頂點？至2最短路徑路徑是=?-4-3-2徑路長度次5“六、總結(jié)與心得該課程設(shè)計主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡(luò)問題入手，進(jìn)而利用計算機(jī)去建立一個交通咨詢系統(tǒng)，以處理和解決旅客們關(guān)心 的各種問題（當(dāng)然此次試驗最終主要解決的問題是： 最短路徑問題）。這次試驗中我深刻的了解到了樹在計算機(jī)中的應(yīng)用是如何的神奇與靈活，對于很多的問題我們可以通過樹的相關(guān)知識來解決，特別 是在解決最短路徑問題中，顯得尤為重要。經(jīng)過著次實驗，我了解到了關(guān)于樹的有關(guān)算法，如：迪杰斯特拉 算法、弗洛伊德算法等，對樹的學(xué)習(xí)有了一個更深的了解。參考文獻(xiàn)【1

11、】數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏.清華大學(xué)出版社.【2】數(shù)據(jù)結(jié)構(gòu)課程設(shè)計蘇仕華.極械工業(yè)出版社.附錄#in clude#in clude#defi ne MVNum 100#define Maxi nt 32767enum boolea nFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum; void CreateMGra

12、ph(MGraph * G ,int n,int e) int i,j,k,w;for(i=1;ivexsi=(char)i;for(i=1;i=n ;i+)for(j=1;jarcsij=Maxi nt;printf(輸入 %d 條邊的 i.j 及 w:n,e); for(k=1;karcsij=w;n);printf(有向圖的存儲結(jié)構(gòu)建立完畢！void Dijkstra(MGraph *G ,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,mi n;en um boolean SMVNum;for(v=1;varcsv1v;if(D2vMaxi nt)

13、p2v=v1;elsep2v=0;D2v1=0; Sv1=TRUE;for(i=2;i n; i+)mi n=Maxi nt;for(w=1;w=n; w+)if(!Sw & D2wmi n)v=w;mi n=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw; p2w=v;printf(路徑長度路徑n);for(i=1;i=n; i+)prin tf(%5d,D2i);prin tf(%5d,i);v=p2i;while(v!=O)prin tf(-%d,v);v=p2v;prin tf(n);void Floyd(MGraph *G,i nt n)int i,j,k,v,w

14、;for(i=1;i=n ;i+)for(j=1;jarcsij!=Maxi nt)pij=j;elsepij=0;Dij=G-arcsij;for(k=1;k=n; k+)for(i=1;i=n ;i+)for(j=1;j=n ;j+)if(Dik+DkjDij)Dij=Dik+Dkj; pij=pik；void mai n()MGraph *G;int m, n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(輸入圖中頂點個數(shù)和邊數(shù)n ,e:);scan f(%d,%d, &n,& e);CreateMGraph(G, n,e);while(xz!=0)prin tf(*求城市之間最短路徑 *、n”)；prin tf(”= n);printf(1.求一個城市到所有城市的最短路徑n);printf(2.求任意的兩個城市之間的最短路徑n);prin tf(”= n); printf(請選擇:1或2，選擇0退出:n);scan f(%d，& xz);if (xz=2)Floyd(G, n);printf(輸入源點(或起點)和終點:v,w:);scan f(%d,%d, &v,&w);k=pvw;