課程設計最短路徑算法

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

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

3、，沒有嵌套調(diào)用的情況， 在主模塊中調(diào)用上面兩個子模塊以下是三個模塊的大體分析：1. 建立有向圖的存儲結(jié)構 .2. 應用 Dijkstra 算法求出該有向圖的最短路徑。3. 在主函數(shù)中調(diào)用上面兩個子函數(shù)，完成求最短路徑的程序設計。4.沈陽航空航天大學課程設計報告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ù)沈陽航空航天大學課程設計報告沈陽航空航天大學課程設計報告2.3Create 函3. Dijkstra 函數(shù)沈陽航空航天大學課程設計報告5沈陽航空航天大學課程設計

4、報告w=n結(jié)束沈陽航空航天大學課程設計報告2.4Dijkstra 函數(shù)流程圖3 數(shù)據(jù)結(jié)構分析3.1 存儲結(jié)構 一個圖的鄰接矩陣表示是唯一的。圖的鄰接矩陣表示，除了需要用一個二維數(shù)組 存儲頂點之間相鄰關系的鄰接矩陣外，通常還需要使用一個具有 n 個元素的一維 數(shù)組存儲頂點信息，其中下標為 i的元素存儲頂點 vi 的信息。因此，圖的鄰接矩 陣的存儲結(jié)構定義如下 :#define MVNum 50 typedef struct VertexType vexsMVNum;Adjmatrix arcsMVNumMVNum ； Mgraph;沈陽航空航天大學課程設計報告3.2 算法描述1. Dijkstr

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

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

7、6 月。3 數(shù)據(jù)結(jié)構課程設計 ，蘇仕華等，機械工業(yè)出版社， 2010年 3月。4 C 程序設計，譚浩強編，清華大學出版社， 2006年 6月。11沈陽航空航天大學課程設計報告附 錄（關鍵部分程序清單）程序代碼#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沈陽航空航天大學課程設計報告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( 有向圖的存儲結(jié)構建立完畢 !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沈陽航空航天大學課程設計報告Sv=TRUE; for(w=1;w=n;w+) if(!Sw&(D2v+G .arcsvwD2w) D2w=D2v+G .arcsvw; P2w=v;printf(

10、路徑長度 路徑 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( 輸入圖中頂點個數(shù)和邊數(shù) n,e:); scanf(%d,%d,&n,&e);CreateMGraph(&G ,n,e);while(1)printf( 求最短路徑，輸入開始點 v:); fflush(stdin);scanf(%c,&ch);v=ch-a+1;Dijkstr

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