Dijkstra算法的優(yōu)化

第30卷第22期計算機工程2004年11月VoL30N22Computer EngineeringNovember 2004●人工智能及識別技術(shù)●文章編號: 1000 -24000-01- -02文獻標識碼: A中圈分類(lèi)號: TP311Dijkstra算法的優(yōu)化余冬梅，張秋余，少林,方邕(蘭州理工大學(xué)電信學(xué)院，蘭州730050)摘要:在求解最優(yōu)路徑時(shí)經(jīng)常使用經(jīng)典的Dijkstrm算法，但在實(shí)際應用當中計算最優(yōu)路徑時(shí)非常消耗內存空間和計算時(shí)間。在物資籌供決策系統的開(kāi)發(fā)過(guò)程中，結合實(shí)際應用情況，對Dijkstra算法進(jìn)行 了優(yōu)化，大大降低了內存消耗和計算時(shí)間。最后利用C++語(yǔ)言對算法進(jìn)行了詳細的算法描述。關(guān)鍵詞: Dijksra; 最短路徑; C++Optimized Dijkstra AlgorithmYU Dongmei, ZHANG Qiuyu, MA Shaolin, FANG Ting(College of Telecommunication, Lanzhou University of Technology, Lanzhou 730050)[Abstract] In shot path calcuating, Dijkstra algorithm is used, but it needs more memory and computer time. In the developmcnt of material providedecision making systen , the pape optimizes the Djkstra algorihm, it saves much memory and calculating time, and describcs it with C++ language.[Kcy words] Dijkstra; Shortest path; C++Djjkstra算法是圖論中求最短路徑的一個(gè)著(zhù)名的算法，論簡(jiǎn)單圖(無(wú)環(huán)和重邊)。使用改進(jìn)算法求從頂點(diǎn)V0(稱(chēng)為源使用其可以求得圖中-一點(diǎn)到其他 各頂點(diǎn)的最短路徑樹(shù)，但在點(diǎn))到其它各頂點(diǎn)的最短路徑長(cháng)度和所經(jīng)過(guò)的最短路徑，存實(shí)際應用當中，使用Dijkstra算法耗費大量的內存空間和計儲結構如下。算時(shí)間，雖然有很多人對Dijkstra算法提出了一些改進(jìn)的算(1)用鏈表數組MGraph來(lái)存儲矩陣G。將鄰接矩陣的每法，但都沒(méi)有達到最理想的結果。作者在《物資籌供決策系一行用一個(gè)單鏈表來(lái)表示，鏈表中只有非∞的元素，每個(gè)節統》開(kāi)發(fā)過(guò)程中，根據實(shí)際情況對D算法在存儲空間和計算點(diǎn)有兩個(gè)元素，一個(gè)為所在的列值，一個(gè)為此點(diǎn)的權值，圖時(shí)間上均做了優(yōu)化，使Djkstra算法 在求解最短路徑時(shí)達到1中無(wú)向圖的存儲格式如圖2所示。時(shí)間下限。1 Dijkstra算法描述Djkstra提出了一個(gè)按路徑長(cháng)度遞增的次序產(chǎn)生最短路4|徑的算法，首先引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D[]為弧上的權值，否則置D[i為∞。顯然，長(cháng)度為D[] = Min{D3[i]|vi∈V}的路徑就是從v出發(fā)的長(cháng)度最短的一-條最短路徑。此路徑為(，vi)。圜I無(wú)向圈假設下一條長(cháng)度次短的最短路徑的終點(diǎn)是vk，則可想G1而知，這條路徑或者是(v, vk),或者是(v, v, vk)。它的長(cháng)度2+2T ]T囚或者是從v到vk的弧上的權值，或者是Dj]和從vj到vk的弧上的權值之和。[G--般情況下，假設S為已經(jīng)求得最短路徑的終點(diǎn)集合，4+241 JF@工3F>331則可證明:下一條最短路徑(設其終點(diǎn)為x)或者是弧(v, x)，65+2T子口或者是中間只經(jīng)過(guò)S中的頂點(diǎn)而最后到達頂點(diǎn)x的路徑。這可用反證法來(lái)證明。假設此路徑上有一個(gè)頂點(diǎn)不在S中，則圈2存儲格式說(shuō)明存在一- 條終點(diǎn)不在S而長(cháng)度比此路徑短的路徑。但是這其C++代碼如下描述:是不可能的，因為我們是按路徑長(cháng)度遞增的次序來(lái)產(chǎn)生各最typeder struct {短路徑的，故此長(cháng)度比此路徑短的所有路徑均已產(chǎn)生,它們MNode * next;的終點(diǎn)必定在S中，即假設不成立。因此在-一般情況下，下}MNode;一條長(cháng)度次短的最短路徑的長(cháng)度必是class MCraph/鄰接矩陣Di] = Min{D[i] |vi∈V_S }public:其中，D[i]或者是弧(V, vi)上的權值，或者是D[](vk∈S)和上的權值之和。中國煤化工= curent;}2優(yōu)化后的存儲結構MHCNMHG設一個(gè)帶權有向圖為G, G=(V, T),其中V為頂點(diǎn)集作者簡(jiǎn)介:余冬梅(1953-),女副教授，主研方向:軟件總線(xiàn);合，T為邊的集合。G中頂點(diǎn)數為,該算法中的圖C限于討張秋余，教授;馬少林、方霆， 碩士生收稿日期: 2003-09-26E-mail: msl _uck@hotmail.com-145--void SetFirst(MNode *p){ first = p:current = first;}{MNode* GotfFirt(ifirst){urrent = frstreturm current;}D[pnode~>r] = pnode~>v;else return NULL;}ChainNode *|= new Node);void Add(MNode *p){current->next=p; current=p;}.>r - pnode>r,MNode *Necx()ifcurrnen->nex(){urreat = current->next;p[pnode->r] = v0;return curent;}else retum NULL:}L.AddTaiK);pnode = pnode->next; }(2)一維數組D來(lái)存儲各頂點(diǎn)到V0的最短距離。while(L.IsEmpty()(3)用一維數組P來(lái)存儲前驅點(diǎn)。min = INFINITY;(4)用-一個(gè)輔助雙向鏈表，用來(lái)存儲正在參與比較的節cn2 = L.First();點(diǎn),使用雙向鏈表的目的是在刪除節點(diǎn)時(shí)降低時(shí)間復雜度。while(en2)}{其C++代碼如下描述:i(D[cn2>r]r;Node◆next,◆prev;min = D[w];}}ChainNode;cn2 = L.Next();class Path {L. Delete(cn/)//刪除已經(jīng)找到最短的節點(diǎn)public:pnode = G[w]frst;ChainNode first,current;while(pnode)int n;{i{D[pnode->)] > (min+ pnode->V))Path(){n=0; current = NULL; first = NULL;}{iD[pnode~>r] == INFINITY)void StFirst(ChainNode* p){frst = p; current = first; n=;}{ChainNode * pNode = new ChainNode);ChainNode* Fist({fitcturrent-firstelse current=pNode->r“pnode->r;NUL:; retum curent}LAdTail(pNode);void AddTai(ChainNode *p){current->next=p:p->prev=D[pnode~>r] = min+pnode->v;current;curent=p; n++;}int Delete(ChainNode *p);p[pnode->r} =w;ChainNode *Next){if(curnext){curent = current->pnode- pnode->next; } }next;returm current;}elsc return NULL}return true; }bool IsEmpty(){retum n==0;}4復雜度分析3優(yōu)化后的算法(1)空間復雜度分析:由于采用了鏈表數組，因此空間實(shí)際應用中的鄰接矩陣大多是稀疏矩陣,在計算過(guò)程中復雜度為0(T), T為有向圖的邊數，對于最差情況下如果有大量的∞參與計算，所以改進(jìn)算法的主要思路就是消除冗T=n?,那么空間復雜度為0(m7)。氽存儲和冗余計算。(2)時(shí)間復雜度分析:用一個(gè)鏈表數組MGraph G[]來(lái)表示鄰接矩陣，算法I)步驟l)的復雜度為0(n)。2)步驟2)的復雜度為0(n)。步驟如下:(1)將與v0直接相連的節點(diǎn)的D[vi]初始化為其權值,其3)步驟3),第一次循環(huán)的次數為與v0直接相連的頂點(diǎn)的個(gè)數nI,第二次循環(huán)次數為n1-I再加上與第一次找到的頂點(diǎn)直接相連且余的置為機器所允許的最大值。與v0的距離為無(wú)窮大的節點(diǎn)的個(gè)數。以此類(lèi)推直到L中的節點(diǎn)個(gè)數(2)將與v0直接相連的頂點(diǎn)加入到鏈表Path中。為零為止。最壞情況下如果v0與其余個(gè)頂點(diǎn)都有直接相連，那么每(3)在Path中找到權值最小的節點(diǎn)w,并在Path中刪除此次循環(huán)的次數為-1).(-2...1,那么時(shí)間復雜度為-1-+-+2+..+頂點(diǎn)，如果剩余節點(diǎn)數為0則結束。即為0(n)。(4)修改最短路徑:在G里與w直接相連的其余各節點(diǎn)vi4)步驟4)的時(shí)間復雜度為0(T),對于任何最短路徑算法必須至的權值中比較D[vi]與D[w]+s(w,vi)的大小，如果D[vi]小于少對每條邊檢查一次，因為任何一條邊都有可能在最短路徑中，因D[w]+s(w,vi) ,并且如果D[vi]為∞則將vi加入到Path中，然此步驟4)的時(shí)間復雜度為O(T)，當T=n?時(shí)， 復雜度為0(n2)，與Dijkstn算法相同。后將P[vi]的前驅設置為w，并修改最短路徑D[vi]= D[w]+因此優(yōu)化后的算法最壞時(shí)間復雜度為max{O(n),O(T),s(w,vi)。 重復步驟(2)。0(m)},即為0(m)。改進(jìn)后的算法C++源代碼如下:5結論bool ShortestPath OptDU(MGraph *G,int n, int v0, /PrevPoint*/優(yōu)化后的算法經(jīng)過(guò)在物資籌供決策系統的實(shí)際應用，算int *p/*ShortPathTable*/ int *D){ int w,imin;法的時(shí)間復雜度與Dijkstra算法- -樣， 但在T<n ) retum fsl:/trow OutOfBounds();多堵文獻for(i=0;i