一種改進(jìn)的dijwsar算法

一種改進(jìn)的dijwsar算法

1頂?shù)狡渌冃温窂絛ijkksta算法（以下簡(jiǎn)稱d算法）是圖論中最短路徑的著名算法。d算法可以通過從一個(gè)點(diǎn)獲得的最短路徑的長(zhǎng)度來確定，而從一個(gè)點(diǎn)獲得的最短路徑的長(zhǎng)度不能從一個(gè)點(diǎn)獲得。1996年，EliOlinick和D.K.Smith等就求出所有最短路徑這一問題做了一些簡(jiǎn)單的探討，但這些探討過于簡(jiǎn)單，又不完整，而且缺少時(shí)間分析，所以沒有多大的實(shí)用性。該文提出了D算法的一種改進(jìn)算法（以下簡(jiǎn)稱改進(jìn)算法），使用改進(jìn)算法能求出從一個(gè)頂點(diǎn)到其它各頂點(diǎn)的所有最短路徑，而且，此改進(jìn)算法的時(shí)間復(fù)雜度非常接近于任何一個(gè)求所有最短路徑算法的時(shí)間復(fù)雜度的一個(gè)下限值。改進(jìn)算法在很多領(lǐng)域（如：交通等）中有著較高的實(shí)用價(jià)值。2路徑單鏈表pr設(shè)一個(gè)帶權(quán)有向圖為G,G=(VER,E），其中VER為頂點(diǎn)集合，E為邊的集合。G中頂點(diǎn)數(shù)為n，該算法中的圖G限于討論簡(jiǎn)單圖（無環(huán)和無重邊）。使用改進(jìn)算法求從頂點(diǎn)V1（稱為源點(diǎn)）到其它各頂點(diǎn)的最短路徑長(zhǎng)度和所有最短路徑，存貯結(jié)構(gòu)如下：(1）用鄰接矩陣cost存貯圖G。(2）一維數(shù)組dist用來存放從V1到其它各頂點(diǎn)的當(dāng)前距離，一旦從V1到頂點(diǎn)Vk(2≤k≤n）的最短路徑長(zhǎng)度已求出，則dist[k]就是從V1到Vk的最短路徑的長(zhǎng)度。(3）當(dāng)前可能的路徑上頂點(diǎn)的所有直接前趨表（以下簡(jiǎn)稱PR表）PR表是用來存儲(chǔ)使用改進(jìn)算法運(yùn)行過程中已求出的從V1到其它各頂點(diǎn)（如Vk）的所有路徑上的此頂點(diǎn)（Vk）的所有直接前趨結(jié)點(diǎn)的。PR表由一個(gè)一維數(shù)組hpr和若干個(gè)單鏈表（這樣的每個(gè)單鏈表以下簡(jiǎn)稱一個(gè)前趨單鏈表）組成。hpr[k]中存儲(chǔ)的是一個(gè)前趨單鏈表的頭指針，一個(gè)以hpr[k]為頭指針的前趨單鏈表中每個(gè)結(jié)點(diǎn)（稱為一個(gè)趨向結(jié)點(diǎn)）由二個(gè)域組成，即Vpnex，其中Vp(1≤p≤n）稱為直接前趨域，它存已求出的從V1到Vk的路徑上Vk的一個(gè)直接前趨結(jié)點(diǎn)，而nex稱為趨向指針域，它存此單鏈表中下一個(gè)趨向結(jié)點(diǎn)的地址。(4）所有最短路徑表（以下簡(jiǎn)稱APT表）APT表是用來存儲(chǔ)已求出的從V1到其它各頂點(diǎn)的所有最短路徑的。APT表由一個(gè)一維數(shù)組hap和若干個(gè)APT表的子表APT1k(2≤k≤n）共同組成。設(shè)從V1到Vk共有n1k條最短路徑，一個(gè)APT的子表APT1k是用來存儲(chǔ)已求出的從V1到Vk的所有這n1k條最短路徑，而APT1k這個(gè)子表的地址存于一維數(shù)組hap的元素hap[k]中。一個(gè)APT表的子表APT1k由一個(gè)一維數(shù)組hp1k和n1k個(gè)單鏈表（這樣的一個(gè)單鏈表稱為一個(gè)路徑單鏈表）組成。hp1k[b](1≤b≤n1k）中存一個(gè)路徑單鏈表的頭指針，這條路徑單鏈表中每個(gè)結(jié)點(diǎn)稱為一個(gè)路徑結(jié)點(diǎn)，它由二個(gè)域組成，即Vfvnex，其中Vf(1≤f≤n）稱為頂點(diǎn)域，它存從V1到Vk的一條最短路徑上的一個(gè)頂點(diǎn)，vnex稱為路徑指針域，指向此路徑單鏈表的下一個(gè)結(jié)點(diǎn)。以hp1k[b]為頭指針的路徑單鏈表中所有結(jié)點(diǎn)的頂點(diǎn)域（從頭結(jié)點(diǎn)開始依次一直到尾結(jié)點(diǎn)）是用該算法求得的第b條從V1到Vk的最短路徑。hp1k這個(gè)數(shù)組元素的地址存于一維數(shù)組hap的數(shù)組元素hap[k]中（用C語言中的與指針變量相關(guān)的知識(shí)易于直接求出一數(shù)組元素的地址），這樣從hap這個(gè)數(shù)組出發(fā)就能查出已求出的從V1到其它頂點(diǎn)的所有最短路徑。(5）一維數(shù)組xs.下一節(jié)介紹的算法中，對(duì)圖G中的一個(gè)頂點(diǎn)Vd(1≤d≤n）來說，如果xs[d]=1，則表明Vd在集合S（下一節(jié)介紹）中，如果xs[d]=0，則表明Vd在集合VER-S中。3改進(jìn)的算法3.1中心vk的距離把圖G中頂點(diǎn)集合VER分成二組，即S和VER-S，第一組S中是已求出最短路徑的所有頂點(diǎn)的集合，S初值是S=邀V1妖，第二組VER-S中是其余尚未求出最短路徑的頂點(diǎn)集合。每個(gè)頂點(diǎn)Vk對(duì)應(yīng)一個(gè)距離dist[k],S中頂點(diǎn)Vk的距離dist[k]就是從V1到此頂點(diǎn)最短路徑的長(zhǎng)度，VER-S中頂點(diǎn)Vk的距離dist[k]是從V1到此頂點(diǎn)的當(dāng)前距離。（dist[k]初值等于cost[k]）。每個(gè)頂點(diǎn)Vk對(duì)應(yīng)于一個(gè)以hpr[k]為頭指針的前趨單鏈表，S中一個(gè)頂點(diǎn)Vk的前趨單鏈表中所有趨向結(jié)點(diǎn)的直接前趨域組成的一個(gè)集合是從V1到此頂點(diǎn)Vk所有最短路徑上此頂點(diǎn)（Vk）的直接前趨結(jié)點(diǎn)的集合，而VER-S中一個(gè)頂點(diǎn)Vk的前趨單鏈表中所有結(jié)點(diǎn)的直接前趨域組成的一個(gè)集合是在求解過程中已求出的從V1到頂點(diǎn)Vk的當(dāng)前所有路徑上此頂點(diǎn)（Vk）的直接前趨結(jié)點(diǎn)的集合。使用改進(jìn)算法從第二組的頂點(diǎn)中選取一個(gè)距離最小的頂點(diǎn)Vz,(2≤z≤n），把Vz加入S中，每次加入一個(gè)頂點(diǎn)Vz到S中后，就要對(duì)第二組中的各個(gè)頂點(diǎn)的距離進(jìn)行一次修改，如果原dist[u]>dist[z]+cost[z][u](Vu為VER-S中的頂點(diǎn)，1≤u≤n），則將距離dist[u]修改成dist[z]+cost[z][u]的值。3.2apts表1y表2假設(shè)源點(diǎn)為V1，改進(jìn)算法步驟如下：(1）把源點(diǎn)V1放入集合S中（即：xs=1),dist[k]的初值等于cost[k]；初始時(shí)，PR表中賦初值如下：hpr=∧；如果cost[k]≠∞，則以hpr[k]為頭指針的前趨單鏈表中僅有一個(gè)趨向結(jié)點(diǎn)，其直接前趨域的值為V1；否則hpr[k]=∧（2≤k≤n）。(2）判斷S中頂點(diǎn)數(shù)是否等于n，若等于n，則本算法結(jié)束；否則轉(zhuǎn)（3）。(3）從VER-S集合中選取一個(gè)距離最小的頂點(diǎn)Vz，把它放入集合S中。(4）每次加入一個(gè)頂點(diǎn)Vz到S中后，就可能要對(duì)第二組中各個(gè)頂點(diǎn)（設(shè)為Vu,Vu∈（VER-S）在PR表中的以hpr[u]為頭指針的前趨單鏈表做如下修改：如果原dist[u]=dist[z]+cost[z][u]，則往以hpr[u]為頭指針的單鏈表中插入一個(gè)新結(jié)點(diǎn)，其直接前趨域的值為Vz。如果原dist[u]>dist[z]+cost[z][u]，則將以hpr[u]為頭指針的單鏈表中原有的各個(gè)結(jié)點(diǎn)刪除并釋放后，再產(chǎn)生一個(gè)新的趨向結(jié)點(diǎn)（設(shè)為T結(jié)點(diǎn)），將T結(jié)點(diǎn)的直接前趨域值置為Vz，其趨向指針域的值置為空，將T結(jié)點(diǎn)的地址存于hpr[u]中。(5）每次加入一個(gè)頂點(diǎn)Vz到S中后，就要在APT表中產(chǎn)生從V1到Vz的所有最短路徑，產(chǎn)生方法如下：依次掃描PR表中以hpr[u]為頭指針的前趨單鏈表中各個(gè)趨向結(jié)點(diǎn)的直接前趨域得到從V1到Vz的所有最短路徑上的Vz的各個(gè)直接前趨頂點(diǎn)。每查得一個(gè)這樣的直接前趨頂點(diǎn)（設(shè)為Vy,1≤y≤n,y為整數(shù)），如果Vy為源點(diǎn)V1，則在APT表的子表APT1z中生成一條有兩個(gè)結(jié)點(diǎn)的路徑單鏈表，此路徑單鏈表的結(jié)點(diǎn)的頂點(diǎn)域的值分別為V1,Vz；如果Vy≠V1，則查找APT表中hap[y]這個(gè)元素得到APT的另一個(gè)子表APT1y的首地址，即hp1y的地址；V1到Vy的所有最短路徑已求出，設(shè)共有n1y條，它們已被存于APT1y表中；APT1y表中的每一條路徑單鏈表中所有路徑結(jié)點(diǎn)的頂點(diǎn)域加上Vz就是一條從V1到Vz的最短路徑。依次掃描APT1y表中這n1y條最短路徑單鏈表，每掃描到其中一條路徑單鏈表（稱為A單鏈表），則在APT1z表中首先拷貝產(chǎn)生一條與A單鏈表相同的單鏈表（稱為B單鏈表），然后在B單鏈表原尾結(jié)點(diǎn)后插入一個(gè)新的結(jié)點(diǎn)，此結(jié)點(diǎn)頂點(diǎn)域的值為Vz，形成一條從V1到Vz的路徑單鏈表。(6）修改不在S中頂點(diǎn)的距離即：如果Vu(1≤u≤n）為VER-S中的頂點(diǎn)，且原dist[u]>dist[z]+cost[z][u]則將dist[u]修改成dist[z]+cost[z][u]。轉(zhuǎn)（2）。4前趨單鏈表最壞時(shí)間復(fù)雜度第（1）步時(shí)間復(fù)雜度為O(n）。第（2）步時(shí)間復(fù)雜度為O(n）。第（3）步時(shí)間復(fù)雜度為（n-1)+(n-2）+……+1，即為O(n2)第（4）步所花時(shí)間是用于修改PR表中的前趨單鏈表的。第q(1≤q≤n-1）次從VER-S集合中選取一個(gè)距離最小的頂點(diǎn)Vq放入S集合后，此時(shí)S集合中共有q+1個(gè)頂點(diǎn)（含頂點(diǎn)V1），設(shè)這些頂點(diǎn)為Vt(1≤t≤n），在PR表中以hpr[t]為頭指針的單鏈表已不需再修改，因此PR表中要修改的單鏈表最多為n-q-1個(gè)，而此時(shí)要修改的每個(gè)前趨單鏈表中最多有q個(gè)結(jié)點(diǎn)。修改一個(gè)前趨單鏈表分兩種情況，一種是往前趨單鏈表中僅僅插入一個(gè)結(jié)點(diǎn)（時(shí)間復(fù)雜度為O(1）），另一種是刪除原有的前趨單鏈表并釋放原來所有結(jié)點(diǎn)后，再插入一個(gè)新的結(jié)點(diǎn)（時(shí)間復(fù)雜度為O(q+1））。根據(jù)上面的分析，第q次從VER-S集合中取一個(gè)距離最小的頂點(diǎn)放入S集合后，僅僅修改PR表中一個(gè)前趨單鏈表最壞時(shí)間復(fù)雜度為O(q+1），要修改整個(gè)PR表最壞時(shí)間復(fù)雜度為：O((n-q-1）×（q+1）），在整個(gè)算法運(yùn)行過程中第（4）步最壞的時(shí)間復(fù)雜度為：所以第（4）步最壞時(shí)間復(fù)雜度為O(n3）。第（5）步是產(chǎn)生從V1到Vz的所有最短路徑，設(shè)一個(gè)頂點(diǎn)數(shù)為n的帶權(quán)有向圖中從一個(gè)頂點(diǎn)到另一個(gè)頂點(diǎn)的所有最短路徑的總個(gè)數(shù)的數(shù)量級(jí)最多為：O(sh(n））。設(shè)第（5）步時(shí)在PR表中查得的Vz頂點(diǎn)的一個(gè)直接前趨為Vy(1≤y≤n），在APT1y表中從V1到Vy的所有路徑單鏈表總個(gè)數(shù)最多為O(sh(n）），因?yàn)橐粭l路徑單鏈表最多含n個(gè)結(jié)點(diǎn)，因此，每掃描或產(chǎn)生一條路徑單鏈表時(shí)間復(fù)雜度為O(n），在第（5）步中依次掃描APT1y表中所有路徑單鏈表并在APT1z表中產(chǎn)生對(duì)應(yīng)的路徑單鏈表的最壞時(shí)間復(fù)雜度為O(n×sh(n)+n×sh(n）），即O(nsh(n））。因?yàn)槊總€(gè)Vz頂點(diǎn)在第（5）步時(shí)所有直接前趨最多有n-1個(gè)（即：上述Vy最多有n-1個(gè)），因此在第（5）時(shí)產(chǎn)生從V1到一個(gè)Vz這樣的頂點(diǎn)的所有最短路徑的最壞時(shí)間復(fù)雜度為：O((n-1）×nsh(n）），即，O(n2sh(n））。而在整個(gè)改進(jìn)算法中Vz這樣的頂點(diǎn)有n-1個(gè)（不包括源點(diǎn)V1），因此第（5）步總的最壞時(shí)間復(fù)雜度為：O((n-1）×n2sh(n）），即為：O(n3sh(n))第（6）步最壞時(shí)間復(fù)雜度為：（n-1)+(n-2）+…+1，即為：O(n2)因此整個(gè)算法的最壞時(shí)間復(fù)雜度為：max邀O(n2),O(n3),O(n3sh(n））妖即為：O(n3sh(n））。雖然，sh(n）在最壞情況下是指數(shù)函數(shù)，但這不能作為否定該算法的依據(jù)，因?yàn)橛行┲笖?shù)時(shí)間算法在實(shí)際中十分有用，有幾個(gè)著名算法就是這種情況，例如：已經(jīng)證明線性規(guī)劃的單純形算法具有指數(shù)時(shí)間復(fù)雜性[KleeandMinty,1972],[Zedeh,1973]，但是它在實(shí)際中計(jì)算得很好，給人留下了深刻印象。因此該算法不失為一種有益的探索。另一方面，sh(n）是一個(gè)帶權(quán)有向圖的固有屬性，根據(jù)上面的假設(shè)，從源點(diǎn)V1至其余n-1個(gè)頂點(diǎn)所有最短路徑的總數(shù)目的數(shù)量級(jí)為：O((n-1）×sh(n）），即：O(nsh(n）），而一條最短路徑上所含結(jié)點(diǎn)總個(gè)數(shù)的數(shù)量級(jí)為O(n），因此任何一個(gè)求圖中一個(gè)頂點(diǎn)V1到其它各頂點(diǎn)的所有最短路徑的算法其時(shí)間復(fù)雜度應(yīng)不小于：O(n×（nsh(n）），即O(n2sh(n）），這是此類求所有最短路徑算法時(shí)間復(fù)雜度的一個(gè)下限值，而該算法時(shí)間復(fù)雜度僅為：O(n3sh(n)),n2sh(n）與n3sh(n）這二個(gè)函數(shù)很接近，因此該算法無疑是一種高效而實(shí)用的