課程設(shè)計(jì)-最短路徑算法

1、沈陽(yáng)大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱(chēng)：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目：最短路徑算法院（系）：信息工程學(xué)院專(zhuān)業(yè)：通信工程專(zhuān)業(yè)班 級(jí)：12級(jí)通信2班學(xué) 號(hào)：F1258212姓 名：劉維成指導(dǎo)教師：目 錄 TOC o 1-5 h z HYPERLINK l bookmark10 o Current Document 1課程設(shè)計(jì)介紹1 HYPERLINK l bookmark13 o Current Document 1.1課程設(shè)計(jì)內(nèi)容1 HYPERLINK l bookmark18 o Current Document 1.2課程設(shè)計(jì)要求1 HYPERLINK l bookmark24 o Current

2、 Document 2課程設(shè)計(jì)原理2 HYPERLINK l bookmark27 o Current Document 2.1課設(shè)題目粗略分析22.2原理圖介紹32.2.1功能模塊圖3 HYPERLINK l bookmark41 o Current Document 2.2.2流程圖分析33數(shù)據(jù)結(jié)構(gòu)分析83.1存儲(chǔ)結(jié)構(gòu)8 HYPERLINK l bookmark72 o Current Document 3.2算法描述8 HYPERLINK l bookmark82 o Current Document 4調(diào)試與分析9 HYPERLINK l bookmark85 o Current Do

3、cument 4.1調(diào)試過(guò)程9 HYPERLINK l bookmark90 o Current Document 4.2程序執(zhí)行過(guò)程9 HYPERLINK l bookmark93 o Current Document 參考文獻(xiàn)11 HYPERLINK l bookmark100 o Current Document 附 錄（關(guān)鍵部分程序清單） 121課程設(shè)計(jì)介紹1.1課程設(shè)計(jì)內(nèi)容設(shè)計(jì)程序，實(shí)現(xiàn)最短路徑的求法，系統(tǒng)主要功能如下：編寫(xiě)算法能夠建立帶權(quán)圖，并能夠用Dijkstra算法求該圖的最短路徑。能夠選擇圖上的任意一頂點(diǎn)做為開(kāi)始節(jié)點(diǎn)。最短路徑輸出不必采用圖 形方式，可頂點(diǎn)序列方式輸出。1.2

4、課程設(shè)計(jì)要求帶權(quán)圖的頂點(diǎn)信息用字符串，數(shù)據(jù)可自定。參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。較規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。2課程設(shè)計(jì)原理2.1課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。兩個(gè)子模塊相互獨(dú)立，沒(méi) 有嵌套調(diào)用的情況，在主模塊中調(diào)用上面兩個(gè)子模塊以下是三個(gè)模塊的大體分析:建立有向圖的存儲(chǔ)結(jié)構(gòu).應(yīng)用Dijkstra算法求出該有向圖的最短路徑。在主函數(shù)中調(diào)用上面兩個(gè)子函數(shù)，完成求最短路徑的程序設(shè)計(jì)。4.2.2原理圖介紹2.2.1功能模塊圖2.2.2流程圖分析1.主函數(shù)圖2.1功能模塊圖2.2主函數(shù)流程圖2. Create 函數(shù)3.2.3Create函數(shù)流程圖Dijkstra

5、函數(shù)i=12.4Dijkstra函數(shù)流程圖3數(shù)據(jù)結(jié)構(gòu)分析3.1存儲(chǔ)結(jié)構(gòu)一個(gè)圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需要用一個(gè)二維數(shù)組 存儲(chǔ)頂點(diǎn)之間相鄰關(guān)系的鄰接矩陣外，通常還需要使用一個(gè)具有n個(gè)元素的一維 數(shù)組存儲(chǔ)頂點(diǎn)信息，其中下標(biāo)為i的元素存儲(chǔ)頂點(diǎn)vi的信息。因此，圖的鄰接矩 陣的存儲(chǔ)結(jié)構(gòu)定義如下：#define MVNum 50typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum；Mgraph;3.2算法描述Dijkstra算法核心是貪心，實(shí)質(zhì)是按路徑長(zhǎng)度遞增產(chǎn)生諸頂點(diǎn)的最短路徑算 法。迪杰斯特拉算法可用自然語(yǔ)言描

6、述如下：初始化S和D,置空最短路徑終點(diǎn)集，置初始的最短路徑值；Sv1=TRUE;Dv1=0;While（S集中的頂點(diǎn)數(shù)n）開(kāi)始循環(huán)，每次求的v1到某個(gè)v頂點(diǎn)的最短路徑，并將v加到S集中; Sv=TRUE;更新當(dāng)前最短路徑及距離。2Dijkstra算法結(jié)束后，通過(guò)設(shè)置一個(gè)數(shù)組記錄下一個(gè)節(jié)點(diǎn)的前趨節(jié)點(diǎn)，然后 通過(guò)倒敘的方式輸出該最短路徑。4調(diào)試與分析4.1調(diào)試過(guò)程在調(diào)試程序是主要遇到一下幾類(lèi)問(wèn)題：程序完成后，調(diào)試時(shí)沒(méi)有發(fā)現(xiàn)問(wèn)題，但是當(dāng)輸入開(kāi)始節(jié)點(diǎn)后，運(yùn)行框卻不停的 出現(xiàn)”-a”，后來(lái)重新檢查程序時(shí)發(fā)現(xiàn)for循環(huán)的括號(hào)后面多了一個(gè)”二 去掉該 分號(hào)之后，程序可以運(yùn)行。程序可以運(yùn)行，但是輸出結(jié)果不是有

7、序的，解決方法，設(shè)立一個(gè)前驅(qū)數(shù)組，用 以記錄節(jié)點(diǎn)的雙親節(jié)點(diǎn)，然后按照倒敘的方式讀出該條最短路徑的有向序列。4.2程序執(zhí)行過(guò)程4.1程序執(zhí)行過(guò)程4.2程序執(zhí)行過(guò)程參考文獻(xiàn)數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅcC+描述），殷人昆等，清華大學(xué)出版社， 2010年3月。算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo)，寧正元等，清華大學(xué)出版社， 2009年6月。數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)，蘇仕華等，機(jī)械工業(yè)出版社，2010年3月。C程序設(shè)計(jì)，譚浩強(qiáng)編，清華大學(xué)出版社，2006年6月。錄（關(guān)鍵部分程序清單）程序代碼#include#include#define MVNum 100#define Maxint 32767typedef cha

8、r VertexType;typedef int Adjmatrix;typedef enum FALSE,TRUEboolean;typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;MGraph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;void CreateMGraph(MGraph *G,int n,int e)int i,j,k,w;char a,b;for(i=1;ivexsi=i;for(i=1;i=n;i+)for(j=1;jarcsij=Maxint;pr

9、intf(輸入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 v,i,w,min;boolean SMVNum;for(v=1;v=n;v+)Sv=FALSE;D2v=G.arcsv1v;if(D2vMaxint)P2v=v1;elseP2v=0;D2v1=0;Sv1=TRUE;for(i=2;i=n;i+)min=Maxint;for(w=1;w=n;w+)if(!Sw&D2wmin)v=w;min=D

10、2w;Sv=TRUE;for(w=1;w=n;w+)if(!Sw&(D2v+G.arcsvwD2w)D2w=D2v+G.arcsvw;P2w=v;printf(路徑長(zhǎng)度路徑n);for(i=1;i=n;i+)printf(%5d,D2i);printf(%5c,i-1+a);v=P2i;while(v!=0)printf(-%c,v-1+a);v=P2v;printf(n);void main()MGraph G;int n,e,v;char ch;printf(-輸入圖中頂點(diǎn)個(gè)數(shù)和邊數(shù)n,e:);scanf(%d,%d”,&n,&e);CreateMGraph(&G,n,e);while(1

11、)printf(求最短路徑，輸入開(kāi)始點(diǎn)v:);fflush(stdin);scanf(%c”,&ch);v=ch-a+1;Dijkstra(G,v,n);課程設(shè)計(jì)總結(jié):本次課程設(shè)計(jì)涉及到的范圍很廣，讓我能夠比較系統(tǒng)的對(duì)C語(yǔ)言和數(shù)據(jù)結(jié)構(gòu) 進(jìn)行一次整理和復(fù)習(xí)。同時(shí)有了很多的體會(huì)和經(jīng)驗(yàn)。又一次復(fù)習(xí)了 C語(yǔ)言，在這次課程設(shè)計(jì)中我體會(huì)到C語(yǔ)言超強(qiáng)的邏輯性， 能夠熟練使用VC+的編譯環(huán)境，也對(duì)這兩門(mén)課程有了新的認(rèn)識(shí)，他們既有聯(lián)系， 又相互區(qū)別，在編寫(xiě)程序過(guò)程中要靈活應(yīng)用。對(duì)數(shù)據(jù)結(jié)構(gòu)的理解有待加強(qiáng)，這次課程設(shè)計(jì)應(yīng)用的算法是Dijkstra算 法。在學(xué)習(xí)的過(guò)程中自己就對(duì)這方面的知識(shí)比較生疏，所以剛拿到這個(gè)課設(shè)題目 時(shí)，自己還是有些不自信，好在自己沒(méi)有氣餒，一步一步的努力終于取得了成功。此次設(shè)計(jì)讓我意識(shí)到程序設(shè)計(jì)要求我們必須有不放棄的