1、數 據 結 構設計說明書單源點最短路徑算法的實現學生姓名 王文剛 學 號 1418064056 班 級 網絡1402 成 績 指導教師 數學與計算機科學學院年 月 日 課程設計任務書20 20 學年第 學期課程設計名稱： 數據結構課程設計 課程設計題目： 單源點最短路徑算法的實現 完 成 期 限：自 年 月 日至 年 月 日共 2 周設計內容：1.任務說明2.要求3.參考資料指導教師： 教研室負責人：課程設計評閱評語： 指導教師簽名： 年 月 日摘 要設計了一求解最短路徑的方法，該方法具有在輸入的途中查找兩個頂點之間的最短路徑的功能。本方法采用VC+作為軟件開發環境，采用Dijkstar函數來

2、求取頂點之間的最短路徑。，用戶可以自己輸入各個地點及其之間的距離，便于用戶在不同情況下均可使用。關鍵詞：最短路徑；Dijkstar；無向圖;目 錄目錄1課題描述22 需求分析33概要設計43.1 存儲結構43.2 算法描述54詳細設計64.1 功能模塊圖64.2 主函數64.3 pd函數74.4 CreateMGraph函數84.5Dijkstar函數95程序編碼116程序的調試與測試158總結16參考文獻171.目錄中可以只有一級標題2.頁碼右側對齊頁邊距3.本頁不需要頁碼4.以上內容僅作參考，具體章節由課程設計類型確定1課題描述 隨著交通的發展，人民生活水平的提高。出門旅行變的越來越頻繁，

3、而且供暖也成為冬天不可或缺的內容。為了節約時間和金錢，所以人們都希望找到旅行目的地的最短路徑和架設暖氣的最短路徑。那么如何找到最短路徑呢？由于路徑較多，手工計算比較麻煩，而且容易出錯，因此人們用計算機語言代替手工計算求最短路徑。而在計算機語言中迪杰斯特拉算法比較常見，簡潔，故人們常借助計算機程序迪杰斯特拉算法求最短路徑。這樣可以廣泛提高效率，容易理解。2 需求分析3概要設計3.1 存儲結構一個圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需要用一個二維數組存儲頂點之間相鄰關系的鄰接矩陣外，通常還需要使用一個具有n個元素的一維數組存儲頂點信息，其中下標為i的元素存儲頂點vi的信息。因此，圖的鄰

4、接矩陣的存儲結構定義如下:#define MVNum 50typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum；Mgraph; 圖如下dacbeF 圖3.1 無向圖a b c d e fa 3 4 b 3 15 5 c 4 3 12 d 15 3 8e 5 12 6f 8 6 圖2.1 G的鄰結矩陣3.2 算法描述(1) Dijkstra算法核心是貪心，實質是按路徑長度遞增產生諸頂點的最短路徑算法。迪杰斯特拉算法可用自然語言描述如下：初始化S和D,置空最短路徑終點集，置初始的最短路徑值；Sv1=TRUE;Dv1=0;Whil

5、e(S集中的頂點數<n) 開始循環，每次求的v1到某個v頂點的最短路徑，并將v加到S集中; Sv=TRUE; 更新當前最短路徑及距離。(2)Dijkstra算法結束后，通過設置一個數組記錄下一個節點的前趨節點，然后通過倒敘的方式輸出該最短路徑。(3)Dijkstra算法思想為：設G=(V,E)，G是帶權無向圖，V代表圖中頂點集合，E代表圖中含權重的邊集合。將全部頂點集合V分成兩組，第一組為已求出最短路徑的頂點集合，用S表示（初始時S中只有一個源點，以后每求得一條最短路徑，就將該路徑的終點加入到集合S中）；第二組為其余待確定最短路徑的頂點集合，用U表示。按最短路徑長度的遞增次序依次把U集合

6、的頂點逐個加入到S集合中，約束條件是保持從源點v到S中各頂點的最短路徑長度不大于從源點v到U中任何頂點的最短路徑長度。算法的終止條件是集合U為空集，即集合U的頂點全部加入到集合S中。（4）Maxint：最大整數值，表示兩個不能到達的頂點。4詳細設計4.1 功能模塊圖 如圖4.1所示求最短路徑 Main函數Pd函數CreateMGraph函數圖4.1功能模塊4.2 主函數 主函數流程圖如圖4.2開始 調用pd函數調用CreateMGraph函數調用Dijkstar函數 圖4.2 主函數4.3 pd函數函數如圖4.3所示開始輸入n，e（n是頂點數，e是邊數）Nn>0&&e&l

7、t;=n(n-1)/2Y結束圖4.3 Pd函數4.4 CreateMGraph函數createMGraph函數如圖4.4所示開始i=1i<=nNYG->vexsi=ii=i+1i=1Ni<=nYi=i+1j=1 Nj<=nYG->arcsij=Maxint G->arcsji=Maxint無向圖a<=>bj=j+1k=1Nj<=nYG->arcsij=Maxint，G->arcsji=Maxint無向圖a<=>b開始k=k+1圖4.4 createMGraph函數4.5Dijkstar函數 開始v1到其余頂點集合v最

8、短路徑,帶權長度 DMVnum,PMVnumv=1Nv<=nY置空s Sv=FALSE,D2v=G.arcsv1v若權值小與最大值D2v<Maxint NYPv=0Pv=v1v=v+1初始化，v1頂點屬于s集D2v1=0:sv1開始主循環，每次求得v1到某個v頂點的最短路徑，并加到s中v=w,min=D2w if(!Sw&&D2w<min)Ni<=nY當前所知離v1頂點最近距離min=Maxint頂點變量 w=1Nw<=nYN!Sw&&D2w<min Yv=w w頂點離v1更近Sv=TRUE;w=1w=w+1Nw<=nY

9、(!Sw&&(D2v+G.arcsvw<D2w)N修改D2w，P2wD2w=D2v+G.arcsvw;P2w=vw=w+1i=i+1i=1i<=mY輸出數據i=i+1結束5程序編碼#include<stdio.h> #include<stdlib.h> #define MVNum 100 #define Maxint 32767 typedef char VertexType; typedef int Adjmatrix; typedef enum FALSE,TRUEboolean; typedef struct VertexType ve

10、xsMVNum; Adjmatrix arcsMVNumMVNum; MGraph; int D1MVNum,P1MVNum; int DMVNumMVNum,PMVNumMVNum; int pd(MGraph *G,int &n,int &e) while(n>0)&&(e>n*(n-1)/2)printf("你輸入的頂點或邊數不正確，請重新圖中頂點個數和邊數n，e:");scanf("%d,%d",&n,&e); return TRUE; CreateMGraph(MGraph *G,in

11、t n,int e) int i,j,k,w; char a,b; for(i=1;i<=n;i+) G->vexsi=i; for(i=1;i<=n;i+) for(j=1;j<=n;j+) G->arcsij=Maxint; G->arcsji=Maxint; printf("輸入%d條邊的i,j及w:n",e);for(k=1;k<=e;k+) fflush(stdin); scanf(" %c,%c,%d",&a,&b,&w); i=a-'a'+1; j=b-

12、9;a'+1; G->arcsij=w; G->arcsji=w; printf("無向圖的存儲結構建立完畢!n"); void Dijkstra(MGraph G,int v1,int n) int D2MVNum,P2MVNum; int v,i,w,min; boolean SMVNum; / 判斷該點是否到過S中，即該點是否被遍歷 for(v=1;v<=n;v+) Sv=FALSE; D2v=G.arcsv1v; if(D2v<Maxint) P2v=v1; else P2v=0; D2v1=0;Sv1=TRUE; for(i=2;i

13、<=n;i+) min=Maxint; for(w=1;w<=n;w+) if(!Sw&&D2w<min) v=w;min=D2w; 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("%14c",i-1+'a');v=P2

14、i; while(v!=0) printf("<-%c",v-1+'a'); v=P2v; printf("n"); void main() MGraph G; int n,e,v; char ch; printf("輸入圖中頂點個數和邊數n，e:"); scanf("%d,%d",&n,&e); pd(&G,n,e);/scanf("%d,%d",&n,&e);/n=r;/e=a;CreateMGraph(&G,n,e);

15、while(1) printf("求最短路徑，輸入開始點v:"); fflush(stdin); scanf("%c",&ch); v=ch-'a'+1; Dijkstra(G,v,n); 6程序的調試與測試調試如圖6.1所示 輸入：2,5a,b,5a,c,15 b,c,6 b,d,2 c,d,10a b 圖6.17總結本次課程設計涉及到的范圍很廣，讓我能夠比較系統的對C語言和數據結構進行一次整理和復習。同時有了很多的體會和經驗。在這次課程設計中我體會到C語言超強的邏輯性，能夠熟練使用的編譯環境，也對這兩門課程有了新的認識，他們既有聯系，又相互區別，在編寫程序過程中要靈活應用。一開始信息是不能重復查詢也就是說，整個設計過程中，遇到了很多問題，例如查詢一次后退出重新運行才可以不能連續查詢后來添加了一個簡單的while()語句就實現了二次查詢這次“求解最優路徑”的課題，讓我明白很多不知道的知識內容，對求解最優路徑有了進一步的了解和認識。最后感謝老師布置給我們的任務，我會更加努力的學好這方面的知識，編寫出更有價值的程序。最短路徑算法關鍵先把已知最短路徑頂點集 (只有一個源點