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

1、課程設(shè)計(jì) _最短路徑算法沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 課程設(shè)計(jì)題目： 最短路徑算法院（系）：計(jì)算機(jī)學(xué)院專 業(yè)：計(jì)算機(jī)科學(xué)與技術(shù)班 級(jí)： 94010105學(xué) 號(hào)： 2009040101133姓 名： 指導(dǎo)教師：沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告目錄1 課程設(shè)計(jì)介紹 01.1 課程設(shè)計(jì)內(nèi)容 01.2 課程設(shè)計(jì)要求 02 課程設(shè)計(jì)原理 12.1 課設(shè)題目粗略分析 12.2 原理圖介紹 22.2.1 功能模塊圖 22.2.2 流程圖分析 23 數(shù)據(jù)結(jié)構(gòu)分析 73.1 存儲(chǔ)結(jié)構(gòu) 73.2 算法描述 84 調(diào)試與分析 84.1 調(diào)試過程 84.2 程序執(zhí)行過程 9參考文獻(xiàn) 1.1.

2、附 錄（關(guān)鍵部分程序清單） 12沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告1 課程設(shè)計(jì)介紹1.1 課程設(shè)計(jì)內(nèi)容設(shè)計(jì)程序，實(shí)現(xiàn)最短路徑的求法，系統(tǒng)主要功能如下：1. 編寫算法能夠建立帶權(quán)圖， 并能夠用 Dijkstra 算法求該圖 的最短路徑。2. 能夠選擇圖上的任意一頂點(diǎn)做為開始節(jié)點(diǎn)。 最短路徑輸出 不必采用圖形方式，可頂點(diǎn)序列方式輸出。1.2 課程設(shè)計(jì)要求1. 帶權(quán)圖的頂點(diǎn)信息用字符串，數(shù)據(jù)可自定。2. 參考相應(yīng)的資料，獨(dú)立完成課程設(shè)計(jì)任務(wù)。3. 較規(guī)范課程設(shè)計(jì)報(bào)告和軟件代碼。沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告2 課程設(shè)計(jì)原理2.1 課設(shè)題目粗略分析根據(jù)課設(shè)題目要求，擬將整體程序分為三大模塊。兩個(gè)子模塊相互獨(dú)立

3、，沒有嵌套調(diào)用的情況， 在主模塊中調(diào)用上面兩個(gè)子模塊以下是三個(gè)模塊的大體分析：1. 建立有向圖的存儲(chǔ)結(jié)構(gòu) .2. 應(yīng)用 Dijkstra 算法求出該有向圖的最短路徑。3. 在主函數(shù)中調(diào)用上面兩個(gè)子函數(shù)，完成求最短路徑的程序設(shè)計(jì)。4.沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告2.2 原理圖介紹2.2.1 功能模塊圖圖 2.1 功能模塊圖2.2.2 流程圖分析1. 主函數(shù)開始輸入數(shù)據(jù)調(diào)用 Create 函數(shù)調(diào)用2.2 主函數(shù)流程圖2. Create 函數(shù)沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告2.3Create 函3. Dijkstra 函數(shù)沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告5沈陽航空航天大學(xué)課程設(shè)計(jì)

4、報(bào)告w=n結(jié)束沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告2.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 50 typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum ； Mgraph;沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告3.2 算法描述1. Dijkstr

5、a 算法核心是貪心，實(shí)質(zhì)是按路徑長(zhǎng)度遞增產(chǎn)生諸頂點(diǎn)的最短路徑 算法。迪杰斯特拉算法可用自然語言描述如下：初始化 S 和 D,置空最短路徑終點(diǎn)集，置初始的最短路徑值； Sv1=TRUE;Dv1=0;While（S 集中的頂點(diǎn)數(shù) n）開始循環(huán)，每次求的 v1 到某個(gè) v 頂點(diǎn)的最短路徑，并將 v 加到 S 集中; Sv=TRUE; 更新當(dāng)前最短路徑及距離。2Dijkstra 算法結(jié)束后， 通過設(shè)置一個(gè)數(shù)組記錄下一個(gè)節(jié)點(diǎn)的前趨節(jié)點(diǎn)， 然后 通過倒敘的方式輸出該最短路徑。4 調(diào)試與分析4.1 調(diào)試過程在調(diào)試程序是主要遇到一下幾類問題：1. 程序完成后， 調(diào)試時(shí)沒有發(fā)現(xiàn)問題， 但是當(dāng)輸入開始節(jié)點(diǎn)后， 運(yùn)

6、行框卻不停的 出現(xiàn)”-a”,后來重新檢查程序時(shí)發(fā)現(xiàn) for 循環(huán)的括號(hào)后面多了一個(gè) ”;”，去掉該 分號(hào)之后，程序可以運(yùn)行。2. 程序可以運(yùn)行，但是輸出結(jié)果不是有序的，解決方法，設(shè)立一個(gè)前驅(qū)數(shù)組，用 以記錄節(jié)點(diǎn)的雙親節(jié)點(diǎn)，然后按照倒敘的方式讀出該條最短路徑的有向序列。沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告4.2 程序執(zhí)行過程4.1 程序執(zhí)行過程沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告4.2 程序執(zhí)行過程10沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告參考文獻(xiàn)1 數(shù)據(jù)結(jié)構(gòu)（用面向?qū)ο蠓椒ㄅc C+描述），殷人昆等，清華大學(xué)出版社， 2010 年 3 月。2 算法與數(shù)據(jù)結(jié)構(gòu)習(xí)題精解和實(shí)驗(yàn)指導(dǎo) ，寧正元等，清華大學(xué)出版社， 2009 年

7、6 月。3 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) ，蘇仕華等，機(jī)械工業(yè)出版社， 2010年 3月。4 C 程序設(shè)計(jì)，譚浩強(qiáng)編，清華大學(xué)出版社， 2006年 6月。11沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告附 錄（關(guān)鍵部分程序清單）程序代碼#include #include#define MVNum 100#define Maxint 32767 typedef char VertexType; typedef int Adjmatrix;typedef enum FALSE,TRUEboolean; typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum;M

8、Graph;int D1MVNum,P1MVNum;int DMVNumMVNum,PMVNumMVNum;12沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告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;printf( 輸入 %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)in

9、t 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=D2w;13沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告Sv=TRUE; for(w=1;w=n;w+) if(!Sw&(D2v+G .arcsvwD2w) D2w=D2v+G .arcsvw; P2w=v;printf(

10、路徑長(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)printf( 求最短路徑，輸入開始點(diǎn) v:); fflush(stdin);scanf(%c,&ch);v=ch-a+1;Dijkstr

11、a(G,v,n);14沈陽航空航天大學(xué)課程設(shè)計(jì)報(bào)告課程設(shè)計(jì)總結(jié)： 本次課程設(shè)計(jì)涉及到的范圍很廣，讓我能夠比較系統(tǒng)的對(duì)C 語言和數(shù)據(jù)結(jié)構(gòu)進(jìn)行一次整理和復(fù)習(xí)。同時(shí)有了很多的體會(huì)和經(jīng)驗(yàn)。1. 又一次復(fù)習(xí)了 C語言，在這次課程設(shè)計(jì)中我體會(huì)到 C 語言超強(qiáng)的邏輯性， 能夠熟練使用 VC+的編譯環(huán)境， 也對(duì)這兩門課程有了新的認(rèn)識(shí)， 他們既有聯(lián)系， 又相互區(qū)別，在編寫程序過程中要靈活應(yīng)用。2. 對(duì)數(shù)據(jù)結(jié)構(gòu)的理解有待加強(qiáng)，這次課程設(shè)計(jì)應(yīng)用的算法是 Dijkstra 算 法。在學(xué)習(xí)的過程中自己就對(duì)這方面的知識(shí)比較生疏，所以剛拿到這個(gè)課設(shè)題 目時(shí)，自己還是有些不自信，好在自己沒有氣餒，一步一步的努力終于取得了 成功。3. 此次設(shè)計(jì)讓我意識(shí)到程序設(shè)計(jì)要求我們必須有不放棄的精神，不能因?yàn)?幾個(gè)錯(cuò)誤就輕言放棄，只有堅(jiān)持不懈方