第30卷第22期計算機工程2004年11月VoL30N22Computer EngineeringNovember 2004●人工智能及識別技術(shù)●文章編號: 1000 -24000-01- -02文獻標(biāo)識碼: A中圈分類號: TP311Dijkstra算法的優(yōu)化余冬梅，張秋余，少林,方邕(蘭州理工大學(xué)電信學(xué)院，蘭州730050)摘要:在求解最優(yōu)路徑時經(jīng)常使用經(jīng)典的Dijkstrm算法，但在實際應(yīng)用當(dāng)中計算最優(yōu)路徑時非常消耗內(nèi)存空間和計算時間。在物資籌供決策系統(tǒng)的開發(fā)過程中，結(jié)合實際應(yīng)用情況，對Dijkstra算法進行 了優(yōu)化，大大降低了內(nèi)存消耗和計算時間。最后利用C++語言對算法進行了詳細的算法描述。關(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算法是圖論中求最短路徑的一個著名的算法，論簡單圖(無環(huán)和重邊)。使用改進算法求從頂點V0(稱為源使用其可以求得圖中-一點到其他 各頂點的最短路徑樹，但在點)到其它各頂點的最短路徑長度和所經(jīng)過的最短路徑，存實際應(yīng)用當(dāng)中，使用Dijkstra算法耗費大量的內(nèi)存空間和計儲結(jié)構(gòu)如下。算時間，雖然有很多人對Dijkstra算法提出了一些改進的算(1)用鏈表數(shù)組MGraph來存儲矩陣G。將鄰接矩陣的每法，但都沒有達到最理想的結(jié)果。作者在《物資籌供決策系一行用一個單鏈表來表示，鏈表中只有非∞的元素，每個節(jié)統(tǒng)》開發(fā)過程中，根據(jù)實際情況對D算法在存儲空間和計算點有兩個元素，一個為所在的列值，一個為此點的權(quán)值，圖時間上均做了優(yōu)化，使Djkstra算法 在求解最短路徑時達到1中無向圖的存儲格式如圖2所示。時間下限。1 Dijkstra算法描述Djkstra提出了一個按路徑長度遞增的次序產(chǎn)生最短路4|徑的算法，首先引進一個輔助向量D，它的每個分量D[]為弧上的權(quán)值，否則置D[i為∞。顯然，長度為D[] = Min{D3[i]|vi∈V}的路徑就是從v出發(fā)的長度最短的一-條最短路徑。此路徑為(，vi)。圜I無向圈假設(shè)下一條長度次短的最短路徑的終點是vk，則可想G1而知，這條路徑或者是(v, vk),或者是(v, v, vk)。它的長度2+2T ]T囚或者是從v到vk的弧上的權(quán)值，或者是Dj]和從vj到vk的弧上的權(quán)值之和。[G--般情況下，假設(shè)S為已經(jīng)求得最短路徑的終點集合，4+241 JF@工3F>331則可證明:下一條最短路徑(設(shè)其終點為x)或者是弧(v, x)，65+2T子口或者是中間只經(jīng)過S中的頂點而最后到達頂點x的路徑。這可用反證法來證明。假設(shè)此路徑上有一個頂點不在S中，則圈2存儲格式說明存在一- 條終點不在S而長度比此路徑短的路徑。但是這其C++代碼如下描述:是不可能的，因為我們是按路徑長度遞增的次序來產(chǎn)生各最typeder struct {短路徑的，故此長度比此路徑短的所有路徑均已產(chǎn)生,它們MNode * next;的終點必定在S中，即假設(shè)不成立。因此在-一般情況下，下}MNode;一條長度次短的最短路徑的長度必是class MCraph/鄰接矩陣Di] = Min{D[i] |vi∈V_S }public:其中，D[i]或者是弧(V, vi)上的權(quán)值，或者是D[](vk∈S)和上的權(quán)值之和。中國煤化工= curent;}2優(yōu)化后的存儲結(jié)構(gòu)MHCNMHG設(shè)一個帶權(quán)有向圖為G, G=(V, T),其中V為頂點集作者簡介:余冬梅(1953-),女副教授，主研方向:軟件總線;合，T為邊的集合。G中頂點數(shù)為,該算法中的圖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)一維數(shù)組D來存儲各頂點到V0的最短距離。while(L.IsEmpty()(3)用一維數(shù)組P來存儲前驅(qū)點。min = INFINITY;(4)用-一個輔助雙向鏈表，用來存儲正在參與比較的節(jié)cn2 = L.First();點,使用雙向鏈表的目的是在刪除節(jié)點時降低時間復(fù)雜度。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)找到最短的節(jié)點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復(fù)雜度分析3優(yōu)化后的算法(1)空間復(fù)雜度分析:由于采用了鏈表數(shù)組，因此空間實際應(yīng)用中的鄰接矩陣大多是稀疏矩陣,在計算過程中復(fù)雜度為0(T), T為有向圖的邊數(shù)，對于最差情況下如果有大量的∞參與計算，所以改進算法的主要思路就是消除冗T=n?,那么空間復(fù)雜度為0(m7)。氽存儲和冗余計算。(2)時間復(fù)雜度分析:用一個鏈表數(shù)組MGraph G[]來表示鄰接矩陣，算法I)步驟l)的復(fù)雜度為0(n)。2)步驟2)的復(fù)雜度為0(n)。步驟如下:(1)將與v0直接相連的節(jié)點的D[vi]初始化為其權(quán)值,其3)步驟3),第一次循環(huán)的次數(shù)為與v0直接相連的頂點的個數(shù)nI,第二次循環(huán)次數(shù)為n1-I再加上與第一次找到的頂點直接相連且余的置為機器所允許的最大值。與v0的距離為無窮大的節(jié)點的個數(shù)。以此類推直到L中的節(jié)點個數(shù)(2)將與v0直接相連的頂點加入到鏈表Path中。為零為止。最壞情況下如果v0與其余個頂點都有直接相連，那么每(3)在Path中找到權(quán)值最小的節(jié)點w,并在Path中刪除此次循環(huán)的次數(shù)為-1).(-2...1,那么時間復(fù)雜度為-1-+-+2+..+頂點，如果剩余節(jié)點數(shù)為0則結(jié)束。即為0(n)。(4)修改最短路徑:在G里與w直接相連的其余各節(jié)點vi4)步驟4)的時間復(fù)雜度為0(T),對于任何最短路徑算法必須至的權(quán)值中比較D[vi]與D[w]+s(w,vi)的大小，如果D[vi]小于少對每條邊檢查一次，因為任何一條邊都有可能在最短路徑中，因D[w]+s(w,vi) ,并且如果D[vi]為∞則將vi加入到Path中，然此步驟4)的時間復(fù)雜度為O(T)，當(dāng)T=n?時， 復(fù)雜度為0(n2)，與Dijkstn算法相同。后將P[vi]的前驅(qū)設(shè)置為w，并修改最短路徑D[vi]= D[w]+因此優(yōu)化后的算法最壞時間復(fù)雜度為max{O(n),O(T),s(w,vi)。 重復(fù)步驟(2)。0(m)},即為0(m)。改進后的算法C++源代碼如下:5結(jié)論bool ShortestPath OptDU(MGraph *G,int n, int v0, /PrevPoint*/優(yōu)化后的算法經(jīng)過在物資籌供決策系統(tǒng)的實際應(yīng)用，算int *p/*ShortPathTable*/ int *D){ int w,imin;法的時間復(fù)雜度與Dijkstra算法- -樣， 但在T<n ) retum fsl:/trow OutOfBounds();多堵文獻for(i=0;i