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

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

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

3、分：建立交通網(wǎng)絡(luò)圖的存儲結(jié)構(gòu)；解決單源最短路徑問題；實現(xiàn)兩個城市頂點之間的最短路徑問題。交通咨詢系統(tǒng)迪杰建 立斯特圖 的拉算存 儲法（單結(jié) 構(gòu)源最義短路徑）迪杰斯特拉算法流圖：費洛依德算法（任意頂點對間最短路徑）2弗洛伊德算法流圖：34四、詳細設(shè)計4.1 建立圖的存儲結(jié)構(gòu)定義交通圖的存儲結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點之間相鄰關(guān)系的矩陣。設(shè) G=(V,E) 是具有 n 個頂點的圖，則 G的鄰接矩陣是具有如下定義的 n 階方陣。Wij，若或E(G)(V i , V j )Vi , V jAi , j 0或，其他情況注：一個圖的鄰接矩陣表示是唯一的！其表示需要用一個二維數(shù)組存儲頂點之間相鄰關(guān)系的鄰接

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

5、生諸頂點的最短路徑算法。算法思想：設(shè)有向圖G=(V,E) ，其中 V=1,2 ，n ，cost 是表示 G的鄰接矩陣，costij表示有向邊 <i,j>的權(quán)。若不存在有向邊<i,j>，則costij 的權(quán)為無窮大（這里取值為 32767）。設(shè) S 是一個集合，集合中一個元素表示一個頂點， 從源點到這些頂點的最短距離已經(jīng)求出。設(shè)頂點 V1 為源點，集合 S 的初態(tài)只包含頂點 V1。數(shù)組 dist 記錄從 源 點 到 其它 各 頂 點 當 前的 最 短 距 離 ，其 初 值 為 disti= costij ，i=2 ，n。從 S 之外的頂點集合 V-S 中選出一個頂點w，使

6、 distw的值最小。于是從源點到達w只通過 S 中的頂點，把w加入集合 S 中，調(diào)整 dist中記錄的從源點到V-S 中每個頂點 v 的距離：從原來的 distv和 distw+costwv中選擇較小的值作為新的 distv 。重復(fù)上述過程，直到 S 中包含 V 中其余頂點的最短路徑。最終結(jié)果是：S記錄了從源點到該頂點存在最短路徑的頂點集合，數(shù)組 dist 記錄了從源點到 V 中其余各頂點之間的最短路徑， path 是最短路徑的路徑數(shù)組， 其中 pathi 表示從源點到頂點 i 之間的最短路徑的前驅(qū)頂點。64.3 任意一對頂點之間的最短路徑任意頂點對之間的最短路徑問題，是對于給定的有向網(wǎng)絡(luò)圖

7、G=(V,E), 要對 G中任意一對頂點有序?qū)Γ?“V,W(VW)”，找出 V 到 W 的最短路徑。而要解決這個問題， 可以依次把有向網(wǎng)絡(luò)圖中每個頂點作為源點，重復(fù)執(zhí)行前面的迪杰斯特拉算法 n 次，即可求得每對之間的最短路徑。費洛伊德算法的基本思想：假設(shè)求從Vi 到 Vj 的最短路徑。如果存在一條長度為 arcsij 的路徑，該路徑不一定是最短路徑，還需要進行 n 次試探。首先考慮路徑 <vi ,v 1 >和<v1,v j >是否存在。如果存在，則比較路徑 <vi .v j >和<vi ,v 1,v j >的路徑長度，取長度較短者為當前所求得。該

8、路徑是中間頂點序號不大于 1 的最短路徑。其次，考慮從 vi 到 vj 是否包含有頂點 v2 為中間頂點的路徑 < vi , ,v 2, ,v j >，若沒有，則說明從 vi 到 vj 的當前最短路徑就是前一步求出的；若有，那么 <vi , ,v 2, ,v j >可分解為 <vi , ,v 2>和<v2, ,v j >，而這兩條路徑是前一次找到的中間點序號不大于 1 的最短路徑，將這兩條路徑長度相加就得到路徑 <vi , ,v 2, vj >的長度。將該長度與前一次中求得的從 vi 到 vj 的中間頂點序號不大于1 的最短路徑比較，

9、取其長度較短者作為當前求得的從 vi 到 vj 的中間頂點序號不大于 2 的最短路徑。依此類推直至頂點 vn 加入當前從 vi 到 vj 的最短路徑后，選出從vi 到 vj 的中間頂點序號不大于 n 的最短路徑為止。由于圖 G中頂點序號不大于 n，所以 vi 到 vj 的中間頂點序號不大于 n 的最短路徑， 已考慮了所有頂點作為中間頂點的可能性，因此，它就是vi 到 vj 的最短7路徑。五、運行與測試測試實例 1：利用如下圖所示的有向圖來測試131317761327476664242656455測試實例 2：利用下圖求交通網(wǎng)絡(luò)圖（無向圖）的最短路徑。2553北京1西安70426958124徐州

10、成都5113349鄭州56511579236813857廣州6實例 1 運行結(jié)果：上海89實例 2 運行結(jié)果：10六、總結(jié)與心得該課程設(shè)計主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡(luò)問題入手，進而利用計算機去建立一個交通咨詢系統(tǒng)，以處理和解決旅客們關(guān)心的各種問題（當然此次試驗最終主要解決的問題是：最短路徑問題）。這次試驗中我深刻的了解到了樹在計算機中的應(yīng)用是如何的神奇與靈活，對于很多的問題我們可以通過樹的相關(guān)知識來解決，特別是在解決最短路徑問題中，顯得尤為重要。經(jīng)過著次實驗， 我了解到了關(guān)于樹的有關(guān)算法，如：迪杰斯特拉算法、弗洛伊德算法等，對樹的學習有了一個更深的了解。參考文獻【 1】數(shù)據(jù)結(jié)構(gòu)嚴蔚敏

11、. 清華大學出版社 .【 2】數(shù)據(jù)結(jié)構(gòu)課程設(shè)計蘇仕華 . 極械工業(yè)出版社 .11附錄#include<stdio.h>#include<stdlib.h>#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pM

12、VNumMVNum;void CreateMGraph(MGraph * G ,int n,int e)int i,j,k,w;for(i=1;i<=n;i+)G->vexsi=(char)i;for(i=1;i<=n;i+)for(j=1;j<=n;j+)G->arcsij=Maxint;printf(" 輸入 %d 條邊的 i.j 及 w:n",e);for(k=1;k<=e;k+)scanf("%d,%d,%d",&i,&j,&w);G->arcsij=w;printf("

13、 有向圖的存儲結(jié)構(gòu)建立完畢！n");void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int v,i,w,min;enum boolean SMVNum;for(v=1;v<=n;v+)Sv=FALSE;D2v=G->arcsv1v;if(D2v<Maxint)p2v=v1;else12p2v=0;D2v1=0; Sv1=TRUE;for(i=2;i<n;i+)min=Maxint;for(w=1;w<=n;w+)if(!Sw && D2w<min)v=w;min=D2

14、w;Sv=TRUE;for(w=1;w<=n;w+)if(!Sw && (D2v+G->arcsvw<D2w)D2w=D2v+G->arcsvw;p2w=v;printf(" 路徑長度路徑 n");for(i=1;i<=n;i+)printf("%5d",D2i);printf("%5d",i);v=p2i;while(v!=0)printf("<-%d",v);v=p2v;printf("n");void Floyd(MGraph *G,in

15、t n)int i,j,k,v,w;for(i=1;i<=n;i+)for(j=1;j<=n;j+)if( G->arcsij!=Maxint)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+Dkj<Dij)13Dij=Dik+Dkj;pij=pik;void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(&q

16、uot; 輸入圖中頂點個數(shù)和邊數(shù)n,e:");scanf("%d,%d",&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf("*求城市之間最短路徑*n");printf("=n");printf("1. 求一個城市到所有城市的最短路徑n");printf("2. 求任意的兩個城市之間的最短路徑n");printf("=n");printf(" 請選擇:1 或 2，選擇 0 退出 :n");scanf("%d",&xz);if (xz=2)Floyd(G,n);printf(" 輸入源點（或起點）和終點:v,w:");scanf("%d,%d",&v,&w);k=pvw;if (k=0)printf(" 頂點 %d到%d無路徑 !n",v,w);elseprintf(" 從頂點 %d 到 %