《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問題實(shí)驗(yàn)報(bào)告材料

《《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問題實(shí)驗(yàn)報(bào)告材料》由會(huì)員分享，可在線閱讀，更多相關(guān)《《大數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)》最短路徑問題實(shí)驗(yàn)報(bào)告材料（16頁珍藏版）》請?jiān)谘b配圖網(wǎng)上搜索。

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

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

3、任意頂點(diǎn)對間最短路徑建立圖的存儲(chǔ)結(jié)構(gòu)義迪杰斯特拉算法流圖：弗洛伊德算法流圖：四、詳細(xì)設(shè)計(jì)建立圖的存儲(chǔ)結(jié)構(gòu)定義交通圖的存儲(chǔ)結(jié)構(gòu)。鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個(gè)頂點(diǎn)的圖，如此G的鄰接矩陣是具有如下定義的n階方陣。注：一個(gè)圖的鄰接矩陣表示是唯一的！其表示需要用一個(gè)二維數(shù)組存儲(chǔ)頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣并且還需要用一個(gè)具有n個(gè)元素的一維數(shù)組來存儲(chǔ)頂點(diǎn)信息下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)的信息。鄰接矩陣的存儲(chǔ)結(jié)構(gòu)：#define MVNum 100 /最大頂點(diǎn)數(shù)typedef struct VertexType vexsMVNum;/頂點(diǎn)數(shù)組，類型假定為char型 Adjm

4、atrix arcsMVNumMVNum;/鄰接矩陣，假定為int型MGraph;注：由于有向圖的鄰接矩陣是不對稱的，故程序運(yùn)行時(shí)只需要輸入所有有向邊與其權(quán)值即可。單源最短路徑單源最短路徑問題：有向圖(帶權(quán))，期望找出從某個(gè)源點(diǎn)SV到G中其余各頂點(diǎn)的最短路徑。迪杰斯特拉算法即按路徑長度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算法。算法思想：設(shè)有向圖G=(V,E)，其中V=1,2，n，cost是表示G的鄰接矩陣，costij表示有向邊的權(quán)。假如不存在有向邊，如此costij 的權(quán)為無窮大這里取值為32767。設(shè)S是一個(gè)集合，集合中一個(gè)元素表示一個(gè)頂點(diǎn)，從源點(diǎn)到這些頂點(diǎn)的最短距離已經(jīng)求出。設(shè)頂點(diǎn)V1為源點(diǎn)，集合S

5、的初態(tài)只包含頂點(diǎn)V1。數(shù)組dist記錄從源點(diǎn)到其它各頂點(diǎn)當(dāng)前的最短距離，其初值為disti= costij，i=2，n。從S之外的頂點(diǎn)集合V-S中選出一個(gè)頂點(diǎn)w，使distw 的值最小。于是從源點(diǎn)到達(dá)w只通過S中的頂點(diǎn)，把w參加集合S中，調(diào)整dist中記錄的從源點(diǎn)到V-S中每個(gè)頂點(diǎn)v的距離：從原來的distv和distw+costwv中選擇較小的值作為新的distv。重復(fù)上述過程，直到S中包含V中其余頂點(diǎn)的最短路徑。 最終結(jié)果是：S記錄了從源點(diǎn)到該頂點(diǎn)存在最短路徑的頂點(diǎn)集合，數(shù)組dist記錄了從源點(diǎn)到V中其余各頂點(diǎn)之間的最短路徑，path是最短路徑的路徑數(shù)組，其中pathi表示從源點(diǎn)到頂點(diǎn)i之

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

7、含有頂點(diǎn)v2為中間頂點(diǎn)的路徑，假如沒有，如此說明從vi到vj的當(dāng)前最短路徑就是前一步求出的；假如有，那么可分解為和，而這兩條路徑是前一次找到的中間點(diǎn)序號(hào)不大于1的最短路徑，將這兩條路徑長度相加就得到路徑的長度。將該長度與前一次中求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于1的最短路徑比擬，取其長度較短者作為當(dāng)前求得的從vi到vj的中間頂點(diǎn)序號(hào)不大于2的最短路徑。依此類推直至頂點(diǎn)vn參加當(dāng)前從vi到vj的最短路徑后，選出從vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑為止。由于圖G中頂點(diǎn)序號(hào)不大于n，所以vi到vj的中間頂點(diǎn)序號(hào)不大于n的最短路徑，已考慮了所有頂點(diǎn)作為中間頂點(diǎn)的可能性，因此，它就是vi到v

8、j的最短路徑。五、運(yùn)行與測試3測試實(shí)例1：利用如如下圖所示的有向圖來測試13177161747632646456262455測試實(shí)例2：利用如下圖求交通網(wǎng)絡(luò)圖無向圖的最短路徑。2553某某70416952349某某某某51181234某某515796512368某某13857某某6實(shí)例1運(yùn)行結(jié)果：實(shí)例2運(yùn)行結(jié)果：六、總結(jié)與心得該課程設(shè)計(jì)主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡(luò)問題入手，進(jìn)而利用計(jì)算機(jī)去建立一個(gè)交通咨詢系統(tǒng)，以處理和解決旅客們關(guān)心的各種問題當(dāng)然此次試驗(yàn)最終主要解決的問題是：最短路徑問題。這次試驗(yàn)中我深刻的了解到了樹在計(jì)算機(jī)中的應(yīng)用是如何的神奇與靈活，對于很多的問題我們可以通過樹的相關(guān)

9、知識(shí)來解決，特別是在解決最短路徑問題中，顯得尤為重要。經(jīng)過著次實(shí)驗(yàn)，我了解到了關(guān)于樹的有關(guān)算法，如：迪杰斯特拉算法、弗洛伊德算法等，對樹的學(xué)習(xí)有了一個(gè)更深的了解。參考文獻(xiàn)【1】數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏.清華大學(xué).【2】數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)蘇仕華.極械工業(yè).附錄#include#include#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjmatrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumM

10、VNum;MGraph;int D1MVNum,p1MVNum;int DMVNumMVNum,pMVNumMVNum;void CreateMGraph(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=Maxint;printf(輸入%d條邊的i.j與w:n,e);for(k=1;karcsij=w;printf(有向圖的存儲(chǔ)結(jié)構(gòu)建立完畢！n);void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int

11、 v,i,w,min;enum boolean SMVNum;for(v=1;varcsv1v; if(D2vMaxint) p2v=v1;else p2v=0;D2v1=0; Sv1=TRUE;for(i=2;in;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw & D2wmin)v=w;min=D2w;Sv=TRUE;for(w=1;warcsvwarcsvw;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

12、;printf(n);void Floyd(MGraph *G,int n)int i,j,k,v,w;for(i=1;i=n;i+)for(j=1;jarcsij!=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+DkjDij) Dij=Dik+Dkj;pij=pik;void main()MGraph *G;int m,n,e,v,w,k;int xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,

13、e:);scanf(%d,%d,&n,&e);CreateMGraph(G,n,e);while(xz!=0)printf(*求城市之間最短路徑*n);printf(=n);printf(1.求一個(gè)城市到所有城市的最短路徑n);printf(2.求任意的兩個(gè)城市之間的最短路徑n);printf(=n);printf(請選擇 :1或2，選擇0退出:n);scanf(%d,&xz);if (xz=2)Floyd(G,n);printf(輸入源點(diǎn)或起點(diǎn)和終點(diǎn):v,w:);scanf(%d,%d,&v,&w);k=pvw;if (k=0)printf(頂點(diǎn)%d 到 %d 無路徑!n,v,w);elseprintf(從頂點(diǎn)%d 到 %d 最短路徑路徑是:%d,v,w,v);while (k!=w)printf(-%d,k);k=pkw;printf(-%d,w);printf(徑路長度:%dn,Dvw);else if(xz=1)printf(求單源路徑，輸入源點(diǎn)v:);scanf(%d,&v);Dijkstra(G,v,n);printf(完畢求最短路徑，再見!n);