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

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

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

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

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

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

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

8、表中畫圓圈的數字表示該步驟中D（w）的最小值。這樣，相應的節點w就加到N中，D（v）的值就按要求更改。因此，在初始化后的第1步，距離最小D（4）=w，節點4就加進集合N中；在第2步，D（5）=2，節點5加進N中；如此不斷繼續下去。第5步以后，所有的節點都在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 算法的計算過程3、設計過程與分析3.1設計內容根據我們平常在通信網基礎的課程中所學的知識，使用Dijkstra算法，設計一個 沈 陽 大 學課程設

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

10、*/AdjType length;/*最短路徑長度*/int prevex;/*從v0到達vi(i=1,2,.n-1)的最短路徑上vi的前趨頂點*/ 沈 陽 大 學課程設計說明書 NO.7Path;Path dist6;/*n為圖中頂點個數*/#define MAX 1e+8void init(GraphMatrix* pgraph,Path dist)int i;dist0.length=0;dist0.prevex=0;dist0.vertex=pgraph->vexs0;pgraph->arcs00=1;/*表示頂點v0在集合U中*/for(i=1;i<pgraph-&

11、gt;n;i+)/*初始化集合V-U中頂點的距離值*/disti.length=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);/*初始化，此時集合U中只有頂點v0*/for(i=1;i<graph.n;i+)min=MAX;minvex=0;for

12、(j=1;j<graph.n;j+)if(graph.arcsjj=0&&(distj.length<min)/*在V-U中選出距離值最小頂點*/min=distj.length;minvex=j;if(minvex=0) break; /* 從v0沒有路徑可以通往集合V-U中的頂點 */ graph.arcsminvexminvex=1; /* 集合V-U中路徑最小的頂點為minvex */ for(j=1; j<graph.n; j+) /* 調整集合V-U中的頂點的最短路徑 */ 沈 陽 大 學課程設計說明書 NO.8 if(graph.arcsjj=1

13、) continue; if(distj.length>distminvex.length+graph.arcsminvexj) distj.length=distminvex.length+graph.arcsminvexj; distj.prevex=minvex; void initgraph() int i,j; graph.n=6; for(i=0;i<graph.n;i+) for(j=0;j<graph.n;j+) graph.arcsij=(i=j?0:MAX); graph.arcs01=50; graph.arcs02=10; graph.arcs12=1

14、5; graph.arcs14=5; graph.arcs20=20; graph.arcs23=15; graph.arcs31=20; graph.arcs34=35; graph.arcs43=30; graph.arcs53=3; graph.arcs04=45; 沈 陽 大 學課程設計說明書 NO.9int main() int i; initgraph(); dijkstra(graph,dist); for(i=0;i<graph.n;i+) printf("(%.0f %d)",disti.length,disti.prevex); return 0;

15、 void initgraph() int i,j; graph.n=6; for(i=0;i<graph.n;i+) for(j=0;j<graph.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; 沈 陽 大 學課程設計說明書 NO.10graph.arcs43=30; graph.arcs53=3;

16、 graph.arcs04=45; int main() int i; initgraph(); dijkstra(graph,dist); for(i=0;i<graph.n;i+) printf("(%.0f %d)",disti.length,disti.prevex); return 0;3.3設計結果分析Dijkstra算法是典型的最短路徑路由算法，用于計算一個節點到其他所有節點的最短路徑。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短路徑的最優解，但由于它遍歷計算的節點很多，所以效率低。 上面部分的源程序為已知點的

17、名稱保存在int Apointnum中,點間的路徑和權值保存在數組int Bpointnumpointnum中，其中兩點間無路徑用-1表示，求void Dijkstra(int B,int pointnum,int depart,int dest)，其中int depart表示出發點的名稱,int dest表示終點名稱。輸出結果：depart->中間點1->中間點2->destDijkstra算法是很有代表性的最短路算法，在很多專業課程中都作為基本內容有詳細的介紹。根據設計結果我們可以知道，如果從某頂點出發（此點稱為源點），經邊到達另一 沈 陽 大 學課程設計說明書 NO.1

18、1頂點（稱為終點）的路徑不止一條，而如何找到一條路徑使沿此路徑上各邊的權值之和為最小就是我們研究的問題。通過C語言的編程和運行，我們就可以方便的用Dijkstra算法求出最短路徑。4、設計體會 通過這次的課程設計，讓我對所學的書本上的知識得到了實際上的應用，這不僅使我對知識的記憶更加牢固，還讓我對有關通信網基礎里的最短路徑算法有了更深的了解，讓我了解到，我們平常所學的知識不是死的，我們在日常中也可以用到。通過這次的學習，讓我對通信網基礎這門課程更加感興趣了。在這期間，我們同學間互相幫助，互相講解不會的地方，讓我們真正在快樂中學習到了知識。我想我們一定會抓住每一次這種學習的機會，更加努力！5、參

19、考文獻1王承恕 . 通信網基礎.北京：人民郵電出版社，20022周昕數據通信與網絡技術北京：清華大學出版社，20043唐寶民，通信網技術基礎，人民郵電出版社,20054申普兵，計算機網絡與通信，人民郵電出版社20075馬進通信網分析M北京：人民交通出版社，2003140-180，193-218 沈 陽 大 學課程設計說明書 NO.12 沈 陽 大 學課程設計說明書 NO.13 沈 陽 大 學課程設計說明書 NO.14 沈 陽 大 學課程設計說明書 NO.15 沈 陽 大 學參考文獻要列出3篇以上，格式如下：1謝宋和,甘勇.單片機模糊控制系統設計與應用實例M.北京:電子工業出版社, 1999.5：20-25（參考書或專著格式為:著者.書名M.版本(第1版不注).出版地:出版者,出版年月：引文所在頁碼）2潘新民,王燕芳.微型計算機控制技術M,第2版.北京:電子工