Dijkstra算法的優(yōu)化研究

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