基于Dijkstra算法的路由選擇

1、 摘 要通過對圖論及其算法深入的學(xué)習(xí)，本文簡單介紹了圖論的發(fā)展與特點，闡述了最短路徑問題及其算法。并采用迪克斯屈拉算法解決最短路由問題。眾所周知，圖論是數(shù)學(xué)的一個分支，它以圖為研究對象。圖論中的圖是由若干給定的點及連接兩點的線所構(gòu)成的圖形，這些圖形通常用來描述某些事物之間的特定關(guān)系，用點代表事物，用連接兩點的線表示相應(yīng)兩個事物間具有的關(guān)系。最短路由的問題利用了圖的描述，并把算法用C+語言來實現(xiàn)，這就很好地將所學(xué)知識和現(xiàn)實生活結(jié)合起來。關(guān)鍵詞：最短路徑 Dijkstra算法 C+AbstractBased on the graph theory and algorithm of in-depth

2、 study, this paper briefly introduces the development and characteristics of graph theory, presents the shortest path problem and its algorithm, and adopts Dijkstra algorithm to solve the shortest routing problem. As is known to all, graph theory is a branch of mathematics, it so as the research obj

3、ect. Graph theory in the diagram consists in some given points and the lines connecting two points of a graph, these graphics are usually used to describe the specific relationship between things, using points representative things, using the lines connecting two points representative the correspond

4、ing relationship between things. The shortest routing problem makes use of graph description, and the realization of the algorithm, which takes advantage of C+. it is a good way to combine the knowledge weve learned with our life.Keyword: shortest path Dijkstra's algorithm C+引 言隨著現(xiàn)代通信技術(shù)的不斷發(fā)展，通信網(wǎng)

5、的范圍也逐漸擴(kuò)大，通信網(wǎng)已成為人們生活中不可或缺的一部分了。而隨著人們之間通信次數(shù)的增加，使的通信網(wǎng)的通信量也隨之大量增加。這給通信網(wǎng)帶了沉重的負(fù)擔(dān)。如何在現(xiàn)有通信網(wǎng)的基礎(chǔ)上提高通信效率，網(wǎng)絡(luò)利用率和網(wǎng)絡(luò)可靠性1，以滿足人們?nèi)找嬖鲩L的對網(wǎng)絡(luò)通信能力的需求已成為對通信網(wǎng)研究的主要內(nèi)容。迪克斯屈拉算法是最適合解決網(wǎng)絡(luò)拓?fù)渲袃晒?jié)點間的最短通信距離的問題的方法之一。本文就如何利用迪克斯屈拉算法解決網(wǎng)絡(luò)中點到點通信的最短距離問題做了說明，以此提高通信網(wǎng)的通信效率。第一章 迪克斯屈拉算法1.1 算法介紹Dijkstra(迪克斯屈拉)算法是典型的單源最短路徑算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主

6、要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等。注意該算法要求圖中不存在負(fù)權(quán)邊3。Procedure Dijkstra（G：所有權(quán)都為正數(shù)的加權(quán)連通簡單圖）G帶有定點a=v0, v1 ，vn=z和權(quán)w（vi , vj）,若 vi, vj 不是G中的邊，則w（vi, vj）=For i:=1 to nL（vi）:=L（a）: =0S:=初始化標(biāo)記，a的標(biāo)記為0，其余結(jié)點標(biāo)記為，S是空集While zSbeginu:=不屬于S的L（u）最小的一個頂點S：=Sufor 所

7、有不屬于S的頂點vif L(u)+w(u,v) < L(v)then L(v):=L(u)+w(u,v)這樣就給S中添加帶最小標(biāo)記的頂點并且更新不在S中的頂點標(biāo)記end L（z）=從a到z的最短路的長度1.2 根據(jù)Dijkstra算法給出的定理定理1 迪克斯屈拉算法求出連通簡單無向加權(quán)圖中的兩個頂點之間最短路的長度2。迪克斯屈拉算法通過一步一步的迭代求出最短路徑，假設(shè)在第k次迭代中。在s中的頂點v的標(biāo)記L(v)是從a到這個頂點v的最短路的長度。不在s中的頂點的標(biāo)記是（除了這個頂點自身之外）只經(jīng)過s中頂點的從a到這個頂點的最短路的長度。設(shè)u是第k次迭代結(jié)束時帶最小標(biāo)記的不在s中的頂點（若該

8、頂點不唯一，可采用帶最小標(biāo)記的任意頂點）。在第k+1次迭代中，u是添加到s中的頂點，則在第k+1次迭代中，u的標(biāo)記必須是a到u的最短路的長度。否則，k次迭代后，從結(jié)點a到某個結(jié)點l的路，其路得長度小于Lk（v）。定理2 迪克斯屈拉算法使用O（n2）次運(yùn)算（加法和比較）來求出n階連通簡單無向加權(quán)圖中兩個頂點之間最短路的長度,求加權(quán)無向圖中最短路的Dijkstra算法可以推廣到求加權(quán)有向圖中最短有向路。定理3 設(shè)有向圖G中不含長度非正的有向圈，并且從點1到其余各點都有有限長的有向路,那么G中結(jié)點1到其余各點j的最短有向路長度Sj有唯一有限解Sj。定理4 設(shè)Sj是加權(quán)有向圖G中自結(jié)點1到結(jié)點j的最短

9、有向路的長度，并且對所有的j=1，2，3，n，Sj為有限值。若圖G中除結(jié)點1外的其余各點能重新編寫成如下的序號2，3，n使得對所有i<j，成立SiSj 且w<j,i>0或者Si>Sj 且 w<j,i>=,即 <j,i>E（G），則S1=0Sj=k<jminSk+w<k,j>,j=2,3,，n 定理5 設(shè)G=<V,E>是一個邊權(quán)為正值的有向圖，其中V=1，2，3，n。則在G中，任意一條最短有向路得長都大于它的真子有向路的長。Dijkstra算法求出了圖中一個特定頂點到其他各定點的最短路，可以利用Dijkstra算法解決

10、實際生活中的一些問題。第二章 Dijkstra算法的實際應(yīng)用2.1 問題的提出在現(xiàn)實生活中，我們常常會遇到很多問題，都是要找到一個地方到另一個地方的最短路徑，當(dāng)然還要滿足各方面的要求，包括可實現(xiàn)性、預(yù)算、帶來的利益等各方面條件4。比如Dijkstra算法在計算機(jī)網(wǎng)絡(luò)路由問題中的應(yīng)用。通常我們解決的辦法就是找到一條距離最短，又在現(xiàn)實可接受范圍內(nèi)的路徑。2.2 運(yùn)用Dijkstra算法解決實際問題在通信網(wǎng)中，如何利用現(xiàn)有的通信網(wǎng)絡(luò)，通過最短的通信路徑完成信息的傳遞，在通信網(wǎng)研究中具有重要意義。為了降低研究復(fù)雜性，我們假設(shè)每條通信線路的通信系能和狀況都一樣且恒定不變。建立如下網(wǎng)絡(luò)模型：點用來表示路由

11、節(jié)點（用a到e及z表示），邊用來表示兩節(jié)點間的通信線路，邊上的權(quán)重表示兩節(jié)點間的距離，節(jié)點本身到他自己的距離記為0，如果兩節(jié)點沒有邊直接相連用 表示。利用Dijkstra算法實現(xiàn)求解最短路徑問題要有邊權(quán)。本文最佳路徑是基于兩個路由節(jié)點間的距離。因此找路由節(jié)點間的最短距離就轉(zhuǎn)化成了找圖G=（V,E）中指定兩點間的最小距離了。首先我們利用上圖可以知道節(jié)點之間的鄰接關(guān)系，為此我們可以先畫出節(jié)點間的鄰接矩陣，方便我們對節(jié)點的關(guān)系進(jìn)行了解。如下表（單位：m）：abcdeza0400200b400 0 100500c200100 08001000d5008000200600e10002000300z600

12、3000下面對最優(yōu)路徑進(jìn)行分析，我們a為路徑的起點，z為終點。初始化： L(a)=0 L(b)=，L(c)=，L(d)=，L(e)=，L(z)=， S=,一次迭代：U=a，S=a L(a)+W(a,b)=0+400=400<L(b) L(a)+W(a,c)=0+200=200<L(c) L(a)+W(a,d)=0+=L(a)+W(a,e)=0+=L(a)+W(a,z)=0+=L(b)=400, L(c)=200, L(d)= L(e)= L(z)= 二次迭代：U=c，S=a,c L(c)+W(c,b)=200+100=300<L(b) L(c)+W(c,d)=200+800=

13、1000<L(d) L(c)+W(c,e)=200+1000=1200<L(e) L(c)+W(c,z)=200+= L(b)=300， L(d)=1000， L(e)=1200，L(z)= 三次迭代：U=b，S=a，c，b L(b)+W(b,d)=300+500=800<L(d) L(b)+W(b,e)=300+=> L(b)+W(b,z)=300+= L(d)=800， L(e)=1200, L(z)= 四次迭代：U=d，S=a，c，b，d L(d)+W(d,e)=800+200=1000<L(e) L(d)+W(d,z)=800+600=1400<L(

14、z) L(e)=1000， L(z)=1400五次迭代：U=e，S=a，c，b，d，e L(e)+W(e,z)=1000+300=1300<L(z) L(z)=1300結(jié)束：U=z，S=a，c，b，d，e，z由于終點z已經(jīng)進(jìn)入S集合中所以迭代結(jié)束。這樣就找到了從起點a到終點z的最短路徑以及到中間各點的最短路徑。本文的算法是在VC+的環(huán)境下實現(xiàn)的，程序的基本思想是基于Dijkstra算法的。這個程序中是以節(jié)點1代表a，且以節(jié)點1作為初始節(jié)點，節(jié)點6最為終止節(jié)點，在程序中所求的最短路徑問題則為從節(jié)點1到節(jié)點6以及其他中間節(jié)點的最短路徑5。具體的程序代碼見附錄。圖2運(yùn)行結(jié)果第三章 結(jié)論通過本學(xué)

15、期對圖論及其算法的學(xué)習(xí)，使我深刻體會到了圖論在實際生活中的廣泛應(yīng)用，也使從以前的定向思維上升了一個臺階，學(xué)會把抽象的變?yōu)榫唧w，能用點、線、圖來描述抽象的事物，把很多抽象的知識具體化，使得抽象的知識更容易理解、記憶。圖論及其算法中有很多簡便的算法，可以實現(xiàn)很多功能。Dijkstra算法是圖論眾多算法中的一種，能夠方便的找到兩點之間的最短路徑，通過上面Dijkstra算法的應(yīng)用例子可以清楚的看到通過Dijkstra算法可以在很復(fù)雜的圖中很容易的找到點到點的最短路徑，也可以對實際生活中的一些問題給予很大的幫助。參考文獻(xiàn)1 樂陽,龔健雅;Dijkstra最短路徑算法的一種高效率實現(xiàn)J;武漢測繪科技大學(xué)

16、學(xué)報;1999年03期.2 殷劍宏，吳開亞；圖論及其算法，中國科學(xué)技術(shù)大學(xué)出版社；2005.3 王樹禾.圖論M.北京：科學(xué)出版社.2009.4 凡金偉,呂康.基于Dijkstra算法在物流配送中的應(yīng)用J.電腦編程技巧與維護(hù),2009,(04).5 徐鳳生，李天志.所有最短路徑的求解算法J.微計算機(jī)應(yīng)用，2004，25（3）：295-300.附錄#include<iostream.h>#include<stdio.h>#define MaxNum 10000 /節(jié)點間不是鄰居節(jié)點#define n 6/節(jié)點數(shù)目int dist100; /到節(jié)點1的最短路徑值int sta

17、te100=0; /節(jié)點被搜索過狀態(tài)指示int data100100; /鄰接矩陣int path100;/從起點到終點的最短路徑，0為沒在集合，從1開始int indexflag=1; /查找權(quán)值最小的節(jié)點int first=1; /起點int end=7; /終點int findmin() int minnode=0, min=MaxNum; for(int i=1; i<=n; i+) if (disti<min) && (!statei) /statei為1時表明該節(jié)點入網(wǎng)了 min=disti; minnode=i; return minnode;void

18、 main() long int datan+1n+1= 0,0,0,0,0,0,0, 0,0,400,200,10000,10000,10000, 0,400,0,100,500,10000,1000, 0,200,100,0,800,1000,10000, 0,10000,500,800,0,200,600, 0,10000,10000,1000,200,0,300, 0,10000,10000,10000,600,300,0 ; /*初始化*/ for(int i=1; i<=n; i+) disti=data1i; pathi=0; statefirst=1; int done=1; while (done<n) int node=findmin(); if (node!=0) done+; /找到一個點就加1 statenode=1; /標(biāo)記已經(jīng)找到