最短路問題及其應用

大連海事大學圖論論文姓名：學號：專業(yè)：計算機科學與技術院系：信息科學技術2009級摘要：關鍵字:主要介紹最短路的兩種算法，迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。以及這兩種關鍵字:圖論，最短路徑，樹，生成樹，迪杰斯特拉(Dijkstra)，弗羅伊德(Floyd)算法最短路問題及其應用1引言圖論是應用數(shù)學的一個分支，它的概念和結果來源非常廣泛，最早起源于一些數(shù)學游戲的難題研究，如歐拉所解決的哥尼斯堡七橋問題，以及在民間廣泛流傳的一些游戲難題，如迷宮問題、博弈問題、棋盤上馬的行走路線問題等.這些古老的難題，當時吸引了很多學者的注意.在這些問題研究的基礎上又繼續(xù)提出了著名的四色猜想和漢米爾頓（環(huán)游世界）數(shù)學難題.1847年，圖論應用于分析電路網絡，這是它最早應用于工程科學，以后隨著科學的發(fā)展，圖論在解決運籌學，網絡理論，信息論，控制論，博弈論以及計算機科學等各個領域的問題時，發(fā)揮出越來越大的作用.在實踐中，圖論已成為解決自然科學、工程技術、社會科學、軍事等領域中許多問題的有力工具之一。最短路問題是圖論理論的一個經典問題。尋找最短路徑就是在指定網絡中兩結點間找一條距離最小的路。最短路不僅僅指一般地理意義上的距離最短，還可以引申到其它的度量，如時間、費用、線路容量等。最短路徑算法的選擇與實現(xiàn)是通道路線設計的基礎,最短路徑算法是計算機科學與地理信息科學等領域的研究熱點，很多網絡相關問題均可納入最短路徑問題的范疇之中。經典的圖論與不斷發(fā)展完善的計算機數(shù)據(jù)結構及算法的有效結合使得新的最短路徑算法不斷涌現(xiàn)。2最短路2.1最短路的定義對最短路問題的研究早在上個世紀60年代以前就卓有成效了,其中對賦權圖^w,,>0）的有效算法是由荷蘭著名計算機專家E.W.Dijkstra在1959年首次提出的，該算法能夠解決兩指定點間的最短路,也可以求解圖G中一特定點到其它各頂點的最短路。后來海斯在Dijkstra算法的基礎之上提出了海斯算法。但這兩種算法都不能解決含有負權的圖的最短路問題。因

此由Ford提出了Ford算法，它能有效地解決含有負權的最短路問題。但在現(xiàn)實生活中，我們所遇到的問題大都不含負權，所以我們在(七>0)的情況下選擇Dijkstra算法。定義①1若圖G=G(V,E)中各邊e都賦有一個實數(shù)W(e)，稱為邊e的權，則稱這種圖為賦權圖，記為G=G(V,E,W)。定義②2若圖G=G(V,E)是賦權圖且W(e)>0,eeE(G),若u是匕到七的路W(u)的權,則稱W(u)為u的長，長最小的％到匕的路W(u)稱為最短路。若要找出從v到v的通路u，使全長最短，即minW(u)=ZW(e)。in2.2最短路問題算法的基本思想及基本步驟e滬2.2最短路問題算法的基本思想及基本步驟在求解網絡圖上節(jié)點間最短路徑的方法中,目前國內外一致公認的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。這兩種算法中，網絡被抽象為一個圖論中定義的有向或無向圖，并利用圖的節(jié)點鄰接矩陣記錄點間的關聯(lián)信息。在進行圖的遍歷以搜索最短路徑時,以該矩陣為基礎不斷進行目標值的最小性判別,直到獲得最后的優(yōu)化路徑。Dijkstra算法是圖論中確定最短路的基本方法,也是其它算法的基礎。為了求出賦權圖中任意兩結點之間的最短路徑，通常采用兩種方法。一種方法是每次以一個結點為源點,重復執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時間復雜度為O婦)，雖然與重復執(zhí)行Dijkstra算法n次的時間復雜度相同，但其形式上略為簡單，且實際運算效果要好于前者。Dijkstra算法基本步驟③:令：s={v.},i=1,S={v2,v3,,v}W(v)=0并令*T(v)=；vesjj1、對ves，求minT(v),W(v)+w}=T(v)。jj.ijj2、求minTET(v)，使T(v)=minT(v)}jkkjvjesvjvjes令W(v)=T(v)kk3、若vk=v^則已找到V1到vn的最短路距離W(vj，否則令i=k從s中刪去V,轉1這樣經過有限次迭代則可以求出七到Vn的最短路線，可以用一個流程圖來表示:這樣經過有限次迭代則可以求出七到Vn的最短路線，可以用一個流程圖來表示:第一步先取W(vi)=0意即V］到V］的距離為0,而T(vj)是對T(vj)所賦的初值。第二步利用W(v)已知，根據(jù)minT(v),W(v)+w｝對T(v)進行修正。ijiijj第三步對所有修正后的T(v,)求出其最小者T(vk)。其對應的點vk是v］所能一步到達的點v,中最近的一個，由于所有W(u)>0。因此任何從其它點v,中轉而到達vk的通路上的距離都大于v］直接到vk的距離T(vj,因此T(七)就是v］到vk的最短距離，所以在算法中令W(vk)=T“)并從s中刪去vk,若k=n則W(v^)=W(Tn)就是七到v〃的最短路線,計算結束。否則令匕二V回到第二步，繼續(xù)運算,直到卜n為止。這樣每一次迭代,得到七到一點v的最短距離，重復上述過程直到丁v。ijFloyd算法的基本原理和實現(xiàn)方法為:如果一個矩陣D=_d」其中j0表示i與j間的距離,若i與J間無路可通，則』為無窮大。i與J間的最短距離存在經過i與J間的上和不經過ijk兩種情況，所以可以令k=1,2,3,…,n,n（n為節(jié)點數(shù)）。檢查"與門+匕的值,在此,門與"分別為目前所知的i到k與k到j的最短距離,因此,d^+dkj就是i到j經過k的最短距離。所以，若有d>d+d，就表示從i出發(fā)經k再到j的距離要比原來的i到j距離短,自然ijikkj把i到j的^重寫成dk+d*每當一個k搜索完,d〃就是目前i到j的最短距離。重復這一過程，最后當查完所有k時,d就為i到j的最短距離。ijij3最短路的應用3.1在運輸網絡中的應用④設6個城市v,v,…,v之間的一個公路網（圖1）每條公路為圖中的邊，邊上的權數(shù)表示該126段公路的長度（單位:百公里）,設你處在城市V1，那么從V1到V6應選擇哪一路徑使你的費用最省。解:首先設每百公里所用費用相同,求v1到v6的費用最少，既求v1到v6的最短路線。為了方便計算,先作出該網絡的距離矩陣,如下：[vv10v25v32v48v58v81v5015982L=v21081083v8580254v89102025v888520L6—1(0)設W(v)=0,T(v)=3,veS={v,v,v,v,v),1j23456(1)第一次迭代①計算T(v.),j=2,3,4,5,6如下T(v2)=minT(v),W(v)+w)=min{3,0+5)=5T(v3)=minT(v),W(v)+w)=min{3,0+2)=2T(v)=minT(v),W(v)+w)=min{3,0+3)=3T(v)=3,T(v)=3/②取minVjEST(v)}=2=T(v)令W(v)=T(v)=2

②取minVjES③由于k=3公(n=6)，令s={v,v,v,v},i=3轉(1)2456第二次迭代：算T(v.),j=2,4,5,6如下T(vj=minT(v),W(v)+w}=min{5,2+1)=3T(vj=minT(v),W(v)+w}=min{8,2+8}=8T(v5)=minT(v),W(v)+w}=min{10,2+10)=10T(v6)=minT(v),W(v)+w)=min{3,2+3)=3取min{T(v))=3=T(v)令W(v)=T(v)=3j222—ves③由于k=2公(n=6),令s={v4,v5,v6)i=2轉(1)第三次迭代：算T(v.),j=4,5,6如下T(vj=minT(v),W(v)+w)=min{8,3+5)=8T(v5)=minT(v),W(v)+w)=min{10,3+9)=10T(v)=36取min{T(v))=8=T(v),W(v)=T(v)=8j444—ves③由于k=4公(n=6)，令i={七,七}i=4轉(1)第四次迭代：①算T(v^),j=5,6如下T(v5)=minT(v),W(v)+w}=min{10,2+8)=10T(v6)=min{T(v),W(v)+w}=min{“,8+5)=13②取min{T(v)}=10=T(v),W(v)=T(v)=10j555—③由于k=5公(n=6),令s={v}轉(1)6第五次迭代：①算T(v.),j=6如下T(v6)=minT(v6),W(v5)+w56}=min{13,10+2)=12②由于k=6=n。因此已找到v1到v6的最短距離為12。計算結束。找最短路線:逆向追蹤得vTvTvTvTvTv132456最短距離為12,即從城市v1到城市v6的距離最短,即費用最省。3.2在艦船通道路線設計中的應用⑤利用圖論的經典理論和人群流量理論研究艦船人員通道路線的優(yōu)化設計及最優(yōu)線路選擇。首先介紹圖論相關理論，對船舶通道進行路網抽象，建立網絡圖，然后根據(jù)人群流動的相關理論，選取不同擁擠情況下的人員移動速度，從而確定各條路段（包括樓梯）的行程時間。以行程時間作為通道網絡的路權，得出路阻矩陣以選擇一對起點7終點的最短時間路線為目標，建立最短路徑問題的數(shù)學模型，利用經典的Floyd算法確定最短路徑。將此方法應用于某艦艇多層甲板的通道網絡中,計算結果并進行討論，最后在此研究的基礎上對通道設計相關問題的深化和拓展進行了探討和總結,并提出設想。路線優(yōu)化技術通常采用圖論中的“圖”來表示路網，船舶通道路網與圖論的路網對應關系為:結點通道的交叉口或斷頭路的終點；邊兩結點之間的路段稱為邊,若規(guī)定了路段的方向，則稱為弧;邊（弧）的權路段某個或某些特征屬性的量化表示。路權的標定決定了最短的路徑搜索依據(jù)，也就是搜索指標。根據(jù)不同的最優(yōu)目標,可以選擇不同的路段屬性。由于艦船上除了平面上的通道之外還有垂直方向的樓梯（或直梯）,如果以最短路程距離作為優(yōu)化目標,路線的效率未必最高（距離最短未必耗時最少）。所以，以最短行程時間作為優(yōu)化的目標，道路權重即為各路段的平均行程時間。對于要研究的對象，取各條通道的起點（或終點）和交叉點為圖的頂點，各路段為邊，路權為路段行走的平均時間。尋找從起點到終點的最短時間路徑即為最優(yōu)路徑。在規(guī)定了結點、邊和權值以后，便將路網抽象為一個賦權無向圖或賦權有向圖，從而確定路網中某兩地間的最優(yōu)路線便轉化為圖論中的最短路徑問題。首先將空間問題抽象為圖，圖2為某艦的兩層甲板的部分抽象圖，上下兩個平面上縱橫交錯的直線為各層甲板的主要通道，連接兩層甲板的直線表示樓梯，包括2個直梯和3個斜梯。每條路段上的標注（a，b）中,a表示路段實際長度或者樓梯的類型，m;b表示此路段的行程時間（即路權）,s如（40,32）。圖2兩層甲板的部分抽象圖圖3賦權圖再利用上述求最短的方法即可求得需要的通道路線。3.3其他應用最短路徑問題在交通網絡結構的分析，交通運輸線路（公路、鐵路、河流航運線、航空線、管道運輸線路等）的選擇，通訊線路的建造與維護，運輸貨流的最小成本分析，城公共交通網絡的規(guī)劃等，都有直接應用的價值。最短路徑問題在實際中還常用于汽車導航系統(tǒng)以及各種應急系統(tǒng)等（如110報警、119火警以及120醫(yī)療救護系統(tǒng)）這些系統(tǒng)一般要求計算出到出事地點的最佳路線的時間應該在15一35內，在行車過程中還需要實時計算出車輛前方的行駛路線，這就決定了最短路徑問題的實現(xiàn)應該是高效率的。在很多目標信息引導系統(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算法，首先計算出任一指定位置點距各疏導出口的最短路徑樹，進而通過編制輔助方向指示箭頭程序.動態(tài)地將火災事故現(xiàn)場救生疏導路徑引導圖加以顯示，從而達到優(yōu)化目標引導路徑的目的.按照城鄉(xiāng)運輸一體化的總體思路，為實現(xiàn)農村村村通客車的目標，針對農村客運線路繁雜，節(jié)點眾多的特點，布局優(yōu)化農村公路客運網的規(guī)劃和建設是農村發(fā)展的重要內容，為落實貫徹中央2004年l號文件，解決三農問題，全面建設小康社會，實現(xiàn)人便于行，貨暢其流。需要從規(guī)劃布局的角度，科學地審視農村公路網和客運線路。村村通客車，是農村客運網的基本要求，但農村村屯點多面廣，線路繁雜，網絡節(jié)點眾多，道路迂回曲折。如何科學合理的選擇路徑，即達到農村客運網絡暢達便捷，合理布局即是關鍵問題。現(xiàn)有的客運線路，系依托路網，村屯自然經濟和區(qū)域特點，經經營者申報，交通運政管理部門審批而形成；其路徑是否合理，線路覆蓋和便捷程度，總體資源配置是否優(yōu)化，尚無完整定量分析，系統(tǒng)和路網是否科學等一系列問題還有待確定。4結語本文將最短路理論應用到實際生活中，尤其是在艦船通道路線中的應用具有很重要的意義。將實際生活中出現(xiàn)的安全隱患盡量降低。同時也凸顯出學習和應用最短路問題原理的重要性。另外，最短路問題在城市道路建設、物資供應站選址等問題上也有很重要的作用。分析和研究最短路問題趨于熱門化。參考文獻：【1】卜月華圖論及其應用南京：東南大學出版社，2000【2】基于圖論的艦船通道路線優(yōu)化余為波王濤2008【3】最短路問題在運輸網絡中的應用李玲200