通信網(wǎng)基礎(chǔ)及應(yīng)用課程設(shè)計(jì)C語言環(huán)境下D算法完成最短路徑求解

1、課程設(shè)計(jì)說明書 NO.1C語言環(huán)境下D算法完成最短路徑求解1.課程設(shè)計(jì)的目的為了鞏固“通信網(wǎng)基礎(chǔ)及應(yīng)用”課程學(xué)到的相關(guān)知識(shí)，通過對(duì)本課程所學(xué)知識(shí)的綜合運(yùn)用，使學(xué)生融會(huì)貫通課程中所學(xué)的理論知識(shí)，初步掌握通信網(wǎng)絡(luò)的體系結(jié)構(gòu)和擴(kuò)頻通信系統(tǒng)等相關(guān)知識(shí)；加深對(duì)通信網(wǎng)絡(luò)的基本理論、基本知識(shí)和常用技術(shù)的理解；提高學(xué)生分析問題的能力和實(shí)踐能力，培養(yǎng)科學(xué)研究的獨(dú)立工作能力。2.設(shè)計(jì)方案論證2.1最短路徑算法的分類用于解決最短路徑問題的算法被稱做“最短路徑算法”，有時(shí)被簡(jiǎn)稱作“路徑算法”。 最常用的路徑算法有： 1.Dijkstra算法,是解決一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)之間的最短路徑的問題。2.A*算法。3.SPFA算法

2、。4.Bellman-Ford算法。5.Floyd-Warshall算法，可以用來求解網(wǎng)中任意兩個(gè)節(jié)點(diǎn)之間的最短路徑。6.Johnson算法。所謂單源最短路徑問題是指：已知G（V，E），我們希望找出從某給定的源結(jié)點(diǎn)SV到V中的每個(gè)結(jié)點(diǎn)的最短路徑。 首先，我們可以發(fā)現(xiàn)有這樣一個(gè)事實(shí)：如果P是G中從vs到vj的最短路，vi是P中的一個(gè)點(diǎn)，那么，從vs沿P到vi的路是從vs到vi的最短路。2.2經(jīng)典Dijkstra算法的主要思想Dijkstra算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào) (dj, pj)，其中dj是從起源點(diǎn)s到點(diǎn)j的最短路徑的長度 (從頂點(diǎn)到其本身的最短路徑是零路(沒有弧的路)，其長度

3、等于零)；pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的最 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO2短路徑算法的基本過程如下：第一步：初始化。令N=1。對(duì)于不在N中的每個(gè)節(jié)點(diǎn)v，設(shè)置D（v）=l（1，v）（對(duì)于與1不直接相連的節(jié)點(diǎn)取為）。 第二步：找到一個(gè)不在N中的使D（w）最小的節(jié)點(diǎn)w，并將w加進(jìn)集N中去，然后計(jì)算下式，以修改不在N中的所有其他節(jié)點(diǎn)的D（v）： D（v）=minD（v），D（w）+l（w，v） 重復(fù)第二步，直至全部節(jié)點(diǎn)包括在N中。2.3 Dijkstra算法的實(shí)現(xiàn)我們利用圖1中所示的網(wǎng)作為例子討論Dijkstra算法，我們的目的是求出源節(jié)點(diǎn)到網(wǎng)中所有其他節(jié)點(diǎn)的最

4、短路徑。在求解過程中，采取步進(jìn)方式，建立一個(gè)以源節(jié)點(diǎn)1為根的最短路徑樹，直到包括最遠(yuǎn)的節(jié)點(diǎn)在內(nèi)為止。到第k步，計(jì)算出到離源節(jié)點(diǎn)最近的k個(gè)節(jié)點(diǎn)的最短路徑。這些路徑定義為在集N內(nèi)。圖1一個(gè)網(wǎng)絡(luò)的例子在按標(biāo)記法實(shí)現(xiàn)Dijkstra算法的過程中，核心步驟就是從未標(biāo)記的點(diǎn)中選擇一個(gè)權(quán)值最小的弧段。要選擇一個(gè)權(quán)值最小的弧段就必須把所有的點(diǎn)都掃描一遍，將這些要掃描的點(diǎn)按其所在邊的權(quán)值進(jìn)行順序排列，這樣即可大大提高算法的執(zhí)行效率。 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.32.4 Dijkstra算法的基本原理Dijkstra算法解決的是有向圖中最短路徑問題。Dijstra算法的基礎(chǔ)操作是邊的拓展。圖2中示出了以

5、源節(jié)點(diǎn)1為根的最短距離樹。它的產(chǎn)生過程是：當(dāng)一個(gè)節(jié)點(diǎn)加入集合N時(shí)，它就連接到已在N中的適當(dāng)點(diǎn)。每個(gè)節(jié)點(diǎn)下面圓圈內(nèi)的數(shù)字代表在第n步該節(jié)點(diǎn)加入樹結(jié)構(gòu)。由節(jié)點(diǎn)1的最短距離樹可以得到節(jié)點(diǎn)1的路由選擇表，如圖3所示。該表指明了到相應(yīng)的目的的地節(jié)點(diǎn)所應(yīng)選的下一節(jié)點(diǎn)。同理，我們可以求得節(jié)點(diǎn)2,3，6的路由選擇表。圖2 節(jié)點(diǎn)1到其他節(jié)點(diǎn)的最短距離（a） 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.4 目的節(jié)點(diǎn) 下一節(jié)點(diǎn)2 23 44 45 46 4圖3 節(jié)點(diǎn)1到其他節(jié)點(diǎn)的最短距離（b）2.4.1 Dijkstra算法的基本過程Dijkstra算法是最短路徑算法中最典型的一種算法，求最短路徑就是解決一個(gè)節(jié)點(diǎn)到其他節(jié)點(diǎn)

6、之間的最短路徑的問題。Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE表方式。大概過程： 創(chuàng)建兩個(gè)表，OPEN, CLOSE。 OPEN表保存所有已生成而未考察的節(jié)點(diǎn)，CLOSED表中記錄已訪問過的節(jié)點(diǎn)。 1 訪問路網(wǎng)中距離起始點(diǎn)最近且沒有被檢查過的點(diǎn)，把這個(gè)點(diǎn)放入OPEN組中等待檢查。 2 從OPEN表中找出距起始點(diǎn)最近的點(diǎn)，找出這個(gè)點(diǎn)的所有子節(jié)點(diǎn)，把這個(gè)點(diǎn)放到CLOSE表中。 3 遍歷考察這個(gè)點(diǎn)的子節(jié)點(diǎn)。求出這些子節(jié)點(diǎn)距起始點(diǎn)的距離值，放子節(jié)點(diǎn)到OPEN表中。 4 重復(fù)第2和第3步,直到OPEN表為空，或找到目標(biāo)點(diǎn)。最短路徑問題是圖論研究中

7、的一個(gè)經(jīng)典算法問題， 旨在尋找圖（由結(jié)點(diǎn)和路徑組成的）中兩結(jié)點(diǎn)之間的最短路徑。算法具體的形式包括：確定起點(diǎn)的最短路徑問題 - 即已知起始結(jié)點(diǎn)，求最短路徑的問題。 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.5確定終點(diǎn)的最短路徑問題 - 與確定起點(diǎn)的問題相反，該問題是已知終結(jié)結(jié)點(diǎn)，求最短路徑的問題。在無向圖中該問題與確定起點(diǎn)的問題完全等同，在有向圖中該問題等同于把所有路徑方向反轉(zhuǎn)的確定起點(diǎn)的問題。 確定起點(diǎn)終點(diǎn)的最短路徑問題 - 即已知起點(diǎn)和終點(diǎn)，求兩結(jié)點(diǎn)之間的最短路徑。 全局最短路徑問題 - 求圖中所有的最短路徑。2.4.2 Dijkstra算法的步驟圖4示出了求圖1網(wǎng)中節(jié)點(diǎn)1到其他節(jié)點(diǎn)最短路徑的過程

8、。在表中畫圓圈的數(shù)字表示該步驟中D（w）的最小值。這樣，相應(yīng)的節(jié)點(diǎn)w就加到N中，D（v）的值就按要求更改。因此，在初始化后的第1步，距離最小D（4）=w，節(jié)點(diǎn)4就加進(jìn)集合N中；在第2步，D（5）=2，節(jié)點(diǎn)5加進(jìn)N中；如此不斷繼續(xù)下去。第5步以后，所有的節(jié)點(diǎn)都在N中，算法終止。步驟ND（2）D（3）D（4）D（5）D（6）初始125111,424221,4,5231431,2,4,5312441,2,3,4,5212451,2,3,4,5,62312圖4 算法的計(jì)算過程3、設(shè)計(jì)過程與分析3.1設(shè)計(jì)內(nèi)容 根據(jù)我們平常在通信網(wǎng)基礎(chǔ)的課程中所學(xué)的知識(shí)，使用Dijkstra算法，設(shè)計(jì)一個(gè) 沈 陽 大 學(xué)

9、課程設(shè)計(jì)說明書 NO.6用C語言程序編譯的求最短路徑的程序。以下為用鄰接矩陣表示的圖的Dijkstra算法的源程序。3.2設(shè)計(jì)程序#include#define MAXVEX 100typedef char VexType;typedef float AdjType;typedef structVextype vexsMAXVEX;/*頂點(diǎn)信息*/AdjType arcsMAXVEXMAXVEX;/*邊信息*/int n;/*圖的頂點(diǎn)個(gè)數(shù)*/GraphMatrix;GraphMatrix graph;typedef structVexType vertex;/*頂點(diǎn)信息*/AdjType le

10、ngth;/*最短路徑長度*/int prevex;/*從v0到達(dá)vi(i=1,2,.n-1)的最短路徑上vi的前趨頂點(diǎn)*/ 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.7Path;Path dist6;/*n為圖中頂點(diǎn)個(gè)數(shù)*/#define MAX 1e+8void init(GraphMatrix* pgraph,Path dist)int i;dist0.length=0;dist0.prevex=0;dist0.vertex=pgraph-vexs0;pgraph-arcs00=1;/*表示頂點(diǎn)v0在集合U中*/for(i=1;in;i+)/*初始化集合V-U中頂點(diǎn)的距離值*/disti.le

11、ngth=pgraph-arcs0i;disti.vertex=pgraph-vexsi;if(disti.length!=MAX)disti.prevex=0;else disti.pervex=-1;void dijlstra(GraphMatrix graph,Path dist)int i,j,minvex;AdjType min;init(&graph,dist);/*初始化，此時(shí)集合U中只有頂點(diǎn)v0*/for(i=1;igraph.n;i+)min=MAX;minvex=0;for(j=1;jgraph.n;j+)if(graph.arcsjj=0&(distj.lengthmin

12、)/*在V-U中選出距離值最小頂點(diǎn)*/min=distj.length;minvex=j;if(minvex=0) break; /* 從v0沒有路徑可以通往集合V-U中的頂點(diǎn) */ graph.arcsminvexminvex=1; /* 集合V-U中路徑最小的頂點(diǎn)為minvex */ for(j=1; jdistminvex.length+graph.arcsminvexj) distj.length=distminvex.length+graph.arcsminvexj; distj.prevex=minvex; void initgraph() int i,j; graph.n=6;

13、for(i=0;igraph.n;i+) for(j=0;jgraph.n;j+) graph.arcsij=(i=j?0:MAX); graph.arcs01=50; graph.arcs02=10; graph.arcs12=15; graph.arcs14=5; graph.arcs20=20; graph.arcs23=15; graph.arcs31=20; graph.arcs34=35; graph.arcs43=30; graph.arcs53=3; graph.arcs04=45; 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.9int main() int i; initgraph(

14、); dijkstra(graph,dist); for(i=0;igraph.n;i+) printf(%.0f %d),disti.length,disti.prevex); return 0; void initgraph() int i,j; graph.n=6; for(i=0;igraph.n;i+) for(j=0;jgraph.n;j+) graph.arcsij=(i=j?0:MAX); graph.arcs01=50; graph.arcs02=10; graph.arcs12=15; graph.arcs14=5; graph.arcs20=20; graph.arcs2

15、3=15;graph.arcs31=20; graph.arcs34=35; 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.10graph.arcs43=30; graph.arcs53=3; graph.arcs04=45; int main() int i; initgraph(); dijkstra(graph,dist); for(i=0;i中間點(diǎn)1-中間點(diǎn)2-destDijkstra算法是很有代表性的最短路算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹。根據(jù)設(shè)計(jì)結(jié)果我們可以知道，如果從某頂點(diǎn)出發(fā)（此點(diǎn)稱為源點(diǎn)），經(jīng)邊到達(dá)另一 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.11頂點(diǎn)（稱為終點(diǎn)）的路徑不止

16、一條，而如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小就是我們研究的問題。通過C語言的編程和運(yùn)行，我們就可以方便的用Dijkstra算法求出最短路徑。4、設(shè)計(jì)體會(huì) 通過這次的課程設(shè)計(jì)，讓我對(duì)所學(xué)的書本上的知識(shí)得到了實(shí)際上的應(yīng)用，這不僅使我對(duì)知識(shí)的記憶更加牢固，還讓我對(duì)有關(guān)通信網(wǎng)基礎(chǔ)里的最短路徑算法有了更深的了解，讓我了解到，我們平常所學(xué)的知識(shí)不是死的，我們?cè)谌粘Ｖ幸部梢杂玫健Ｍㄟ^這次的學(xué)習(xí)，讓我對(duì)通信網(wǎng)基礎(chǔ)這門課程更加感興趣了。在這期間，我們同學(xué)間互相幫助，互相講解不會(huì)的地方，讓我們真正在快樂中學(xué)習(xí)到了知識(shí)。我想我們一定會(huì)抓住每一次這種學(xué)習(xí)的機(jī)會(huì)，更加努力！5、參考文獻(xiàn)1王承恕 . 通信網(wǎng)基

17、礎(chǔ).北京：人民郵電出版社，20022周昕數(shù)據(jù)通信與網(wǎng)絡(luò)技術(shù)北京：清華大學(xué)出版社，20043唐寶民，通信網(wǎng)技術(shù)基礎(chǔ)，人民郵電出版社,20054申普兵，計(jì)算機(jī)網(wǎng)絡(luò)與通信，人民郵電出版社20075馬進(jìn)通信網(wǎng)分析M北京：人民交通出版社，2003140-180，193-218 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.12 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.13 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.14 沈 陽 大 學(xué)課程設(shè)計(jì)說明書 NO.15 沈 陽 大 學(xué)參考文獻(xiàn)要列出3篇以上，格式如下：1謝宋和,甘 勇.單片機(jī)模糊控制系統(tǒng)設(shè)計(jì)與應(yīng)用實(shí)例M.北京:電子工業(yè)出版社, 1999.5：20-25（參考書或?qū)Ｖ?/p>

18、格式為:著者.書名M.版本(第1版不注).出版地:出版者,出版年月：引文所在頁碼）2潘新民,王燕芳.微型計(jì)算機(jī)控制技術(shù)M,第2版.北京:電子工業(yè)出版社, 2003.4：305-350（1本書只能作為1篇參考文獻(xiàn)，不能將1本書列為多個(gè)參考文獻(xiàn)）3范立南,謝子殿.單片機(jī)原理及應(yīng)用教程M.北京:北京大學(xué)出版社, 2006.1：123-1304 Newman W M, Sbroull R F. Principles of Interactive Computer GraphicsM. New York: McGraw Hill, 1979.10：10-255卜小明,龍全求.一種薄板彎曲問題的四邊形位移單元J.力學(xué)學(xué)報(bào), 1991,23(1):53-60（參考期刊雜志格式為:作者.論文題目J.期刊名,出版年,卷號(hào)(期號(hào)):頁碼）（期刊名前不寫出版地）6Mastri A R. Neuropathy of diabetic neurogenic bl