最短路問題及其應用——最短路徑

1、大連海事大學圖論論文 姓名：學號：專業(yè)：計算機科學與技術院系：信息科學技術2009級摘要： 主要介紹最短路的兩種算法，迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。以及這兩種算法在實際問題中的應用和比較。關鍵字：圖論，最短路徑，樹，生成樹，迪杰斯特拉(Dijkstra)，弗羅伊德(Floyd)算法最短路問題及其應用1 引言圖論是應用數(shù)學的一個分支，它的概念和結(jié)果來源非常廣泛，最早起源于一些數(shù)學游戲的難題研究，如歐拉所解決的哥尼斯堡七橋問題，以及在民間廣泛流傳的一些游戲難題，如迷宮問題、博弈問題、棋盤上馬的行走路線問題等 這些古老的難題，當時吸引了很多學者的注意在這些問題研究的基礎

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

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

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

5、圖的遍歷以搜索最短路徑時,以該矩陣為基礎不斷進行目標值的最小性判別,直到獲得最后的優(yōu)化路徑。Dijkstra算法是圖論中確定最短路的基本方法,也是其它算法的基礎。為了求出賦權圖中任意兩結(jié)點之間的最短路徑,通常采用兩種方法。一種方法是每次以一個結(jié)點為源點,重復執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法,其時間復雜度為,雖然與重復執(zhí)行Dijkstra算法n次的時間復雜度相同,但其形式上略為簡單,且實際運算效果要好于前者。Dijkstra算法基本步驟：令：并令：1、 對，求。2、 求得，使=令3、若則已找到到的最短路距離，否則令從中刪去轉(zhuǎn)1這樣經(jīng)過有限次迭

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

7、過兩種情況,所以可以令,n(n為節(jié)點數(shù))。檢查與的值,在此,與分別為目前所知的到與到的最短距離,因此,就是到經(jīng)過的最短距離。所以,若有,就表示從出發(fā)經(jīng)再到的距離要比原來的到距離短,自然把到的重寫成。每當一個搜索完,就是目前到的最短距離。重復這一過程,最后當查完所有時,就為到的最短距離。3 最短路的應用3.1在運輸網(wǎng)絡中的應用設6個城市之間的一個公路網(wǎng)(圖1)每條公路為圖中的邊,邊上的權數(shù)表示該段公路的長度(單位:百公里),設你處在城市,那么從到應選擇哪一路徑使你的費用最省。解:首先設每百公里所用費用相同,求到的費用最少,既求到的最短路線。為了方便計算,先作出該網(wǎng)絡的距離矩陣,如下:(0)設,(

8、1)第一次迭代計算如下取,令由于,令轉(zhuǎn)(1)第二次迭代:算如下取令由于,令轉(zhuǎn)(1)第三次迭代:算如下取由于,令轉(zhuǎn)(1)第四次迭代:算如下取由于,令轉(zhuǎn)(1)第五次迭代:算如下由于。因此已找到到的最短距離為12。計算結(jié)束。找最短路線:逆向追蹤得最短距離為12,即從城市到城市的距離最短,即費用最省。3.2在艦船通道路線設計中的應用利用圖論的經(jīng)典理論和人群流量理論研究艦船人員通道路線的優(yōu)化設計及最優(yōu)線路選擇。首先介紹圖論相關理論,對船舶通道進行路網(wǎng)抽象,建立網(wǎng)絡圖,然后根據(jù)人群流動的相關理論,選取不同擁擠情況下的人員移動速度,從而確定各條路段(包括樓梯)的行程時間。以行程時間作為通道網(wǎng)絡的路權，得出路

9、阻矩陣以選擇一對起點/終點的最短時間路線為目標,建立最短路徑問題的數(shù)學模型,利用經(jīng)典的Floyd算法確定最短路徑。將此方法應用于某艦艇多層甲板的通道網(wǎng)絡中,計算結(jié)果并進行討論,最后在此研究的基礎上對通道設計相關問題的深化和拓展進行了探討和總結(jié),并提出設想。路線優(yōu)化技術通常采用圖論中的“圖”來表示路網(wǎng),船舶通道路網(wǎng)與圖論的路網(wǎng)對應關系為:結(jié)點通道的交叉口或斷頭路的終點;邊兩結(jié)點之間的路段稱為邊,若規(guī)定了路段的方向,則稱為弧;邊(弧)的權路段某個或某些特征屬性的量化表示。路權的標定決定了最短的路徑搜索依據(jù),也就是搜索指標。根據(jù)不同的最優(yōu)目標,可以選擇不同的路段屬性。由于艦船上除了平面上的通道之外還

10、有垂直方向的樓梯(或直梯),如果以最短路程距離作為優(yōu)化目標,路線的效率未必最高(距離最短未必耗時最少)。所以,以最短行程時間作為優(yōu)化的目標,道路權重即為各路段的平均行程時間。對于要研究的對象,取各條通道的起點(或終點)和交叉點為圖的頂點,各路段為邊,路權為路段行走的平均時間。尋找從起點到終點的最短時間路徑即為最優(yōu)路徑。在規(guī)定了結(jié)點、邊和權值以后,便將路網(wǎng)抽象為一個賦權無向圖或賦權有向圖,從而確定路網(wǎng)中某兩地間的最優(yōu)路線便轉(zhuǎn)化為圖論中的最短路徑問題。首先將空間問題抽象為圖,圖2為某艦的兩層甲板的部分抽象圖,上下兩個平面上縱橫交錯的直線為各層甲板的主要通道,連接兩層甲板的直線表示樓梯,包括2個直梯

11、和3個斜梯。每條路段上的標注中,表示路段實際長度或者樓梯的類型,m;b表示此路段的行程時間(即路權),s如(40,32)。圖2 兩層甲板的部分抽象圖圖3 賦權圖再利用上述求最短的方法即可求得需要的通道路線。3.3 其他應用l 最短路徑問題在交通網(wǎng)絡結(jié)構的分析，交通運輸線路(公路、鐵路、河流航運線、航空線、管道運輸線路等)的選擇，通訊線路的建造與維護，運輸貨流的最小成本分析，城公共交通網(wǎng)絡的規(guī)劃等，都有直接應用的價值。l 最短路徑問題在實際中還常用于汽車導航系統(tǒng)以及各種應急系統(tǒng)等(如110報警、119火警以及120醫(yī)療救護系統(tǒng))這些系統(tǒng)一般要求計算出到出事地點的最佳路線的時間應該在15一35內(nèi)，

12、在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現(xiàn)應該是高效率的。l 在很多目標信息引導系統(tǒng)的設計中需要獲得最優(yōu)化路徑引導信息。例如，在日益增多的高層建筑、大型公共建筑(超級市場、博物館、醫(yī)院、游樂場等)場臺的火災事故現(xiàn)場救生疏導系統(tǒng)，需要根據(jù)現(xiàn)場情況動態(tài)地為逃生者實時提供最短的安全通道指引信息；而當這些場合發(fā)生盜竊、搶劫等突發(fā)犯罪事件時，安全監(jiān)控系統(tǒng)如能為警方實時提供通向罪犯所處位置最短搜索路徑信息則可以達到迅速制止犯罪的目的。在設計一個大型高層建筑火災事故現(xiàn)場救生疏導系統(tǒng)時，將圖論中Dijkstra算法應用于目標信息引導系統(tǒng)的設計中，通過Dijkstra算法，首先

13、計算出任一指定位置點距各疏導出口的最短路徑樹，進而通過編制輔助方向指示箭頭程序動態(tài)地將火災事故現(xiàn)場救生疏導路徑引導圖加以顯示，從而達到優(yōu)化目標引導路徑的目的l 按照城鄉(xiāng)運輸一體化的總體思路，為實現(xiàn)農(nóng)村村村通客車的目標，針對農(nóng)村客運線路繁雜，節(jié)點眾多的特點，布局優(yōu)化農(nóng)村公路客運網(wǎng)的規(guī)劃和建設是農(nóng)村發(fā)展的重要內(nèi)容，為落實貫徹中央2004年l號文件，解決三農(nóng)問題，全面建設小康社會，實現(xiàn)人便于行，貨暢其流。需要從規(guī)劃布局的角度，科學地審視農(nóng)村公路網(wǎng)和客運線路。村村通客車，是農(nóng)村客運網(wǎng)的基本要求，但農(nóng)村村屯點多面廣，線路繁雜，網(wǎng)絡節(jié)點眾多，道路迂回曲折。如何科學合理的選擇路徑，即達到農(nóng)村客運網(wǎng)絡暢達便捷

14、，合理布局即是關鍵問題。 現(xiàn)有的客運線路，系依托路網(wǎng)，村屯自然經(jīng)濟和區(qū)域特點，經(jīng)經(jīng)營者申報，交通運政管理部門審批而形成；其路徑是否合理，線路覆蓋和便捷程度，總體資源配置是否優(yōu)化，尚無完整定量分析，系統(tǒng)和路網(wǎng)是否科學等一系列問題還有待確定。4 結(jié)語本文將最短路理論應用到實際生活中，尤其是在艦船通道路線中的應用具有很重要的意義。將實際生活中出現(xiàn)的安全隱患盡量降低。同時也凸顯出學習和應用最短路問題原理的重要性。另外，最短路問題在城市道路建設、物資供應站選址等問題上也有很重要的作用。分析和研究最短路問題趨于熱門化。參考文獻：【1】 卜月華 圖論及其應用 南京：東南大學出版社，2000【2】 基于圖論的艦船通道路線優(yōu)化 余為波 王濤 2008【3】 最短路問題在運輸網(wǎng)絡中的應用 李玲 2006【4】 戴文舟. 交通網(wǎng)絡中最短路徑算法的研究 D . 重慶大學碩士學位論文 ,2004.【5】 謝灼利,等.地鐵車站站臺火災中人員的安全疏散J.中國安全科學學報 ,20