資源描述：
《求最短路徑的新算法》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、CN4321258/TP計(jì)算機(jī)工程與科學(xué)2006年第28卷第2期ISSN10072130XCOMPUTERENGINEERING&SCIENCEVol128,No12,2006文章編號:10072130X(2006)02200832033求最短路徑的新算法TheNewAlgorithmforFindingtheShortestPaths徐鳳生XUFeng2sheng(德州學(xué)院計(jì)算機(jī)系,山東德州253023)(DepartmentofComputerScienceandTechnology,DezhouUniversity,Dez
2、hou253023,China)摘要:本文提出了一種求最短路徑的新算法,并用C語言設(shè)計(jì)相應(yīng)的程序驗(yàn)證了此算法。實(shí)驗(yàn)表明,該算法能高效地求出一個(gè)頂點(diǎn)到其它各頂點(diǎn)的所有最短路徑。Abstract:Anewalgorithmforfindingtheshortestpathshasbeenputforwardinthispaper.Alltheshortestpathsfromonenodetoalltheothernodescanbederivedquicklybyusingthealgorithm.Thealgorithmisve
3、rifiedandimplementedbyarelevantCprogram.關(guān)鍵詞:最短路徑;Dijkstra算法;鄰接矩陣Keywords:shortestpath;Dijkstraalgorithm;adjacentmatrix中圖分類號:TP301.6文獻(xiàn)標(biāo)識碼:A?,vm∈V,邊(或弧)e1,e2,?,em∈E,其中vi-1、vi是ei的1引言結(jié)點(diǎn),序列v0v1?vm稱為連接v0到vm的路,記為v0v1?vm。路中邊的數(shù)目稱為該路的秩。ω01+ω12+?+ω(n-1)n最短路徑問題是圖論中研究的一個(gè)重要課題,它廣泛稱
4、為該路的長度。所有連接v0到vm的路中長度最小的路應(yīng)用于交通、網(wǎng)絡(luò)尋優(yōu)等領(lǐng)域。最短路徑問題要解決的就稱為v0到vm的最短路徑。是求加權(quán)圖G=中兩給定頂點(diǎn)之間的最短路通常的無向圖和有向圖可以看成是加權(quán)圖的特例。[1]徑。求最短路徑的一個(gè)著名算法是Dijkstra算法,它可定義2給定簡單加權(quán)圖G=,V={v0,以求出圖中從一個(gè)頂點(diǎn)到其它各頂點(diǎn)的最短路徑的長度及v1,?,vn-1},稱A=(aij)為圖G的鄰接矩陣,其中:一條最短路徑。但是,該算法具有其局限性,不能求出從一ωij,若vi和vj之間有邊相連個(gè)
5、頂點(diǎn)到其它各頂點(diǎn)的所有最短路徑。1965年,EliOlin2aij=∞,若vi和vj之間無邊相連ick和D.K.Smith等就求出所有最短路徑這一問題進(jìn)行了0,若i=j一些簡單的探討,但這些探討過于簡單且不完整。針對Di2ωij表示vi和vj之間邊的權(quán)值。jkstra算法的局限性,孫強(qiáng)等人在文獻(xiàn)[2]中給出了一種解求最短路徑最著名的算法是Dijkstra算法,其基本思決方案,但其使用的數(shù)據(jù)結(jié)構(gòu)形式較為復(fù)雜。文獻(xiàn)[3]提出了一種新的解決方案,但其求解過程仍然十分繁瑣。本文想是按路徑長度遞增的次序產(chǎn)生最短路徑,可由下式給出:在對最短
6、路徑問題進(jìn)行了分析和探討的基礎(chǔ)上,提出了一D[i]=min{D[i],D[i]+ωji}種新的求從一個(gè)頂點(diǎn)到其它各頂點(diǎn)的所有最短路徑的算Dijkstra算法具有其局限性,它只能求出一條最短路法。與文獻(xiàn)[2,3]給出的算法相比,本文的算法具有數(shù)據(jù)結(jié)徑,而不能求出所有最短路徑。構(gòu)形式簡單、求解方便且比較直觀等特點(diǎn)。3算法與實(shí)例2相關(guān)概念本文提出了一種求最短路徑的新算法,其基本思想與定義1給定簡單加權(quán)圖G=,設(shè)v0,v1,Dijkstra算法一致,但它克服了Dijkstra算法的不足之處,3收稿日期:2004209201
7、;修訂日期:2004210222基金項(xiàng)目:德州市科學(xué)技術(shù)攻關(guān)計(jì)劃資助項(xiàng)目(040705)作者簡介:徐鳳生(1965),男,山東聊城人,教授,研究方向?yàn)閿?shù)據(jù)挖掘、數(shù)據(jù)庫技術(shù)、數(shù)據(jù)結(jié)構(gòu)和算法。通訊地址:253023山東省德州市德州學(xué)院計(jì)算機(jī)系;Tel:(0534)8985635;E2mail:xfs@dzu.edu.cnAddress:DepartmentofComputerScienceandTechnology,DezhouUniversity,Dezhou,Shandong253023,P.R.China83能夠快速地求出一個(gè)
8、頂點(diǎn)到其它各頂點(diǎn)的所有最短路徑。表3修正P為了敘述方便,首先引入以下記號并作相應(yīng)的約定。v0v1v2v3v4(1)向量D的每個(gè)分量D[i]表示當(dāng)前所找到的從始v0021∞∞點(diǎn)v0到每個(gè)終點(diǎn)vi的最短路徑的長度。v110112v22203∞(2)向量S的每個(gè)分量S
