科技研究Dijkstra算法的優(yōu)化研究馬翠杰孫曉琳煙臺南山學(xué)院物流學(xué)院山東煙臺265713[摘要]D1jkstra算法是典型最短路算法，用于計(jì)算網(wǎng)絡(luò)圖中一個節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑。但由于它計(jì)算所經(jīng)過的的節(jié)點(diǎn)很多，并且會有很多重復(fù)計(jì)算的步驟,所以效率低。本文主要從算法所需要計(jì)算的主要步驟來考慮，提出可能節(jié)省時間的一些有效措施。!關(guān)鍵詞]Dijkstra算法最短路徑[ Abstract I Dijkstra algorithm is a typical Algorithm used to calculate the shortest path.It Calculstes from one node to the other nodes to resut to theshortest path.But because it traveis among too much nodes,that it is low fficiency.This article Consider the main steps calculated to make it much easy切0 save time and become much effective.[Key Words ] agritm of Dinksra;The shoret Dath中圈分類號: TP39文獻(xiàn)標(biāo)識碼: B文章編號: 1009 4672011)03-94-010Dijkstra算法用于求解- -個有 向圖(也可以是無向圖.無向園是有向圈d+w.d,的一種特例)的一個點(diǎn)(稱之為原點(diǎn))到其余各點(diǎn)(稱之為周邊點(diǎn))的最短如果滿足條件再記下有向邊(v,"),依次繼續(xù),直到得到有向邊(v,路徑問題。算法主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展,直到尋找到到目v、)為止。如果不滿足.則返問到終點(diǎn)Vt的其它先行節(jié)點(diǎn)循環(huán)進(jìn)行反向追蹤。的節(jié)點(diǎn)為止。Dijkstra算法能得出最短路徑的最優(yōu)解，Dijikstra算法可以直到得到從v。到v,的最短路徑:看做是廣度優(yōu)先搜索的變種"也可以被認(rèn)為是啟發(fā)性搜索的特例,Djikstraμ=(vv).-,(v,v) -.v,v.算法所采用的一“致代價搜索在人工智能中稱為貪心搜索策略,它是初級的啟三算法的特點(diǎn)與改進(jìn)方法發(fā)性搜索策略。Diktra遍歷計(jì)算的節(jié)點(diǎn)數(shù)目很多.所以需要的時間相對比較長,對于一一、算法思想些少節(jié)點(diǎn)的圖尚可應(yīng)用,對于-些節(jié)點(diǎn)數(shù)日非常多的網(wǎng)絡(luò)閱就滿要重復(fù)計(jì)算該算法的主要思想是,假設(shè)已經(jīng)求出從v,到v,的最短路徑μ "如下:很多次，顯得非常麻煩.為此,我們可以考慮采取以下幾點(diǎn)措施:在整個計(jì)算過程中,我們可以考慮做完第一步之后,去尋找最后一 -個節(jié)點(diǎn)根據(jù)最短路徑的性質(zhì),從vs沿u "到v,或者v、的路,就是vs到v或者v。vt,看一下它的先行節(jié)點(diǎn)有哪些,然后,再返回到第一步的計(jì)算結(jié)果,來對比vt的最短路徑。這就是說u "不僅是起點(diǎn)V,到終點(diǎn)v,的最短路，而且從起點(diǎn)v,的先行節(jié)點(diǎn)號是否跟得出的非無窮路徑里的節(jié)點(diǎn)號有重復(fù)的。如果有,則提到終點(diǎn)v_上任意中間點(diǎn)的最短路也在對應(yīng)節(jié)點(diǎn)的山'上。為了求得v,到v的取這--路徑,作為- -個備選路徑。然后按正常的第二步計(jì)算第二次迭代,在第最短路，可以先求出vs到每-一個中間點(diǎn)的最短路,然后逐步擴(kuò)展到找終點(diǎn)V。二次迭代之后,繼續(xù)對比v,的先行節(jié)點(diǎn)號是否跟得出的非無窮路徑里的節(jié)點(diǎn)二、算法過程號有重復(fù)的。如果有，則提取這-路徑,作為- -個備選路徑。在計(jì)算過程中,需要將已經(jīng)求出到起點(diǎn)最短路的點(diǎn)與尚未求出到起點(diǎn)最如此循環(huán),- -直到vt的先行 節(jié)點(diǎn)全部找到為止,然后在這些備選路徑里短路的點(diǎn)區(qū)別開來,以順序執(zhí)行選代。這個問題呵以用不同的標(biāo)號來解決,即選擇最短路徑,同時也就知道了最短路徑的中間節(jié)點(diǎn)。從vs開始,對每個頂點(diǎn)給以不同的標(biāo)號.在這種算法中一般有兩類標(biāo)號:臨這樣計(jì)算可以減少很多計(jì)算步驟, 省略很多非先行節(jié)點(diǎn)。個人認(rèn)為可以時標(biāo)號Lj和永久標(biāo)號dj, LJ表示從起點(diǎn)到被標(biāo)號vj的最短路權(quán)的一個數(shù)值，適當(dāng)?shù)奶岣咚惴ǖ男?。但不一定是最短的路?dj表示從vs開始到被標(biāo)號點(diǎn)vj的真正對短路權(quán).具Dijksta算法在上述計(jì)算過程中可以找到起點(diǎn)到其他點(diǎn)的最短路徑,同體步驟如下:時我們還可以在Dijkstra算法的基礎(chǔ)上作-些擴(kuò)展, 有時候，我們希望在求得1. k=1,d, (1) =0,L (1) =w。(j≠s)。N={v}最短路徑的基礎(chǔ)上還可以列出一些次短的路徑,或者是找到路徑的序列。為2.將各Ljk中數(shù)值最小者對應(yīng)的頂點(diǎn)標(biāo)號x的改成永久性標(biāo)號,即:此,可先在原圖上計(jì)算出最短路徑,然后從圖中刪去該最短路徑中的某-條Dxk)=min{L()}邊,在余下的子圖中重新計(jì)算最短路徑。對于原每條最短路徑中的每一條邊，3.如果N={vy}則算法終止。d, x)就是從v,到v,的最短路的權(quán)。均可求得一條刪去該邊后f圖的最短路徑，,這些最短路徑路徑經(jīng)排序后即為4.如果未能找到最終節(jié)點(diǎn),則需要繼續(xù)迭代,令k=k+1,對每一_個v,∈原圖的一系列次短路徑。N.的頂點(diǎn)由下述方法修改其標(biāo)號:即對每一條弧(Vv,v)令:參考文獻(xiàn)u (u) =min({Q(",dx (-1 +wj}(1]軍.郭耀煌:《物流配送車輛調(diào)度理論與方法景,中國物資出版社。5.反向追蹤[2]郭耀煌: 《運(yùn)籌學(xué)原理與方法》,西南交通大學(xué)出版社.從最后頂點(diǎn)vt開始反向?qū)ふ?先看終點(diǎn)t的先行節(jié)點(diǎn)中是否存在一點(diǎn)作者簡介-點(diǎn)vj使?jié)M足1.馮翠杰(1983一),女,山東濰坊人,煙臺南山學(xué)院教師,硬士,主要研d+w,=d,究方向:工程測量，工程管理. .如果有,則記下有向邊(v,v)然后再從vj開始尋求它的先行節(jié)點(diǎn)vi使:2.孫曉琳。(1982-),女山東煙臺,助教,工學(xué)碩士.(接上頁)圖像分割是圖像分析的重要環(huán)節(jié),也是計(jì)算機(jī)視覺的重要研究方[1]楊潤玲, 高新流,介軍.一種基于模糊聚類的快速圖像分割算法[J].面。本文在對模糊C均值緊類算法和區(qū)城生長算法進(jìn)行分析的基礎(chǔ)上,提出了西安建筑科技大學(xué)學(xué)報:自然科學(xué)版, 2007, 39 (2): 280-285.-種將模糊C均值聚類 算法與區(qū)域生長算法相結(jié)合的混合分割方法。該算法[2] BEZDEKJ C.Paltern recognition with objective function能夠有效地提高分割區(qū)城的完整性.實(shí)驗(yàn)結(jié)果表明該方法能夠取得好的分割algorithms (w]. New York: Plenun Press, 1981.效果。[3] wAN SY.HIGGINS v. Symetric region growing []. IEEB Trans-標(biāo)準(zhǔn)的區(qū)域生長算法要依賴于用戶進(jìn)行交互輸入,需要根據(jù)生長結(jié)果不actions on Imare Process ing.2003. 12 (9): 1007.斷地對闢值參數(shù)進(jìn)行調(diào)整,闊值過大可能導(dǎo)致過生長,國值過小則叮能導(dǎo)致生中國煤化工圖像的分制([D].蘭州:蘭州長不完全。模糊C均值檠類算法同樣需要用戶交互輸人,以確定合理的聚類中心數(shù)。本文算法則是預(yù)先給定閾值參數(shù)進(jìn)行區(qū)城生長,隨后根據(jù)區(qū)城生長YHc N M H G欺群聚類的圖像分制()]. .確定的區(qū)域敷用模糊C均值聚類算法作后續(xù)的分割處理,使分割取得了較好算機(jī)應(yīng)用研究, 2008, 25 (5): 1579-1581.的結(jié)果。[6] RAFAEL C. Gonzalez, RICHARD E. Nwoods. 數(shù)字田像處理(MATLAB版)0].阮秋琦等,譯.北京:電子工業(yè)出版社，2005.94序黢穗務(wù)2011.03