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