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

上傳人:jun****875 文檔編號:23624788 上傳時間:2021-06-10 格式:DOC 頁數(shù):17 大?。?39.91KB
收藏 版權申訴 舉報 下載
《數(shù)據(jù)結構課程設計》最短路徑問題實驗報告_第1頁
第1頁 / 共17頁
《數(shù)據(jù)結構課程設計》最短路徑問題實驗報告_第2頁
第2頁 / 共17頁
《數(shù)據(jù)結構課程設計》最短路徑問題實驗報告_第3頁
第3頁 / 共17頁

下載文檔到電腦,查找使用更方便

9.9 積分

下載資源

還剩頁未讀,繼續(xù)閱讀

資源描述:

《《數(shù)據(jù)結構課程設計》最短路徑問題實驗報告》由會員分享,可在線閱讀,更多相關《《數(shù)據(jù)結構課程設計》最短路徑問題實驗報告(17頁珍藏版)》請在裝配圖網(wǎng)上搜索。

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

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

3、間的最短路徑問題。交通咨詢系統(tǒng)迪杰斯特拉算法(單源最短路徑)費洛依德算法(任意頂點對間最短路徑)建立圖的存儲結構義迪杰斯特拉算法流圖:弗洛伊德算法流圖:四、詳細設計 4.1建立圖的存儲結構定義交通圖的存儲結構。鄰接矩陣是表示圖形中頂點之間相鄰關系的矩陣。設G=(V,E)是具有n個頂點的圖,則G的鄰接矩陣是具有如下定義的n階方陣。注:一個圖的鄰接矩陣表示是唯一的!其表示需要用一個二維數(shù)組存儲頂點之間相鄰關系的鄰接矩陣并且還需要用一個具有n個元素的一維數(shù)組來存儲頂點信息(下標為i的元素存儲頂點的信息)。鄰接矩陣的存儲結構:#define MVNum 100 /最大頂點數(shù)typedef struct

4、 VertexType vexsMVNum;/頂點數(shù)組,類型假定為char型 Adjmatrix arcsMVNumMVNum;/鄰接矩陣,假定為int型MGraph;注:由于有向圖的鄰接矩陣是不對稱的,故程序運行時只需要輸入所有有向邊及其權值即可。4.2單源最短路徑單源最短路徑問題:已知有向圖(帶權),期望找出從某個源點SV到G中其余各頂點的最短路徑。迪杰斯特拉算法即按路徑長度遞增產(chǎn)生諸頂點的最短路徑算法。算法思想:設有向圖G=(V,E),其中V=1,2,n,cost是表示G的鄰接矩陣, costij表示有向邊的權。若不存在有向邊,則costij 的權為無窮大(這里取值為32767)。設S是

5、一個集合,集合中一個元素表示一個頂點,從源點到這些頂點的最短距離已經(jīng)求出。設頂點V1為源點,集合S的初態(tài)只包含頂點V1。數(shù)組dist記錄從源點到其它各頂點當前的最短距離,其初值為disti= costij,i=2,n。從S之外的頂點集合V-S中選出一個頂點w,使distw 的值最小。于是從源點到達w只通過S中的頂點,把w加入集合S中,調整dist中記錄的從源點到V-S中每個頂點v的距離:從原來的distv和distw+costwv中選擇較小的值作為新的distv。重復上述過程,直到S中包含V中其余頂點的最短路徑。 最終結果是:S記錄了從源點到該頂點存在最短路徑的頂點集合,數(shù)組dist記錄了從源

6、點到V中其余各頂點之間的最短路徑,path是最短路徑的路徑數(shù)組,其中pathi表示從源點到頂點i之間的最短路徑的前驅頂點。 4.3任意一對頂點之間的最短路徑 任意頂點對之間的最短路徑問題,是對于給定的有向網(wǎng)絡圖G=(V,E),要對G中任意一對頂點有序對,“V,W(VW)”,找出V到W的最短路徑。而要解決這個問題,可以依次把有向網(wǎng)絡圖中每個頂點作為源點,重復執(zhí)行前面的迪杰斯特拉算法n次,即可求得每對之間的最短路徑。 費洛伊德算法的基本思想:假設求從Vi到Vj的最短路徑。如果存在一條長度為arcsij的路徑,該路徑不一定是最短路徑,還需要進行n次試探。首先考慮路徑和是否存在。如果存在,則比較路徑和

7、的路徑長度,取長度較短者為當前所求得。該路徑是中間頂點序號不大于1的最短路徑。其次,考慮從vi到vj是否包含有頂點v2為中間頂點的路徑,若沒有,則說明從vi到vj的當前最短路徑就是前一步求出的;若有,那么可分解為和,而這兩條路徑是前一次找到的中間點序號不大于1的最短路徑,將這兩條路徑長度相加就得到路徑的長度。將該長度與前一次中求得的從vi到vj的中間頂點序號不大于1的最短路徑比較,取其長度較短者作為當前求得的從vi到vj的中間頂點序號不大于2的最短路徑。依此類推直至頂點vn加入當前從vi到vj的最短路徑后,選出從vi到vj的中間頂點序號不大于n的最短路徑為止。由于圖G中頂點序號不大于n,所以v

8、i到vj的中間頂點序號不大于n的最短路徑,已考慮了所有頂點作為中間頂點的可能性,因此,它就是vi到vj的最短路徑。五、運行與測試3測試實例1:利用如下圖所示的有向圖來測試131771 61747632646456262455測試實例2:利用下圖求交通網(wǎng)絡圖(無向圖)的最短路徑。2553北京西安70416952349徐州成都51181234鄭州515796512368上海13857廣州6實例1運行結果:實例2運行結果:六、總結與心得該課程設計主要是從日常生活中經(jīng)常遇到的交通網(wǎng)絡問題入手,進而利用計算機去建立一個交通咨詢系統(tǒng),以處理和解決旅客們關心的各種問題(當然此次試驗最終主要解決的問題是:最短

9、路徑問題)。這次試驗中我深刻的了解到了樹在計算機中的應用是如何的神奇與靈活,對于很多的問題我們可以通過樹的相關知識來解決,特別是在解決最短路徑問題中,顯得尤為重要。經(jīng)過著次實驗,我了解到了關于樹的有關算法,如:迪杰斯特拉算法、弗洛伊德算法等,對樹的學習有了一個更深的了解。參考文獻【1】數(shù)據(jù)結構嚴蔚敏.清華大學出版社.【2】數(shù)據(jù)結構課程設計蘇仕華.極械工業(yè)出版社.附錄#include#include#define MVNum 100#define Maxint 32767enum booleanFALSE,TRUE;typedef char VertexType;typedef int Adjm

10、atrix;typedef structVertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;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(有向圖的存儲結構建立完畢!n)

11、;void Dijkstra(MGraph *G,int v1,int n)int D2MVNum,p2MVNum;int 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+)print

12、f(%5d,D2i);printf(%5d,i);v=p2i;while(v!=0)printf(-%d,v);v=p2v;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;in

13、t xz=1;G=(MGraph *)malloc(sizeof(MGraph);printf(輸入圖中頂點個數(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 到 %d 最短路徑路徑是:%d,v,w,v);while (k!=w)printf(-%d,k);k=pkw;printf(-%d,w);printf(徑路長度:%dn,Dvw);else if(xz=1)printf(求單源路徑,輸入源點v :);scanf(%d,&v);Dijkstra(G,v,n);printf(結束求最短路徑,再見!n);

展開閱讀全文
溫馨提示:
1: 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
4. 未經(jīng)權益所有人同意不得將文件中的內容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
6. 下載文件中如有侵權或不適當內容,請與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

相關資源

更多
正為您匹配相似的精品文檔
關于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內容的表現(xiàn)方式做保護處理,對上載內容本身不做任何修改或編輯。若文檔所含內容侵犯了您的版權或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!