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

1、<p><b>　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)</b></p><p><b>　　設(shè)計(jì)說明書</b></p><p>　　數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院</p><p>　　2014年3月7日 </p><p>　單元點(diǎn)最短路徑算法的實(shí)現(xiàn) </p><p><b>　　

2、課程設(shè)計(jì)任務(wù)書</b></p><p>　　2013—2014學(xué)年第2 學(xué)期</p><p>　　專業(yè)： 學(xué)號： 姓名： </p><p>　　課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) </p><p>　　設(shè)計(jì)題目：

3、 單源點(diǎn)最短路徑算法的實(shí)現(xiàn) </p><p>　　完成期限：自 2014 年 2 月24 日至 2014 年3 月 7 日共 2 周</p><p>　　設(shè)計(jì)依據(jù)、要求及主要內(nèi)容（可另加附頁）：</p><p>　　最短路徑問題是數(shù)據(jù)結(jié)構(gòu)中數(shù)組部分的重點(diǎn)和難點(diǎn)知識。它屬于圖結(jié)構(gòu)問題，其解決方

4、法也有不少（如Dijkstra、 A-star），可自行選擇算法。本課程設(shè)計(jì)按以下的要求運(yùn)用C/ C++結(jié)構(gòu)體、指針、數(shù)據(jù)結(jié)構(gòu)等基知識編程實(shí)現(xiàn)。</p><p>　　任務(wù)要求：1）闡述設(shè)計(jì)思想,畫出流程圖;2）任意建立存儲m個頂點(diǎn)n條邊的圖；3）按照用戶要求的源點(diǎn)和目標(biāo)點(diǎn)，求出它們間的最短路徑，并打印出路徑，若無路徑需給出說明；4）說明測試方法,寫出完整的運(yùn)行結(jié)果,較好的界面設(shè)計(jì)；5）按照格式要求完成課程設(shè)計(jì)說明

5、書。</p><p><b>　　設(shè)計(jì)要求:</b></p><p>　　1）問題分析和任務(wù)定義：根據(jù)設(shè)計(jì)題目的要求，充分地分析和理解問題，明確問題要求做什么？（而不是怎么做？）限制條件是什么？確定問題的輸入數(shù)據(jù)集合。</p><p>　　2）邏輯設(shè)計(jì)：對問題描述中涉及的操作對象定義相應(yīng)的數(shù)據(jù)類型，并按照以數(shù)據(jù)結(jié)構(gòu)為中心的原則劃分模塊，定義主程

6、序模塊和各抽象數(shù)據(jù)類型。邏輯設(shè)計(jì)的結(jié)果應(yīng)寫出每個抽象數(shù)據(jù)類型的定義（包括數(shù)據(jù)結(jié)構(gòu)的描述和每個基本操作的功能說明），各個主要模塊的算法，并畫出模塊之間的調(diào)用關(guān)系圖；</p><p>　　3）詳細(xì)設(shè)計(jì)：定義相應(yīng)的存儲結(jié)構(gòu)并寫出各函數(shù)的偽碼算法。在這個過程中，要綜合考慮系統(tǒng)功能，使得系統(tǒng)結(jié)構(gòu)清晰、合理、簡單和易于調(diào)試，抽象數(shù)據(jù)類型的實(shí)現(xiàn)盡可能做到數(shù)據(jù)封裝，基本操作的規(guī)格說明盡可能明確具體。詳細(xì)設(shè)計(jì)的結(jié)果是對數(shù)據(jù)結(jié)構(gòu)和基

7、本操作做出進(jìn)一步的求精，寫出數(shù)據(jù)存儲結(jié)構(gòu)的類型定義，寫出函數(shù)形式的算法框架；</p><p>　　4）程序編碼：把詳細(xì)設(shè)計(jì)的結(jié)果進(jìn)一步求精為程序設(shè)計(jì)語言程序。同時加入一些注解和斷言，使程序中邏輯概念清楚；</p><p>　　5）程序調(diào)試與測試：能夠熟練掌握調(diào)試工具的各種功能，設(shè)計(jì)測試數(shù)據(jù)確保程序正確。調(diào)試正確后，認(rèn)真整理源程序及其注釋，形成格式和風(fēng)格良好的源程序清單和結(jié)果；</p&

8、gt;<p>　　6）結(jié)果分析：程序運(yùn)行結(jié)果包括合法的輸入及其輸出結(jié)果和含有非法的輸入及其輸出結(jié)果。算法的時間、空間復(fù)雜性分析；</p><p>　　7）編寫課程設(shè)計(jì)報(bào)告；</p><p>　　以上要求中前三個階段的任務(wù)完成后，先將設(shè)計(jì)說明書的草稿交指導(dǎo)老師面審，審查合格后方可進(jìn)入后續(xù)階段的工作。設(shè)計(jì)工作結(jié)束后，經(jīng)指導(dǎo)老師驗(yàn)收合格后將設(shè)計(jì)說明書打印裝訂。</p>

9、<p>　　指導(dǎo)教師（簽字）： 教研室主任（簽字）： </p><p>　　批準(zhǔn)日期：2014 年 2 月 23 日</p><p><b>　　摘 要</b></p><p>　　本系統(tǒng)以VC++作為軟件開發(fā)環(huán)境，C語言作為程序開發(fā)語言，鄰接矩陣作為存儲結(jié)構(gòu)，設(shè)計(jì)與實(shí)現(xiàn)

10、了最短路徑運(yùn)算。該系統(tǒng)實(shí)現(xiàn)了有向圖的存儲、最短路徑的運(yùn)算等主要功能。依照該系統(tǒng)可以解決生活中許多問題，比如交通路線的選擇，工程時間的預(yù)算等等，讓人們可以做出合理的選擇。本系統(tǒng)通過分析課題的背景、意義、要求，分別從課題描述、邏輯設(shè)計(jì)、算法設(shè)計(jì)、調(diào)試與測試等各個方面詳細(xì)介紹了系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)過程，最后對系統(tǒng)的完成情況進(jìn)行了總結(jié)。界面清晰，操作簡單，易于用戶接受。</p><p>　　關(guān)鍵詞：VC++;鄰接矩陣; 最短

11、路徑</p><p><b>　　目錄</b></p><p><b>　　1 課題描述1</b></p><p>　　2 問題分析與任務(wù)定義2</p><p>　　2.1 問題分析2</p><p>　　2.2 任務(wù)定義2</p><p>

12、;<b>　　3 算法設(shè)計(jì)3</b></p><p>　　3.1 圖的鄰接矩陣的存儲結(jié)構(gòu)3</p><p>　　3.2 Dijkstra算法思想4</p><p>　　4 系統(tǒng)邏輯設(shè)計(jì)5</p><p>　　4.1 主函數(shù)流程圖如圖4.1所示5</p><p>　　4.2 Crea

13、te函數(shù)流程圖如圖4.2所示6</p><p>　　4.3 Dijkstra函數(shù)流程圖如圖4.3所示8</p><p><b>　　4 源代碼11</b></p><p>　　5 調(diào)試與測試14</p><p><b>　　6 總結(jié)16</b></p><p>

14、;<b>　　參考文獻(xiàn)17</b></p><p><b>　　1 課題描述</b></p><p>　　乘車旅行的人大多數(shù)都希望找出到目的地盡可能短，花費(fèi)少的行程，那么如何找出從出發(fā)點(diǎn)到目的地的最短路徑？由于路徑比較多，所以用手工計(jì)算起來比較復(fù)雜，抽象，因此人們用計(jì)算機(jī)語言代替手工計(jì)算來求得最短路徑。而在計(jì)算機(jī)語言中迪杰斯拉算法比較常用，簡

15、捷，故人們經(jīng)常借助計(jì)算機(jī)程序用迪杰斯拉算法求得單源點(diǎn)的最短路徑，這樣可以廣泛的提高效率，而且條理清晰，通俗易懂。</p><p>　　2 問題分析與任務(wù)定義</p><p><b>　　2.1 問題分析</b></p><p>　　本系統(tǒng)是要解決的是單源點(diǎn)最短路徑問題，設(shè)計(jì)程序，實(shí)現(xiàn)最短路徑的求法，系統(tǒng)需要達(dá)到的主要功能如下：</p&g

16、t;<p>　　(1) 編寫算法能夠建立帶權(quán)圖，并能夠用Dijkstra算法求該圖的最短路徑。</p><p>　　(2) 能夠選擇圖上的任意一頂點(diǎn)做為開始節(jié)點(diǎn)。最短路徑輸出不必采用圖形方式，可頂點(diǎn)序列方式輸出。</p><p>　　(3) 根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。兩個子模塊相互獨(dú)立，沒有嵌套調(diào)用的情況，在主模塊中調(diào)用上面兩個子模塊。</p>

17、<p><b>　　2.2 任務(wù)定義</b></p><p>　　根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。兩個子模塊相互獨(dú)立，沒有嵌套調(diào)用的情況，在主模塊中調(diào)用上面兩個子模塊以下是三個模塊的大體分析：</p><p>　　(1) 建立有向圖的存儲結(jié)構(gòu)。</p><p>　　(2) 應(yīng)用Dijkstra算法求出該有向圖的最短路徑。

18、</p><p>　　(3) 在主函數(shù)中調(diào)用兩個子函數(shù)，完成最短路徑的程序設(shè)。</p><p><b>　　3 算法設(shè)計(jì)</b></p><p>　　3.1 圖的鄰接矩陣的存儲結(jié)構(gòu)</p><p>　　一個圖的鄰接矩陣表示唯一的。故在圖的鄰接矩陣表示中，除了需要用一個二維數(shù)組存儲頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣外，通常還需要

19、使用一個具有n個元素的一維數(shù)組存儲頂點(diǎn)信息，其中下標(biāo)為i的元素存儲頂點(diǎn)vi的信息。本設(shè)計(jì)是基于類C語言的算法描述，因此，圖的鄰接矩陣的存儲結(jié)構(gòu)定義如下:</p><p>　　#define MVNum 50</p><p>　　typedef struct {</p><p>　　VertexType vexs[MVNum];</p><p>

20、;　　Adjmatrix arcs[MVNum][MVNum]；</p><p><b>　　}Mgraph;</b></p><p>　　在本系統(tǒng)中，以鄰接矩陣存儲有向圖，如圖3.1a中有向圖G所示，其鄰接矩陣為圖 3.1b所示： </p><p>　　3.2 Dijkstra算法思想</p><p>　?。?）Di

21、jkstra算法核心是貪心，實(shí)質(zhì)是按路徑長度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算法。用自然語言描述如下：</p><p>　　初始化S和D,置空最短路 徑終點(diǎn)集，置初始的最短路徑值；</p><p>　　S[v1]=TRUE;D[v1]=0;</p><p>　　While(S集中的頂點(diǎn)數(shù)<n)</p><p><b>　　{</

22、b></p><p>　　開始循環(huán)，每次求的v1到某個v頂點(diǎn)的最短路徑，并將v加到S集中;</p><p>　　S[v]=TRUE; 更新當(dāng)前最短路徑及距離。</p><p><b>　　}</b></p><p>　?。?）Dijkstra算法結(jié)束后，通過設(shè)置一個數(shù)組記錄下一個節(jié)點(diǎn)的前趨節(jié)點(diǎn)，然后通過倒敘的方式

23、輸出該最短路徑。</p><p><b>　　4 系統(tǒng)邏輯設(shè)計(jì)</b></p><p>　　4.1 主函數(shù)流程圖如圖4.1所示</p><p><b>　　3.1主函數(shù)流程圖</b></p><p>　　4.2 Create函數(shù)流程圖</p><p>　　4.2 Creat

24、e函數(shù)流程圖如圖4.2所示</p><p>　　G->arcs[i][j]=w</p><p>　　4.3 Dijkstra函數(shù)流程圖如圖4.3所示 </p><p><b>　　、</b></p><p><b>　　S[v]=TRUE</b></p><p&g

25、t;<b>　　、</b></p><p><b>　　4 源代碼</b></p><p>　　#include<stdio.h></p><p>　　#include<stdlib.h></p><p>　　#define MVNum 50</p><

26、p>　　#define Maxint 1111</p><p>　　typedef char VertexType; // 定義頂點(diǎn)</p><p>　　typedef int Adjmatrix; </p><p>　　typedef enum {FALSE,TRUE}boolean;</p><p&

27、gt;　　typedef struct { // 圖的鄰接矩陣</p><p>　　VertexType vexs[MVNum]; //頂點(diǎn)向量 存放頂點(diǎn)的一維數(shù)組</p><p>　　Adjmatrix arcs[MVNum][MVNum]; // 鄰接矩陣二維數(shù)組</p><p&g

28、t;　　}MGraph; //定義鄰接矩陣結(jié)構(gòu)類型</p><p>　　void CreateMGraph(MGraph *G,int m,int n) // 采用數(shù)組（鄰接矩陣）表示法，構(gòu)造圖G</p><p><b>　　{</b></p><p>　　int i,j,k,w;</p><p><b>

29、;　　char a,b;</b></p><p>　　for(i=1;i<=m;i++) //構(gòu)造頂點(diǎn)向量</p><p>　　G->vexs[i]=i;</p><p>　　for(i=1;i<=m;i++) //初始化鄰接矩陣</p><p>　　for(j=1;j&

30、lt;=m;j++)</p><p>　　G->arcs[i][j]=Maxint;</p><p>　　printf("輸入%d條邊的i,j及w:\n",n);</p><p>　　for(k=1;k<=n;k++) // 構(gòu)造鄰接矩陣</p><p><b>　　{

31、</b></p><p>　　fflush(stdin);</p><p>　　scanf("%c,%c,%d",&a,&b,&w); //輸入一條邊依附的頂點(diǎn)及權(quán)值</p><p>　　i=a-'a'+1;</p><p>　　j=b-'a'+1;

32、 </p><p>　　G->arcs[i][j]=w; //弧<i,j>的權(quán)值</p><p><b>　　}</b></p><p>　　printf("有向圖的存儲結(jié)構(gòu)建立完成!\n");</p><p>　　printf("***********

33、***********************\n");</p><p><b>　　}</b></p><p>　　void Dijkstra(MGraph G,int v1,int m)</p><p>　　//用Dijkstra算法求G中v1頂點(diǎn)到其余頂點(diǎn)v的最短路徑p[v]及帶權(quán)長度D[v]</p><p&

34、gt;<b>　　{</b></p><p>　　int D[MVNum],P[MVNum];</p><p>　　int v,i,w,min;</p><p>　　boolean S[MVNum];// S以求得最短路徑的終點(diǎn)的集合</p><p>　　for(v=1;v<=m;v++)</p>

35、<p><b>　　{</b></p><p>　　S[v]=FALSE;</p><p>　　D[v]=G.arcs[v1][v];</p><p>　　if(D[v]<Maxint)</p><p><b>　　P[v]=v1;</b></p><p>&

36、lt;b>　　else</b></p><p><b>　　P[v]=0;</b></p><p><b>　　}</b></p><p>　　D[v1]=0;S[v1]=TRUE; // 初始化，v1頂點(diǎn)屬于s集</p><p>　　//開始主循環(huán)，每次求得v1到某個v頂點(diǎn)的

37、最短路徑，并加v到s集</p><p>　　for(i=2;i<=m;i++) // 其余n-1個頂點(diǎn)</p><p><b>　　{</b></p><p>　　min=Maxint; //當(dāng)前所知離v1頂點(diǎn)的最近距離</p><p>　　for(w=1;w<=m;w++)</p><

38、;p>　　if(!S[w]&&D[w]<min) // w頂點(diǎn)在v-s中</p><p><b>　　{</b></p><p><b>　　v=w;</b></p><p>　　min=D[w]; //w頂點(diǎn)離v1頂點(diǎn)更近</p><p><

39、b>　　}</b></p><p>　　S[v]=TRUE;</p><p>　　for(w=1;w<=m;w++) //更新當(dāng)前最短路徑及距離</p><p>　　if(!S[w]&&(D[v]+G.arcs[v][w]<D[w])) // 修改D[w]和P[w],w屬于v-s</p><p>

40、;<b>　　{</b></p><p>　　D[w]=D[v]+G.arcs[v][w];</p><p><b>　　P[w]=v;</b></p><p><b>　　}</b></p><p><b>　　}</b></p><

41、p>　　printf("路徑長度-----------路徑\n");</p><p>　　for(i=1;i<=m;i++)</p><p><b>　　{</b></p><p>　　printf("%5d",D[i]);</p><p>　　printf("

42、;%12c",i-1+'a');v=P[i];</p><p>　　while(v!=0)</p><p><b>　　{</b></p><p>　　printf("<-%c",v-1+'a');</p><p><b>　　v=P[v];&

43、lt;/b></p><p><b>　　}</b></p><p>　　printf("\n");</p><p><b>　　} </b></p><p><b>　　}</b></p><p>　　void main()&

44、lt;/p><p><b>　　{ </b></p><p><b>　　MGraph G;</b></p><p>　　int m,n,v;</p><p><b>　　char ch;</b></p><p>　　printf("輸入所需圖

45、的頂點(diǎn)個數(shù)和邊數(shù)m,n:");</p><p>　　scanf("%d,%d",&m,&n);</p><p>　　CreateMGraph(&G,m,n);</p><p>　　while (v<=m)</p><p><b>　　{</b></p>

46、;<p>　　printf("求最短路徑，請輸入初始點(diǎn)v:");</p><p>　　fflush(stdin);</p><p>　　scanf("%c",&ch);</p><p>　　printf("\n");</p><p>　　v=ch-'a&

47、#39;+1;</p><p>　　Dijkstra(G,v,m);</p><p><b>　　}</b></p><p><b>　　} </b></p><p><b>　　5 調(diào)試與測試</b></p><p>　　（1）合法數(shù)據(jù)測試結(jié)果

48、如圖5.1所示</p><p>　　圖5.1合法數(shù)據(jù)測試結(jié)果</p><p>　?。?）非法數(shù)據(jù)測試結(jié)果如圖5.2所示</p><p>　　圖5.2非法數(shù)據(jù)測試結(jié)果</p><p>　　當(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）。

49、采用鄰接矩陣存儲有向圖，應(yīng)處理每兩個頂點(diǎn)之間的關(guān)系，所以空間復(fù)雜度為O（n2）。</p><p><b>　　6 總結(jié)</b></p><p>　　本次課程設(shè)計(jì)涉及到的范圍很廣，讓我比較系統(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ā)

50、現(xiàn)for循環(huán)的括號后面多了一個“;”，去掉該分號之后，程序可以運(yùn)行。在這次課程設(shè)計(jì)中我體會到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è)計(jì)應(yīng)用的算法是Dijkstra算法。在學(xué)習(xí)的過程中自己對這方面的知識比較生疏，所以在算法設(shè)計(jì)過程中比較困難，尤其是設(shè)計(jì)Dijkstra算法的流程圖時，發(fā)

51、現(xiàn)自己對流程圖這一塊知識存在漏洞，有待加強(qiáng)。目前，該課設(shè)的缺點(diǎn)是：①采用鄰接矩陣存儲圖時，測試其邊的數(shù)目，必須檢查邊二維數(shù)組的所有元素，時間復(fù)雜度為O（n2）,這對于頂點(diǎn)很多而邊較少的圖（稀疏圖）是非常不合算的；②輸出結(jié)果不是有序的；這兩點(diǎn)還有待改進(jìn)。在這次課程設(shè)計(jì)中，我深刻體會到了，不管做任何事情，只要持之以恒，一定會取得成功。</p><p><b>　　參考文獻(xiàn)</b></p&g