基于Dijkstra的最短路徑改進(jìn)算法

《基于Dijkstra的最短路徑改進(jìn)算法》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在學(xué)術(shù)論文-天天文庫。

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

2、30$4/文獻(xiàn)標(biāo)識(shí)碼!5文章編號(hào)!$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、=+(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=+,;>.(A-.M(D,L=;,L=-A;D=+4?1@A%$(2%+L;

4、-,=+,M.,L’.<>;-(,LB;?,L=+L;-,=+,M.,L’.<>;-(,LB;?’()*+,-.’;E,!(AD=>-==隨著社會(huì)的不斷進(jìn)步#最短路徑算法在人們的是從固定的一個(gè)點(diǎn)到其他各點(diǎn)的最短路徑問題$但日常生活顯得越來越重要$比如%每天開車去上班#是在實(shí)際生活中往往要求解決的不只是固定一點(diǎn)應(yīng)該選擇哪條公路才能使自己到公司的費(fèi)用最低&到其他點(diǎn)的最短路徑#而是要求計(jì)算出任意兩點(diǎn)之時(shí)間最少#這是最短路徑的問題’在網(wǎng)絡(luò)路由中#怎間的最短距離$針對(duì)這個(gè)問題#本文主要討論了怎樣選擇最優(yōu)的路由路徑#這也是最短路徑問題’在樣利用’()*+,-.算法優(yōu)化實(shí)現(xiàn)圖中任意兩點(diǎn)之間交通旅游&城

5、市規(guī)劃以及電網(wǎng)架設(shè)中怎樣使其耗費(fèi)的最短路徑問題$的資金最少#這還是最短路徑問題$由此可見對(duì)最短路徑問題的研究是非常有意義的$$基本思路最短路徑這一重要問題早在"#世紀(jì)初就已經(jīng)得到人們的高度重視#當(dāng)時(shí)也有許多科學(xué)家研究這為了解決最短路徑問題#首先應(yīng)根據(jù)要求選取一重要問題的求解方法$但直到$%&%年荷蘭計(jì)算一種量度標(biāo)準(zhǔn)$然后將!個(gè)輸入排成這種量度標(biāo)準(zhǔn)機(jī)科學(xué)家’()*+,-.!迪杰斯特拉"才給出這一問題求要求的順序#按照這種順序一次輸入一個(gè)量$如果解的基本思想#并給出了算法$后來這個(gè)算法就成這個(gè)輸入和當(dāng)前已經(jīng)構(gòu)成的在這種量度意義的部了眾所周知的’()*+,-.算法#也成為了一代經(jīng)典$分最優(yōu)解加

6、在一起能產(chǎn)生一個(gè)可行解#則把此輸入當(dāng)時(shí)的’()*+,-.提出的這一算法主要解決的問題加到這部分最優(yōu)解中#否則不加入$這種能夠在某收稿日期!!""#!"$!%&作者簡(jiǎn)介!羅理!%’(!!"#男#湖南長(zhǎng)沙人#碩士生#主要從事網(wǎng)絡(luò)信息安全研究$第!!卷第"期羅理等,基于’()*+,-.的最短路徑改進(jìn)算法!!"!種量度意義下得到最優(yōu)解的分級(jí)處理方法稱為貪!(根據(jù)’()*+,-.算法思想!可以由圖中結(jié)點(diǎn)的心算法"出入度信息來提高各點(diǎn)之間最短路徑的查找速度&按照上面的思路!可以逐步地構(gòu)造出這些最短"(在帶權(quán)圖中利用’()*+,-.算法找出部分結(jié)點(diǎn)路徑"使用迄今已經(jīng)生成的所有路徑長(zhǎng)度之和作之間的最短路

7、徑后!若其他還沒有找出最短路徑的為一種量度!為了使這一量度達(dá)到最小!單獨(dú)的每結(jié)點(diǎn)可以利用前面已找出的最短路徑信息為自己一條路徑都必須具有最小長(zhǎng)度"使用這一量度標(biāo)提供快速的最短路徑查找&準(zhǔn)!假定已經(jīng)構(gòu)造了!條最短路徑!則下面要構(gòu)造"=!利用結(jié)點(diǎn)入度信息查找的路徑應(yīng)該是下一條最短的最小長(zhǎng)度路徑"根據(jù)結(jié)點(diǎn)的入度信息來優(yōu)化查找最短路徑的如何根據(jù)貪心算法!確定路徑上的每個(gè)節(jié)點(diǎn)基本思想是,當(dāng)某結(jié)點(diǎn)的入度為$時(shí)!圖中其他結(jié)而最終求得最短路徑!’(