課程設(shè)計 單源點(diǎn)最短路徑算法的實現(xiàn)

1、數(shù)據(jù)結(jié)構(gòu)課程設(shè)計設(shè)計說明書單源點(diǎn)最短路徑算法的實現(xiàn)學(xué)生姓名學(xué)號班級成績指導(dǎo)教師數(shù)學(xué)與計算機(jī)科學(xué)學(xué)院2015年 1 月 2 日 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計評閱書題 目單源點(diǎn)最短路徑算法的實現(xiàn)學(xué)生姓名學(xué) 號指導(dǎo)教師評語及成績成 績： 教師簽名： 年 月 日教研室意見總成績： 室主任簽名： 年 月 日課程設(shè)計任務(wù)書20142015學(xué)年第1學(xué)期專業(yè)： 學(xué)號： 姓名： 課程設(shè)計名稱： 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 設(shè) 計 題 目： 單源點(diǎn)最短路徑算法的實現(xiàn) 完 成 期 限：自 2014 年 12 月 22 日至 2015 年 1 月 2 日共 2 周設(shè)計內(nèi)容及要求:最短路徑問題已經(jīng)被應(yīng)用到GIS、GPS等信息管理系統(tǒng)中，為

2、人們生活帶來了很大便利。它屬于圖結(jié)構(gòu)問題，其解決方法也有不少（如Dijkstra、 A-star）。單源點(diǎn)最短路徑問題解決的是既定起點(diǎn)的情況下，尋求該點(diǎn)到圖中其它頂點(diǎn)的最短路徑。請用C/C+語言的結(jié)構(gòu)體、指針、數(shù)據(jù)結(jié)構(gòu)等基礎(chǔ)知識，編寫程序?qū)崿F(xiàn)圖的結(jié)構(gòu)定義、圖的存儲，以及求解單源點(diǎn)最短路徑。設(shè)計過程以及寫作要求如下：（1）要針對本題目，認(rèn)真研究所設(shè)計的內(nèi)容，用簡明扼要的語言描述課題，給出課題的基本內(nèi)容及要求；（2）根據(jù)數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識給出實現(xiàn)建立任意m個頂點(diǎn)n條邊的圖算法、按照用戶給定的源點(diǎn)和目標(biāo)點(diǎn)，求出它們間的最短路徑（打印出來）算法的基本策略及思路；（3）給出較為詳盡數(shù)據(jù)結(jié)構(gòu)與算法，算法可

3、以用流程圖、偽代碼等描述手段進(jìn)行描述；（4）給出一個完整的算法實現(xiàn)的C/C+程序，算法中的各子算法要力求用函數(shù)來實現(xiàn)；（5）對編寫的程序要進(jìn)行詳盡的測試分析；（6）對本課題的設(shè)計工作要進(jìn)行一個完整深刻的總結(jié)。最終設(shè)計成果形式為：1、 設(shè)計軟件一套；2、 撰寫一份課程設(shè)計說明書一份，打印并裝訂成冊。指導(dǎo)教師（簽字）： 教研室主任（簽字）： 批準(zhǔn)日期： 年 月 日摘要 本系統(tǒng)以VC+作為軟件開發(fā)環(huán)境，C語言作為程序開發(fā)語言，鄰接矩陣作為存儲結(jié)構(gòu)，設(shè)計與實現(xiàn)了最短路徑運(yùn)算。該系統(tǒng)實現(xiàn)了有向圖的存儲、最短路徑的運(yùn)算等主要功能。依照該系統(tǒng)可以解決生活中許多問題，比如交通路線的選擇，工程時間的預(yù)算等等，讓

4、人們可以做出合理的選擇。本系統(tǒng)通過分析課題的背景、意義、要求，分別從課題描述、邏輯設(shè)計、算法設(shè)計、調(diào)試與測試等各個方面詳細(xì)介紹了系統(tǒng)的設(shè)計與實現(xiàn)過程，最后對系統(tǒng)的完成情況進(jìn)行了總結(jié)。界面清晰，操作簡單，易于用戶接受。關(guān)鍵詞：VC+;鄰接矩陣; 最短路徑目 錄1課題描述12 問題分析與任務(wù)定義22.1問題分析22.2任務(wù)定義23 算法設(shè)計33.1 圖的鄰接矩陣的存儲結(jié)構(gòu)33.2 Dijkstra算法思想44 系統(tǒng)邏輯設(shè)計54.1 主函數(shù)流程圖如圖4.1所示54.2 Create函數(shù)流程圖如圖4.2所示64.3 Dijkstra函數(shù)流程圖如圖4.3所示 85 源代碼116 調(diào)試與測試146.1合法

5、數(shù)據(jù)輸入146.2非法數(shù)據(jù)輸入15總結(jié)16參考文獻(xiàn)171課題描述乘車旅行的人大多數(shù)都希望找出到目的地盡可能短，花費(fèi)少的行程，那么如何找出從出發(fā)點(diǎn)到目的地的最短路徑？由于路徑比較多，所以用手工計算起來比較復(fù)雜，抽象，因此人們用計算機(jī)語言代替手工計算來求得最短路徑。而在計算機(jī)語言中迪杰斯拉算法比較常用，簡捷，故人們經(jīng)常借助計算機(jī)程序用迪杰斯拉算法求得單源點(diǎn)的最短路徑，這樣可以廣泛的提高效率，而且條理清晰，通俗易懂。02 問題分析與任務(wù)定義2.1問題分析 本系統(tǒng)是要解決的是單源點(diǎn)最短路徑問題，設(shè)計程序，實現(xiàn)最短路徑的求法，系統(tǒng)需要達(dá)到的主要功能如下：(1) 編寫算法能夠建立帶權(quán)圖，并能夠用Dijks

6、tra算法求該圖的最短路徑。(2) 能夠選擇圖上的任意一頂點(diǎn)做為開始節(jié)點(diǎn)。最短路徑輸出不必采用圖形方式，可頂點(diǎn)序列方式輸出。(3) 根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。兩個子模塊相互獨(dú)立，沒有嵌套調(diào)用的情況，在主模塊中調(diào)用上面兩個子模塊。2.2任務(wù)定義 根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。兩個子模塊相互獨(dú)立，沒有嵌套調(diào)用的情況，在主模塊中調(diào)用上面兩個子模塊以下是三個模塊的大體分析：(1) 建立有向圖的存儲結(jié)構(gòu)。(2) 應(yīng)用Dijkstra算法求出該有向圖的最短路徑。(3) 在主函數(shù)中調(diào)用兩個子函數(shù)，完成最短路徑的程序設(shè)。13 算法設(shè)計3.1 圖的鄰接矩陣的存儲結(jié)構(gòu)一個圖的鄰接矩

7、陣表示唯一的。故在圖的鄰接矩陣表示中，除了需要用一個二維數(shù)組存儲頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個具有n個元素的一維數(shù)組存儲頂點(diǎn)信息，其中下標(biāo)為i的元素存儲頂點(diǎn)vi的信息。本設(shè)計是基于類C語言的算法描述，因此，圖的鄰接矩陣的存儲結(jié)構(gòu)定義如下:#define MVNum 50typedef struct VertexType vexsMVNum; Adjmatrix arcsMVNumMVNum；Mgraph;在本系統(tǒng)中，以鄰接矩陣存儲有向圖，如圖3.1a中有向圖G所示，其鄰接矩陣為圖 3.1b所示： 圖3.1b G的鄰接矩陣 10 30 100 5 50 10 20 60 bae

8、f550圖3.1a 有向圖G圖3.1b G的鄰接矩陣 10 30 100 5 50 10 20 60 圖3.1b G的鄰接矩陣圖3.1a 有向圖G505feabcd1006030 2010103.2 Dijkstra算法思想（1）Dijkstra算法核心是貪心，實質(zhì)是按路徑長度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算法。用自然語言描述如下：初始化S和D,置空最短路 徑終點(diǎn)集，置初始的最短路徑值；Sv1=TRUE;Dv1=0;While(S集中的頂點(diǎn)數(shù)<n) 開始循環(huán)，每次求的v1到某個v頂點(diǎn)的最短路徑，并將v加到S集中; Sv=TRUE; 更新當(dāng)前最短路徑及距離。（2）Dijkstra算法結(jié)束后，通過

9、設(shè)置一個數(shù)組記錄下一個節(jié)點(diǎn)的前趨節(jié)點(diǎn)，然后通過倒敘的方式輸出該最短路徑。4 系統(tǒng)邏輯設(shè)計4.1 主函數(shù)流程圖如圖4.1所示開始輸入頂點(diǎn)個數(shù)和邊數(shù)m,n開始輸入數(shù)據(jù)調(diào)用Create函數(shù)建立圖的鄰接矩陣調(diào)用Create函數(shù)N調(diào)用Dijkstra函數(shù)Y3.1主函數(shù)流程圖請輸入初始點(diǎn)v4.2 Create函數(shù)流程圖調(diào)用Dijkstra函數(shù)求得最短路徑k=1 結(jié)束圖4.1 主函數(shù)流程圖4.2 Create函數(shù)流程圖如圖4.2所示開始定義頂點(diǎn)序號i=1，頂點(diǎn)數(shù)m,邊數(shù)nNi<=mY存入一維向量G.vexsi=ii=i+1i=1Ni<=mYi=i+1j=1Nj<=mY 10 30 100

10、5 50 10 20 60 對鄰接矩陣m*m個單元初始化G.arcsij=Maxintj=j+1接下一頁接上一頁 N變量k=1k<=nY定位i,ji=a-a+1 , j=b-a+1G->arcsij=w給鄰接矩陣有關(guān)單元賦權(quán)值wG.arcsij=wk=k+1 結(jié)束圖4.2 Create函數(shù)流程圖4.3 Dijkstra函數(shù)流程圖如圖4.3所示 開始定義G中v1到其余頂點(diǎn)v的最短路徑、帶權(quán)長度及最短路徑終點(diǎn)的集合int DMVNum, PMVNum boolean SMVNum 定義頂點(diǎn)數(shù) int mv=1Nv<=mY置空S Sv=FALSE Dv=G.arcsv1vN若權(quán)值小

11、于最大值 無窮Dv<MaxintYPv=0Pv=v1v=v+1初始化，v1頂點(diǎn)屬于s集Dv1=0;Sv1=TRUE 開始主循環(huán)，每次求得v1到某個v頂點(diǎn)的最短路徑，并加v到s集i=2接下一頁接上一頁Ni<=mmmmY當(dāng)前所知離v1頂點(diǎn)的最近距離min=Maxint 頂點(diǎn)變量w=1Nw<=m、YN!Sw&&Dw<minYv=w W頂點(diǎn)離v1更近min=D wSv=TRUEw=w+1w=1Nw<=mYSv=TRUEN!Sw&&Dv+G.arcsvw<DwY修改Dw,Pw Dw=Dv+G.arcsvwPw=vw=w+1i=i+1接下

12、一頁接上一頁、i=1Ni<=mmmmY輸出數(shù)據(jù)pvi=i+1結(jié)束圖4.3 Dijkstra函數(shù)流程圖 5 源代碼#include<stdio.h>#include<stdlib.h>#define MVNum 50#define Maxint 1111typedef char VertexType; / 定義頂點(diǎn)typedef int Adjmatrix; typedef enum FALSE,TRUEboolean;typedef struct / 圖的鄰接矩陣VertexType vexsMVNum; /頂點(diǎn)向量 存放頂點(diǎn)的一維數(shù)組Adjmatrix arcs

13、MVNumMVNum; / 鄰接矩陣二維數(shù)組MGraph; /定義鄰接矩陣結(jié)構(gòu)類型void CreateMGraph(MGraph *G,int m,int n) / 采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖Gint i,j,k,w;char a,b;for(i=1;i<=m;i+) /構(gòu)造頂點(diǎn)向量G->vexsi=i;for(i=1;i<=m;i+) /初始化鄰接矩陣for(j=1;j<=m;j+)G->arcsij=Maxint;printf("輸入%d條邊的i,j及w:n",n);for(k=1;k<=n;k+) / 構(gòu)造鄰接矩陣fflu

14、sh(stdin);scanf("%c,%c,%d",&a,&b,&w); /輸入一條邊依附的頂點(diǎn)及權(quán)值i=a-'a'+1;j=b-'a'+1; G->arcsij=w; /弧<i,j>的權(quán)值printf("有向圖的存儲結(jié)構(gòu)建立完成!n");printf("*n"); void Dijkstra(MGraph G,int v1,int m)/用Dijkstra算法求G中v1頂點(diǎn)到其余頂點(diǎn)v的最短路徑pv及帶權(quán)長度Dvint DMVNum,PMVNum;int v

15、,i,w,min;boolean SMVNum;/ S以求得最短路徑的終點(diǎn)的集合for(v=1;v<=m;v+)Sv=FALSE;Dv=G.arcsv1v;if(Dv<Maxint)Pv=v1;elsePv=0;Dv1=0;Sv1=TRUE; / 初始化，v1頂點(diǎn)屬于s集 /開始主循環(huán)，每次求得v1到某個v頂點(diǎn)的最短路徑，并加v到s集for(i=2;i<=m;i+) / 其余n-1個頂點(diǎn)min=Maxint; /當(dāng)前所知離v1頂點(diǎn)的最近距離for(w=1;w<=m;w+)if(!Sw&&Dw<min) / w頂點(diǎn)在v-s中v=w;min=Dw; /

16、w頂點(diǎn)離v1頂點(diǎn)更近Sv=TRUE;for(w=1;w<=m;w+) /更新當(dāng)前最短路徑及距離if(!Sw&&(Dv+G.arcsvw<Dw) / 修改Dw和Pw,w屬于v-sDw=Dv+G.arcsvw;Pw=v;printf("路徑長度-路徑n");for(i=1;i<=m;i+)printf("%5d",Di); printf("%12c",i-1+'a');v=Pi;while(v!=0)printf("<-%c",v-1+'a');v

17、=Pv;printf("n"); void main() MGraph G;int m,n,v;char ch;printf("輸入所需圖的頂點(diǎn)個數(shù)和邊數(shù)m,n:");scanf("%d,%d",&m,&n);CreateMGraph(&G,m,n); while (v<=m) printf("求最短路徑，請輸入初始點(diǎn)v:");fflush(stdin);scanf("%c",&ch);printf("n");v=ch-'a

18、9;+1;Dijkstra(G,v,m); 6 調(diào)試與測試6.1合法數(shù)據(jù)輸入（1）合法數(shù)據(jù)測試結(jié)果如圖6.1所示圖6.1合法數(shù)據(jù)測試結(jié)果6.2非法數(shù)據(jù)輸入（2）非法數(shù)據(jù)測試結(jié)果如圖6.2所示圖6.2非法數(shù)據(jù)測試結(jié)果當(dāng)前任務(wù)已達(dá)到任務(wù)目標(biāo)，對于n個頂點(diǎn)的有向圖，求一個頂點(diǎn)到其他頂點(diǎn)的最短路徑的時間為O(n)，調(diào)整最短路徑的循環(huán)共執(zhí)行n-1次，所以，時間復(fù)雜度是O（n2）。采用鄰接矩陣存儲有向圖，應(yīng)處理每兩個頂點(diǎn)之間的關(guān)系，所以空間復(fù)雜度為O（n2）?？偨Y(jié)本次課程設(shè)計涉及到的范圍很廣，讓我比較系統(tǒng)的對C語言和數(shù)據(jù)結(jié)構(gòu)知識進(jìn)行了一次整理和復(fù)習(xí)。本系統(tǒng)存在的問題主要是程序完成后，調(diào)試時沒有發(fā)現(xiàn)問題，但是當(dāng)輸入開始節(jié)點(diǎn)后，運(yùn)行框卻不停的出現(xiàn)”<-a”,后來重新檢查程序時發(fā)現(xiàn)for循環(huán)的括號后面多了一個“;”，去掉該分號之后，程序可以運(yùn)行。在這次課程設(shè)計中我體會到C語言超強(qiáng)的邏輯性以及能夠熟練使用VC+編譯環(huán)境的重要性，對C語言與數(shù)據(jù)結(jié)構(gòu)這兩門課程有了新的認(rèn)識，它們既有聯(lián)系，又相互區(qū)別，在編寫程序過程中要靈活應(yīng)用。我對數(shù)據(jù)結(jié)構(gòu)的理解還有待加強(qiáng)，這次課程設(shè)計應(yīng)用的算法是Dijkstra算法。在學(xué)習(xí)的過程中自己對這方面的知識比較生疏，所以在算法設(shè)計過程中比較困難，尤其是設(shè)計Dij