圖論最短路徑分析及應(yīng)用(共7頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 最短路徑問題分析及應(yīng)用 專 業(yè)： 信息與計算科學(xué) 班 級： 同組成員： 2012年06月23日·北京摘要： 主要介紹最短路的兩種算法，迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。以及這兩種算法在實際問題中的應(yīng)用和比較。關(guān)鍵詞：圖論，最短路徑，迪杰斯特拉(Dijkstra)，弗羅伊德(Floyd)最短路問題及其應(yīng)用1 引言圖論是應(yīng)用數(shù)學(xué)的一個分支，它的概念和結(jié)果來源非常廣泛，最早起源于一些數(shù)學(xué)游戲的難題研究，如歐拉所解決的哥尼斯堡七橋問題，以及在民間廣泛流傳的一些游戲難題，如迷宮問題、博弈問題、棋盤上馬的行走路線問題等 這些古老的難題，當(dāng)時吸

2、引了很多學(xué)者的注意在這些問題研究的基礎(chǔ)上又繼續(xù)提出了著名的四色猜想和漢米爾頓（環(huán)游世界）數(shù)學(xué)難題 1847年，圖論應(yīng)用于分析電路網(wǎng)絡(luò)，這是它最早應(yīng)用于工程科學(xué)，以后隨著科學(xué)的發(fā)展，圖論在解決運(yùn)籌學(xué)，網(wǎng)絡(luò)理論，信息論，控制論，博弈論以及計算機(jī)科學(xué)等各個領(lǐng)域的問題時，發(fā)揮出越來越大的作用在實踐中，圖論已成為解決自然科學(xué)、工程技術(shù)、社會科學(xué)、軍事等領(lǐng)域中許多問題的有力工具之一。 最短路問題是圖論理論的一個經(jīng)典問題。尋找最短路徑就是在指定網(wǎng)絡(luò)中兩結(jié)點間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短,還可以引申到其它的度量,如時間、費(fèi)用、線路容量等。最短路徑算法的選擇與實現(xiàn)是通道路線設(shè)計的基

3、礎(chǔ),最短路徑算法是計算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域的研究熱點,很多網(wǎng)絡(luò)相關(guān)問題均可納入最短路徑問題的范疇之中。經(jīng)典的圖論與不斷發(fā)展完善的計算機(jī)數(shù)據(jù)結(jié)構(gòu)及算法的有效結(jié)合使得新的最短路徑算法不斷涌現(xiàn)。2 最短路2.1 最短路的定義對最短路問題的研究早在上個世紀(jì)60年代以前就卓有成效了,其中對賦權(quán)圖的有效算法是由荷蘭著名計算機(jī)專家E.W.Dijkstra在1959年首次提出的,該算法能夠解決兩指定點間的最短路,也可以求解圖G中一特定點到其它各頂點的最短路。后來海斯在Dijkstra算法的基礎(chǔ)之上提出了海斯算法。但這兩種算法都不能解決含有負(fù)權(quán)的圖的最短路問題。因此由Ford提出了Ford算法,它能有效地

4、解決含有負(fù)權(quán)的最短路問題。但在現(xiàn)實生活中,我們所遇到的問題大都不含負(fù)權(quán),所以我們在的情況下選擇Dijkstra算法。定義1若圖G=G(V,E)中各邊e都賦有一個實數(shù)W(e),稱為邊e的權(quán),則稱這種圖為賦權(quán)圖,記為G=G(V,E,W)。定義2若圖G=G(V,E)是賦權(quán)圖且,若u是到的路的權(quán),則稱為的長,長最小的到的路稱為最短路。若要找出從到的通路,使全長最短,即。2.2 最短路問題算法的基本思想及基本步驟在求解網(wǎng)絡(luò)圖上節(jié)點間最短路徑的方法中,目前國內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。這兩種算法中,網(wǎng)絡(luò)被抽象為一個圖論中定義的有向或無向圖,并利用圖的

5、節(jié)點鄰接矩陣記錄點間的關(guān)聯(lián)信息。在進(jìn)行圖的遍歷以搜索最短路徑時,以該矩陣為基礎(chǔ)不斷進(jìn)行目標(biāo)值的最小性判別,直到獲得最后的優(yōu)化路徑。Dijkstra算法是圖論中確定最短路的基本方法,也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點之間的最短路徑,通常采用兩種方法。一種方法是每次以一個結(jié)點為源點,重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法,其時間復(fù)雜度為,雖然與重復(fù)執(zhí)行Dijkstra算法n次的時間復(fù)雜度相同,但其形式上略為簡單,且實際運(yùn)算效果要好于前者。Dijkstra算法基本步驟：令：并令：1、 對，求2、 求得，使令3、 若則已找到到的最短路距離

6、，否則令從中刪去轉(zhuǎn)1這樣經(jīng)過有限次迭代則可以求出到的最短路線，可以用一個流程圖來表示：第一步 先取意即到的距離為0，而是對所賦的初值。第二步 利用已知，根據(jù)對進(jìn)行修正。第三步 對所有修正后的求出其最小者。其對應(yīng)的點是所能一步到達(dá)的店中最近的一個，由于所有。因此任何從其它點中轉(zhuǎn)而到達(dá)的通路上的距離都大于直接到的距離，因此就是到的最短距離，所以在算法中令并從s中刪去，若k=n則就是到的最短路線，計算結(jié)束。否則令回到第二部，計算運(yùn)算，直到k=n為止。這樣每一次迭代，得到到一點的最短距離，重復(fù)上述過程直到。Floyd算法的基本原理和實現(xiàn)方法為：如果一個矩陣其中表示i與j間的距離，若i與j間無路可通，則

7、為無窮大。i 和j間的最短距離存在經(jīng)過i和j間的k和不經(jīng)過k兩種情況，所以可以令n(n為節(jié)點數(shù))。檢查與的值，在此，與分別為目前所知的i到k與k到j(luò)的最短距離，因此，就是i到j(luò)經(jīng)過k的最短距離。所以，若有就表示從i出發(fā)經(jīng)k再到j(luò)的距離要比原來的i到j(luò)距離短，自然把i到j(luò)的寫成。每當(dāng)一個k搜索完，就是目前i到j(luò)的最短距離。重復(fù)這一過程，最后當(dāng)查完所有k時，就為i到j(luò)的最短距離。3 最短路的應(yīng)用例2 從北京（Pe）乘飛機(jī)到東京(T)、紐約(N)、墨西哥城(M)、倫敦(L)、巴黎(Pa)五城市做旅游，每城市恰去一次再回北京，應(yīng)如何安排旅游線，使旅程最短？各城市之間的航線距離如下表：LMNPaPeTL

8、5635215160M5621577870N3521366868Pa2157365161Pe5178685113T6070686113解：編寫程序如下：clc,cleara(1,2)=56;a(1,3)=35;a(1,4)=21;a(1,5)=51;a(1,6)=60;a(2,3)=21;a(2,4)=57;a(2,5)=78;a(2,6)=70;a(3,4)=36;a(3,5)=68;a(3,6)=68;a(4,5)=51;a(4,6)=61;a(5,6)=13;a(6,:)=0;a=a+a'c1=5 1:4 6;L=length(c1);flag=1;while flag>0

9、 flag=0; for m=1:L-3 for n=m+2:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endcircle=c1;sum=sum1;c1=5 6 1:4;%改變初始圈，該算法的最后一個頂點不動flag=1;while flag>0 flag=0; for m=1:L-3 for n=m+2

10、:L-1 if a(c1(m),c1(n)+a(c1(m+1),c1(n+1)<. a(c1(m),c1(m+1)+a(c1(n),c1(n+1) flag=1; c1(m+1:n)=c1(n:-1:m+1); end end endendsum1=0;for i=1:L-1 sum1=sum1+a(c1(i),c1(i+1);endif sum1<sum sum=sum1; circle=c1;endcircle,sum4 結(jié)語本文將最短路理論應(yīng)用到實際生活中，同時也凸顯出學(xué)習(xí)和應(yīng)用最短路問題原理的重要性。另外，最短路問題在城市道路建設(shè)、物資供應(yīng)站選址等問題上也有很重要的作用。分析和研究最短路問題趨于熱門化。參考文獻(xiàn)：【1】 卜月華 圖論及其應(yīng)用 南京：東南大學(xué)出版社，2000【2】 基于圖論的艦船通道路線優(yōu)化 余為波 王濤 2008【3】 最短路問題在運(yùn)輸網(wǎng)絡(luò)中的應(yīng)用 李玲 2006【4】 戴文舟. 交通網(wǎng)絡(luò)中最短路徑算法的研究 D . 重慶大學(xué)碩士學(xué)位論文 ,2004.【5】 謝灼利,等.地鐵車站站臺火災(zāi)中人員的安全疏散J.中國安全科學(xué)學(xué)報 ,2004,14(7):21.【6】 榮瑋.基于道路網(wǎng)的最短路徑算法的研究與實現(xiàn).武漢理工大學(xué)碩士學(xué)位論文D,2005.【7】 朱建青