最短路問題及其應(yīng)用

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

此由Ford提出了Ford算法，它能有效地解決含有負(fù)權(quán)的最短路問題。但在現(xiàn)實(shí)生活中，我們所遇到的問題大都不含負(fù)權(quán)，所以我們?cè)?七>0)的情況下選擇Dijkstra算法。定義①1若圖G=G(V,E)中各邊e都賦有一個(gè)實(shí)數(shù)W(e)，稱為邊e的權(quán)，則稱這種圖為賦權(quán)圖，記為G=G(V,E,W)。定義②2若圖G=G(V,E)是賦權(quán)圖且W(e)>0,eeE(G),若u是匕到七的路W(u)的權(quán),則稱W(u)為u的長(zhǎng)，長(zhǎng)最小的％到匕的路W(u)稱為最短路。若要找出從v到v的通路u，使全長(zhǎng)最短，即minW(u)=ZW(e)。in2.2最短路問題算法的基本思想及基本步驟e滬2.2最短路問題算法的基本思想及基本步驟在求解網(wǎng)絡(luò)圖上節(jié)點(diǎn)間最短路徑的方法中,目前國(guó)內(nèi)外一致公認(rèn)的較好算法有迪杰斯特拉(Dijkstra)及弗羅伊德(Floyd)算法。這兩種算法中，網(wǎng)絡(luò)被抽象為一個(gè)圖論中定義的有向或無向圖，并利用圖的節(jié)點(diǎn)鄰接矩陣記錄點(diǎn)間的關(guān)聯(lián)信息。在進(jìn)行圖的遍歷以搜索最短路徑時(shí),以該矩陣為基礎(chǔ)不斷進(jìn)行目標(biāo)值的最小性判別,直到獲得最后的優(yōu)化路徑。Dijkstra算法是圖論中確定最短路的基本方法,也是其它算法的基礎(chǔ)。為了求出賦權(quán)圖中任意兩結(jié)點(diǎn)之間的最短路徑，通常采用兩種方法。一種方法是每次以一個(gè)結(jié)點(diǎn)為源點(diǎn),重復(fù)執(zhí)行Dijkstra算法n次。另一種方法是由Floyd于1962年提出的Floyd算法，其時(shí)間復(fù)雜度為O婦)，雖然與重復(fù)執(zhí)行Dijkstra算法n次的時(shí)間復(fù)雜度相同，但其形式上略為簡(jiǎn)單，且實(shí)際運(yùn)算效果要好于前者。Dijkstra算法基本步驟③:令：s={v.},i=1,S={v2,v3,,v}W(v)=0并令*T(v)=；vesjj1、對(duì)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,轉(zhuǎn)1這樣經(jīng)過有限次迭代則可以求出七到Vn的最短路線，可以用一個(gè)流程圖來表示:這樣經(jīng)過有限次迭代則可以求出七到Vn的最短路線，可以用一個(gè)流程圖來表示:第一步先取W(vi)=0意即V］到V］的距離為0,而T(vj)是對(duì)T(vj)所賦的初值。第二步利用W(v)已知，根據(jù)minT(v),W(v)+w｝對(duì)T(v)進(jìn)行修正。ijiijj第三步對(duì)所有修正后的T(v,)求出其最小者T(vk)。其對(duì)應(yīng)的點(diǎn)vk是v］所能一步到達(dá)的點(diǎn)v,中最近的一個(gè)，由于所有W(u)>0。因此任何從其它點(diǎn)v,中轉(zhuǎn)而到達(dá)vk的通路上的距離都大于v］直接到vk的距離T(vj,因此T(七)就是v］到vk的最短距離，所以在算法中令W(vk)=T“)并從s中刪去vk,若k=n則W(v^)=W(Tn)就是七到v〃的最短路線,計(jì)算結(jié)束。否則令匕二V回到第二步，繼續(xù)運(yùn)算,直到卜n為止。這樣每一次迭代,得到七到一點(diǎn)v的最短距離，重復(fù)上述過程直到丁v。ijFloyd算法的基本原理和實(shí)現(xiàn)方法為:如果一個(gè)矩陣D=_d」其中j0表示i與j間的距離,若i與J間無路可通，則』為無窮大。i與J間的最短距離存在經(jīng)過i與J間的上和不經(jīng)過ijk兩種情況，所以可以令k=1,2,3,…,n,n（n為節(jié)點(diǎn)數(shù)）。檢查"與門+匕的值,在此,門與"分別為目前所知的i到k與k到j(luò)的最短距離,因此,d^+dkj就是i到j(luò)經(jīng)過k的最短距離。所以，若有d>d+d，就表示從i出發(fā)經(jīng)k再到j(luò)的距離要比原來的i到j(luò)距離短,自然ijikkj把i到j(luò)的^重寫成dk+d*每當(dāng)一個(gè)k搜索完,d〃就是目前i到j(luò)的最短距離。重復(fù)這一過程，最后當(dāng)查完所有k時(shí),d就為i到j(luò)的最短距離。ijij3最短路的應(yīng)用3.1在運(yùn)輸網(wǎng)絡(luò)中的應(yīng)用④設(shè)6個(gè)城市v,v,…,v之間的一個(gè)公路網(wǎng)（圖1）每條公路為圖中的邊，邊上的權(quán)數(shù)表示該126段公路的長(zhǎng)度（單位:百公里）,設(shè)你處在城市V1，那么從V1到V6應(yīng)選擇哪一路徑使你的費(fèi)用最省。解:首先設(shè)每百公里所用費(fèi)用相同,求v1到v6的費(fèi)用最少，既求v1到v6的最短路線。為了方便計(jì)算,先作出該網(wǎng)絡(luò)的距離矩陣,如下：[vv10v25v32v48v58v81v5015982L=v21081083v8580254v89102025v888520L6—1(0)設(shè)W(v)=0,T(v)=3,veS={v,v,v,v,v),1j23456(1)第一次迭代①計(jì)算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轉(zhuǎn)(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轉(zhuǎn)(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轉(zhuǎn)(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}轉(zhuǎn)(1)6第五次迭代：①算T(v.),j=6如下T(v6)=minT(v6),W(v5)+w56}=min{13,10+2)=12②由于k=6=n。因此已找到v1到v6的最短距離為12。計(jì)算結(jié)束。找最短路線:逆向追蹤得vTvTvTvTvTv132456最短距離為12,即從城市v1到城市v6的距離最短,即費(fèi)用最省。3.2在艦船通道路線設(shè)計(jì)中的應(yīng)用⑤利用圖論的經(jīng)典理論和人群流量理論研究艦船人員通道路線的優(yōu)化設(shè)計(jì)及最優(yōu)線路選擇。首先介紹圖論相關(guān)理論，對(duì)船舶通道進(jìn)行路網(wǎng)抽象，建立網(wǎng)絡(luò)圖，然后根據(jù)人群流動(dòng)的相關(guān)理論，選取不同擁擠情況下的人員移動(dòng)速度，從而確定各條路段（包括樓梯）的行程時(shí)間。以行程時(shí)間作為通道網(wǎng)絡(luò)的路權(quán)，得出路阻矩陣以選擇一對(duì)起點(diǎn)7終點(diǎn)的最短時(shí)間路線為目標(biāo)，建立最短路徑問題的數(shù)學(xué)模型，利用經(jīng)典的Floyd算法確定最短路徑。將此方法應(yīng)用于某艦艇多層甲板的通道網(wǎng)絡(luò)中,計(jì)算結(jié)果并進(jìn)行討論，最后在此研究的基礎(chǔ)上對(duì)通道設(shè)計(jì)相關(guān)問題的深化和拓展進(jìn)行了探討和總結(jié),并提出設(shè)想。路線優(yōu)化技術(shù)通常采用圖論中的“圖”來表示路網(wǎng)，船舶通道路網(wǎng)與圖論的路網(wǎng)對(duì)應(yīng)關(guān)系為:結(jié)點(diǎn)通道的交叉口或斷頭路的終點(diǎn)；邊兩結(jié)點(diǎn)之間的路段稱為邊,若規(guī)定了路段的方向，則稱為弧;邊（?。┑臋?quán)路段某個(gè)或某些特征屬性的量化表示。路權(quán)的標(biāo)定決定了最短的路徑搜索依據(jù)，也就是搜索指標(biāo)。根據(jù)不同的最優(yōu)目標(biāo),可以選擇不同的路段屬性。由于艦船上除了平面上的通道之外還有垂直方向的樓梯（或直梯）,如果以最短路程距離作為優(yōu)化目標(biāo),路線的效率未必最高（距離最短未必耗時(shí)最少）。所以，以最短行程時(shí)間作為優(yōu)化的目標(biāo)，道路權(quán)重即為各路段的平均行程時(shí)間。對(duì)于要研究的對(duì)象，取各條通道的起點(diǎn)（或終點(diǎn)）和交叉點(diǎn)為圖的頂點(diǎn)，各路段為邊，路權(quán)為路段行走的平均時(shí)間。尋找從起點(diǎn)到終點(diǎn)的最短時(shí)間路徑即為最優(yōu)路徑。在規(guī)定了結(jié)點(diǎn)、邊和權(quán)值以后，便將路網(wǎng)抽象為一個(gè)賦權(quán)無向圖或賦權(quán)有向圖，從而確定路網(wǎng)中某兩地間的最優(yōu)路線便轉(zhuǎn)化為圖論中的最短路徑問題。首先將空間問題抽象為圖，圖2為某艦的兩層甲板的部分抽象圖，上下兩個(gè)平面上縱橫交錯(cuò)的直線為各層甲板的主要通道，連接兩層甲板的直線表示樓梯，包括2個(gè)直梯和3個(gè)斜梯。每條路段上的標(biāo)注（a，b）中,a表示路段實(shí)際長(zhǎng)度或者樓梯的類型，m;b表示此路段的行程時(shí)間（即路權(quán)）,s如（40,32）。圖2兩層甲板的部分抽象圖圖3賦權(quán)圖再利用上述求最短的方法即可求得需要的通道路線。3.3其他應(yīng)用最短路徑問題在交通網(wǎng)絡(luò)結(jié)構(gòu)的分析，交通運(yùn)輸線路（公路、鐵路、河流航運(yùn)線、航空線、管道運(yùn)輸線路等）的選擇，通訊線路的建造與維護(hù)，運(yùn)輸貨流的最小成本分析，城公共交通網(wǎng)絡(luò)的規(guī)劃等，都有直接應(yīng)用的價(jià)值。最短路徑問題在實(shí)際中還常用于汽車導(dǎo)航系統(tǒng)以及各種應(yīng)急系統(tǒng)等（如110報(bào)警、119火警以及120醫(yī)療救護(hù)系統(tǒng)）這些系統(tǒng)一般要求計(jì)算出到出事地點(diǎn)的最佳路線的時(shí)間應(yīng)該在15一35內(nèi)，在行車過程中還需要實(shí)時(shí)計(jì)算出車輛前方的行駛路線，這就決定了最短路徑問題的實(shí)現(xiàn)應(yīng)該是高效率的。在很多目標(biāo)信息引導(dǎo)系統(tǒng)的設(shè)計(jì)中.需要獲得最優(yōu)化路徑引導(dǎo)信息。例如，在日益增多的高層建筑、大型公共建筑（超級(jí)市場(chǎng)、博物館、醫(yī)院、游樂場(chǎng)等）場(chǎng)臺(tái)的火災(zāi)事故現(xiàn)場(chǎng)救生疏導(dǎo)系統(tǒng)，需要根據(jù)現(xiàn)場(chǎng)情況動(dòng)態(tài)地為逃生者實(shí)時(shí)提供最短的安全通道指引信息；而當(dāng)這些場(chǎng)合發(fā)生盜竊、搶劫等突發(fā)犯罪事件時(shí)，安全監(jiān)控系統(tǒng)如能為警方實(shí)時(shí)提供通向罪犯所處位置最短搜索路徑信息.則可以達(dá)到迅速制止犯罪的目的。在設(shè)計(jì)一個(gè)大型高層建筑火災(zāi)事故現(xiàn)場(chǎng)救生疏導(dǎo)系統(tǒng)時(shí)，將圖論中Dijkstra算法應(yīng)用于目標(biāo)信息引導(dǎo)系統(tǒng)的設(shè)計(jì)中，通過Dijkstra算法，首先計(jì)算出任一指定位置點(diǎn)距各疏導(dǎo)出口的最短路徑樹，進(jìn)而通過編制輔助方向指示箭頭程序.動(dòng)態(tài)地將火災(zāi)事故現(xiàn)場(chǎng)救生疏導(dǎo)路徑引導(dǎo)圖加以顯示，從而達(dá)到優(yōu)化目標(biāo)引導(dǎo)路徑的目的.按照城鄉(xiāng)運(yùn)輸一體化的總體思路，為實(shí)現(xiàn)農(nóng)村村村通客車的目標(biāo)，針對(duì)農(nóng)村客運(yùn)線路繁雜，節(jié)點(diǎn)眾多的特點(diǎn)，布局優(yōu)化農(nóng)村公路客運(yùn)網(wǎng)的規(guī)劃和建設(shè)是農(nóng)村發(fā)展的重要內(nèi)容，為落實(shí)貫徹中央2004年l號(hào)文件，解決三農(nóng)問題，全面建設(shè)小康社會(huì)，實(shí)現(xiàn)人便于行，貨暢其流。需要從規(guī)劃布局的角度，科學(xué)地審視農(nóng)村公路網(wǎng)和客運(yùn)線路。村村通客車，是農(nóng)村客運(yùn)網(wǎng)的基本要求，但農(nóng)村村屯點(diǎn)多面廣，線路繁雜，網(wǎng)絡(luò)節(jié)點(diǎn)眾多，道路迂回曲折。如何科學(xué)合理的選擇路徑，即達(dá)到農(nóng)村客運(yùn)網(wǎng)絡(luò)暢達(dá)便捷，合理布局即是關(guān)鍵問題。現(xiàn)有的客運(yùn)線路，系依托路網(wǎng)，村屯自然經(jīng)濟(jì)和區(qū)域特點(diǎn)，經(jīng)經(jīng)營(yíng)者申報(bào)，交通運(yùn)政管理部門審批而形成；其路徑是否合理，線路覆蓋和便捷程度，總體資源配置是否優(yōu)化，尚無完整定量分析，系統(tǒng)和路網(wǎng)是否科學(xué)等一系列問題還有待確定。4結(jié)語本文將最短路理論應(yīng)用到實(shí)際生活中，尤其是在艦船通道路線中的應(yīng)用具有很重要的意義。將實(shí)際生活中出現(xiàn)的安全隱患盡量降低。同時(shí)也凸顯出學(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)用李玲200