基于dijkstra的最短路徑改進算法

《基于dijkstra的最短路徑改進算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在學術論文-天天文庫。

1、第!$卷第"期湖北汽車工業(yè)學院學報)*+,!$-*,""009年/月Q;E-A.<;?REN=(5E,;B;,(H=@ADE+,-(=+@A+,(,E,=QEA,"009基于!"#$%&’(的最短路徑改進算法羅理!王鋒!昆明理工大學信息工程與自動化學院#云南昆明/&00&$"摘要!針對如何利用’()*+,-.算法來高效地查找圖中任意兩結點之間的最短路徑這一問題#提出了"種優(yōu)化方法%其一是應用圖中各結點的出入度來簡化查找任意兩結點之間的最短路徑’其二是利用已求出的兩點之間的最短路徑來快速獲得其他結點之間的最短路徑$關鍵詞!最短路徑’最短路徑算法’’()*

2、+,-.算法’出入度中圖分類號!1230$4/文獻標識碼!5文章編號!$0067&863!"009"0"!00""!08!"#$%&’()*+%$,-."%/0.%$-12-34-.562’7%89,:;2-$6"#$"%#&’!()*!(!:;<<=>=;?@A?;-B.,(;ACA>(A==-(A>.AD5E,;B.,(;A#FEAB(A>GA(H=-+(,I;?JK(=AK=.AD1=KLA;<;>I#FEAB(A>/&00&#:L(A."<=2-$6>-%5(B(A>.,,L=M-;N<=B;?L;O,;B;-==??=K,(H=

3、L=+L;-,=+,M.,LN=,O==A.-N(,-.-I,O;A;D=+(A>-.MLNI,L=.<>;-(,LB;?’()*+,-.#,L=,O;;M,(B(P=DB=,L;D+O=-=N-;E>L,?;-O.-D#OL(KLO=-=.MM;E,!(AD=>-==;?A;D=+(A,L=>-.ML,;+(BM<(?I,L=+=.-KL;?,L=+L;-,=+,M.,LN=,O==A.-N(,-.-I,O;A;D=+.ADB.*(A>E+=;?>.(A=D.<-=.DI,L=+L;-,=+,M.,LN=,O==A,O;A;D=+,;>.(

4、A-.M(D,L=;,L=-A;D=+4?1@A%$(2%+L;-,=+,M.,L’.<>;-(,LB;?,L=+L;-,=+,M.,L’.<>;-(,LB;?’()*+,-.’;E,!(AD=>-==隨著社會的不斷進步#最短路徑算法在人們的是從固定的一個點到其他各點的最短路徑問題$但日常生活顯得越來越重要$比如%每天開車去上班#是在實際生活中往往要求解決的不只是固定一點應該選擇哪條公路才能使自己到公司的費用最低&到其他點的最短路徑#而是要求計算出任意兩點之時間最少#這是最短路徑的問題’在網(wǎng)絡路由中#怎間的最

5、短距離$針對這個問題#本文主要討論了怎樣選擇最優(yōu)的路由路徑#這也是最短路徑問題’在樣利用’()*+,-.算法優(yōu)化實現(xiàn)圖中任意兩點之間交通旅游&城市規(guī)劃以及電網(wǎng)架設中怎樣使其耗費的最短路徑問題$的資金最少#這還是最短路徑問題$由此可見對最短路徑問題的研究是非常有意義的$$基本思路最短路徑這一重要問題早在"#世紀初就已經(jīng)得到人們的高度重視#當時也有許多科學家研究這為了解決最短路徑問題#首先應根據(jù)要求選取一重要問題的求解方法$但直到$%&%年荷蘭計算一種量度標準$然后將!個輸入排成這種量度標準機科學家’()*+,-.!迪杰斯特拉"才給出這一問題求要求的順序#

6、按照這種順序一次輸入一個量$如果解的基本思想#并給出了算法$后來這個算法就成這個輸入和當前已經(jīng)構成的在這種量度意義的部了眾所周知的’()*+,-.算法#也成為了一代經(jīng)典$分最優(yōu)解加在一起能產(chǎn)生一個可行解#則把此輸入當時的’()*+,-.提出的這一算法主要解決的問題加到這部分最優(yōu)解中#否則不加入$這種能夠在某收稿日期!!""#!"$!%&作者簡介!羅理!%’(!!"#男#湖南長沙人#碩士生#主要從事網(wǎng)絡信息安全研究$第!!卷第"期羅理等,基于’()*+,-.的最短路徑改進算法!!"!種量度意義下得到最優(yōu)解的分級處理方法稱為貪!(根據(jù)’()*+,-.算法思

7、想!可以由圖中結點的心算法"出入度信息來提高各點之間最短路徑的查找速度&按照上面的思路!可以逐步地構造出這些最短"(在帶權圖中利用’()*+,-.算法找出部分結點路徑"使用迄今已經(jīng)生成的所有路徑長度之和作之間的最短路徑后!若其他還沒有找出最短路徑的為一種量度!為了使這一量度達到最小!單獨的每結點可以利用前面已找出的最短路徑信息為自己一條路徑都必須具有最小長度"使用這一量度標提供快速的最短路徑查找&準!假定已經(jīng)構造了!條最短路徑!則下面要構造"=!利用結點入度信息查找的路徑應該是下一條最短的最小長度路徑"根據(jù)結點的入度信息來優(yōu)化查找最短路徑的如何根據(jù)貪心

8、算法!確定路徑上的每個節(jié)點基本思想是,當某結點的入度為$時!圖中其他結而最終求得最短路徑!’(