一種代購(gòu)鄰接矩陣乘位加比小算法

一種代購(gòu)鄰接矩陣乘位加比小算法

g（v，e，w）、{v=n，w={wij是相對(duì)于e=s的樹(shù)，vj是相對(duì)于i和j的節(jié)點(diǎn)編號(hào)}。求結(jié)點(diǎn)vi→vj,j=1,2,L,n的“權(quán)值之和最小”的最短路徑是經(jīng)典的路由問(wèn)題。Dijkstra標(biāo)號(hào)算法及基于標(biāo)號(hào)思想發(fā)展出的幾種其他算法是公認(rèn)的求最短路徑的較好算法,文獻(xiàn)也指出Dijkstra算法是目前因特網(wǎng)和Adhoc網(wǎng)絡(luò)鏈路狀態(tài)協(xié)議所采用的路由算法。Dijkstra算法依賴于局部路徑代價(jià),通過(guò)不斷擴(kuò)展最低代價(jià)的葉子結(jié)點(diǎn),從而計(jì)算出始結(jié)點(diǎn)到目的結(jié)點(diǎn)的最短路徑。這種方法的缺陷在于它不從圖的全局考慮路由,在某些圖中,易得一條前端權(quán)值低而后端權(quán)值高的總權(quán)值較高的路徑,而不是一條總權(quán)值更低但前端權(quán)值高而后端權(quán)值低的路徑,故在這種情況下并非最佳?；诖?本文將提出并證明“代價(jià)鄰接矩陣乘位加比小算法”,完全克服了標(biāo)號(hào)算法的上述缺陷。1階最短路徑矩陣k計(jì)算本文先引用文獻(xiàn)的一個(gè)定理,然后給出5個(gè)定義。定理1在一個(gè)n階圖中,若從頂點(diǎn)vi→vj(vi≠vj)存在通路,則從vi→vj存在長(zhǎng)度小于等于n-1的初級(jí)通路(通路所經(jīng)所有結(jié)點(diǎn)互不相同)。定義1n階有向圖D的一階代價(jià)鄰接矩陣A1(D):A1(D)=(aij(1))n×n。令aij(1)為iv鄰接到vj的邊的最小權(quán),若該二結(jié)點(diǎn)僅通過(guò)一條邊鄰接,則a(1)ij為鄰接邊權(quán);若有多條平行邊,則選取帶權(quán)邊權(quán)重最小值;若iv與vj不鄰接,則記為∞。定義2一階代價(jià)鄰接矩陣A1(D)的“乘位加比小”運(yùn)算⊙:A1(D)⊙A1(D)。令A(yù)1(D)=(aij(2))n×n=A1(D)⊙A1(D),其中:顯然,aij(2)表示vi→vj的長(zhǎng)度為2(經(jīng)一個(gè)中間結(jié)點(diǎn))的路徑的最小權(quán),對(duì)應(yīng)路徑為vi→vm→vj。若aij(2)=∞,則vi→vj長(zhǎng)度為2的路徑不可達(dá)。定義3K階代價(jià)鄰接矩陣Ak(D):Ak(D)=(aij(k))n×nAk-1(D)=Ak-1(D)⊙A1(D),k=2,3,L,n-1。其中:式中aij(k)表示vi→vj的長(zhǎng)度為K的路徑的最小權(quán),從aim(k-1)對(duì)應(yīng)的vi→vm長(zhǎng)度為K-1的最短路徑到達(dá)vj,得長(zhǎng)度為K的最短路徑。若aij(k)=∞,則vi→vj經(jīng)長(zhǎng)度為K的路徑不可達(dá)。定義4一階最短路徑矩陣1R(D):1R(D)=(rij(1))n×n。rij(1)表示vi→vj長(zhǎng)度為1的路徑經(jīng)過(guò)的結(jié)點(diǎn)有序集。若iv鄰接到vj,則rij(1)=<i,j>,否則為空集φ。若i=j,則rii(1)=<i,i>為多重有序集。可見(jiàn),一階最短路徑矩陣1R(D)是一階代價(jià)鄰接矩陣1A(D)導(dǎo)出的矩陣,若aij(1)≠∞,則rij(1)=<i,j>,否則rij(1)=φ。定義5k階最短路徑矩陣Rk(D):Rk(D)=(rij(k))n×n。rij(k)表示vi→vj長(zhǎng)度為K的最短路徑經(jīng)過(guò)的結(jié)點(diǎn)有序集(K+1個(gè)結(jié)點(diǎn)),即rij(k)=<i,L,l,Lj>,rij(k)可能是一個(gè)多重有序集,此時(shí)將該集中相同元素只保留一次,所得的路徑序列即為此長(zhǎng)度為K的路徑所對(duì)應(yīng)的最短初級(jí)通路;若vi→vj不存在長(zhǎng)度為K的路徑,則rij(k)為空集φ。Rk(D)矩陣是Ak(D)矩陣的衍生矩陣。Ak(D)=(aij(k))n×n,若aij(k)=∞,則rij(k)=φ;若aij(k)≠∞,則rij(k)為結(jié)點(diǎn)有序集rim(k-1)的末尾添上結(jié)點(diǎn)vj,即:rij(k)=rim(k-1)U<j>=<i,L,l,Lm,j>,其中。2最短路徑權(quán)的種類定理2(“乘位加比小”最短路徑算法)已知n階有向圖D=<V,E,W>是所有環(huán)代價(jià)都為零的多重圖,構(gòu)造一階代價(jià)鄰接矩陣1A(D),并通過(guò)“乘位加比小”運(yùn)算,得代價(jià)鄰接陣序列A1(D),A2(D),L,An-1(D),同時(shí)得到相應(yīng)的衍生最短路徑矩陣序列R1(D),R2(D),L,Rn-1(D)。取自An-1(D)的元素aij(n-1)是vi→vj的最短路徑權(quán);取自Rn-1(D)的元素rij(n-)1(結(jié)點(diǎn)有序集)若是單重集,則就是vi→vj長(zhǎng)度為n-1的最短路徑,若rij(n-1)是多重集,將該集中相同元素只保留一個(gè)所得的有序集就是vi→vj長(zhǎng)度小于n-1的最短路徑。稱該算法為代價(jià)陣“乘位加比小”算法。證明:設(shè)vi,vj∈V。1)若vi=vj,則aij(1)=aii(1)=0同理可得aii(3)=0,L,aii(n-1)=0,即結(jié)點(diǎn)到達(dá)自身不需經(jīng)任何中間結(jié)點(diǎn)。這與給出的圖相符。2)若vi≠vj。(1)證明aij(k)是vi→vj長(zhǎng)度為K的最短路徑權(quán),rij(k)是相應(yīng)長(zhǎng)度為K的最短路徑。用數(shù)學(xué)歸納法證明:(1)aij(1)∈A1(D),若aij(1)=∞,則通過(guò)長(zhǎng)為1的路徑,vi→vj不可達(dá);若aij(1)≠∞,則由aij(1)的構(gòu)造方法,aij(1)顯然是vi→vj長(zhǎng)為1的最短路徑權(quán),對(duì)應(yīng)的最短路徑為rij=<i,j>;若aij(1)=0,即vi=vj,顯然aij(1)是最短路徑權(quán),最短路徑為rii=<i,i>。(2)aij(2)∈A2(D)=A1(D)⊙A1(D),aij(2)=min{(ai1(1)+a1j(1)),(ai2(1)+a2j(1)),L,(ain(1)+anj(1))},若aij(2)=∞,則通過(guò)長(zhǎng)為2的路徑,vi→vj不可達(dá);若aij(2)≠∞,則通過(guò)長(zhǎng)為2的路徑,vi→vj可達(dá),且aij(2)是最小權(quán),令aij(2)=aim(1)+am(1)j,rij(2)=<i,m,j>一定是所有長(zhǎng)為2的路徑<i,l,j>(l=1,2,L,n-1)中權(quán)值之和最小的路徑,即最短路徑。(3)aij(k)∈Ak(D),當(dāng)aij(k)=∞,通過(guò)長(zhǎng)為K的路徑,vi→vj不可達(dá);當(dāng)aij(k)≠∞,假設(shè)aij(k)是vi→vj長(zhǎng)為K的路徑之最短路徑權(quán),假設(shè)rij(k)是vi→vj的長(zhǎng)為K的最短路徑。當(dāng)aij(k+1)∈Ak+1(D)=Ak(D)⊙A1(D),若aij(k+1)=∞,則vi→vj通過(guò)長(zhǎng)為K+1的路徑不可達(dá);若aij(k+1)≠∞,由“乘位加比小”運(yùn)算法則:假設(shè)ai1(k),ai2(k),L,ain(k)分別是vi->v1,vi->v2,L,vi->vn的長(zhǎng)為K的最短路徑權(quán),相應(yīng)的ri1(k),ri2(k),L,rin(k)分別是vi->v1,vi->v2,L,vi->vn長(zhǎng)為K的最短路徑,而aij(k+1)=aim(k)+amj(1)是vi→vj長(zhǎng)為K+1的路徑中權(quán)最小者,即最短路徑權(quán),rij(k+1)=rim(k)U<j>就是vi→vj長(zhǎng)為K+1的最短路徑(若是多重有序集,按定理所述方法變?yōu)閱沃赜行蚣?即得對(duì)應(yīng)最短初級(jí)通路)。綜合(1)、(2)、(3)的證明,由數(shù)學(xué)歸納法知:aij(k)∈Ak(D)是vi→vj長(zhǎng)度為K的最短路徑權(quán),rij(k)∈Rk(D)是相應(yīng)的長(zhǎng)度為K的最短路徑。(2)當(dāng)p<q,p,q∈{1,2,L,n-1},證明下述兩個(gè)結(jié)論。結(jié)論1:若a(p)ij是vi→vj的所有路徑中的最小路徑權(quán)值,rij(p)是所有路徑中的最短路徑,則a(p)ij)=aij(q),rij(p)=rij(q)(多重有序集變成對(duì)應(yīng)單重有序集后相等),即算法不會(huì)過(guò)濾掉全局最優(yōu)。結(jié)論2:若a(p)ij、rij(p)非全局最優(yōu),代價(jià)陣“乘位加比小”運(yùn)算會(huì)繼續(xù)優(yōu)化該二元素,直到全局最優(yōu)。(1)vi→vj長(zhǎng)為p的最短路徑是全局最短路徑,即a(p)ij小于等于任何其他vi→vj的路徑權(quán)值,a(p)il+alj(1)(l=1,L,n-1Λl≠j)是vi→vj長(zhǎng)為p+1的路徑,ajj(1)=0,則a(p)ij=a(ijp)+ajj(1)≤a(p)il+alj(1),故:對(duì)應(yīng)rij(p+1)=rij(p)U<j>。同理可得,a(ijp+2)=L=aij(n-1)=a(p)ij,rij(p+2)=rij(p)U<j,j>,rij(p+3)=rij(p)U<j,j,j>,…,rij(n-1)=rij(p)U<j,j,L,j>(n-1-p個(gè)j)。結(jié)論1得證。(2)vi→vj通過(guò)長(zhǎng)度為p的路徑可達(dá),a(p)ij≠0,由(1)知若vi→vj長(zhǎng)為p+1的路徑權(quán)值a(ilp)+alj(1)(l=1,L,n-1Λl≠j)大于a(ijp),則a(p+1)ij=a(p)ij,rij(p+1)=rij(p)U<j>。若min{a(p)il+alj(1),l=1,L,n-1Λl≠j}=a(p)im+amj(1)<a(p)ij成立,則a(p+1)ij=aim(p)+amj(1),rij(p+1)=rim(p)U<j>?？梢?jiàn),vi→vj的路徑中,若某一階最短路徑p+l(l=1,2,L,n-1-p)的權(quán)值a(p+l)ij比p階最短路徑權(quán)值a(ijp)小,則a(p+l)ij就會(huì)更新a(p)ij(aij(p+l)≠a(p)ij),且以該最短路徑rij(p+l)更新rij(p)U<j,j,L,j>,其中<j,j,L,j>=l-1。結(jié)論2得證。若iv可達(dá)vj,由定理1知vi→vj必存在長(zhǎng)度小于等于n-1的初級(jí)通路,則aij(n-1)必為最短路徑權(quán),rij(n-1)必為vi→vj的最短路徑。綜合證明1)和2)知該最短路徑定理成立。3“乘位加比小”算法利用該最小路徑算法計(jì)算n階有向圖中vi→vj的最短路徑,需要(n-1)(n-2)次加法運(yùn)算以及調(diào)用n-2次n元素選小函數(shù)。運(yùn)算量與矩陣乘法相當(dāng)。對(duì)下述兩圖,分別用Dijkstra算法和本算法計(jì)算0v到5v的最短路徑。用Dijkstra算法,文獻(xiàn)給出圖1所得最短路徑為:Γ=v0v1v2v4v3v5,最短路徑權(quán)值為9;圖2也得相同路徑,Γ=v0v1v2v4v3v5,最小路徑權(quán)值為11。采用代價(jià)陣“乘位加比小”算法。先構(gòu)造1A(D),再計(jì)算5A(D)、R5(D)。圖1中最短路徑權(quán)aij(n-1)=a05(5)=9,最短路徑頂點(diǎn)集r05(5)=<0,1,2,4,3,5>,則最短路徑為:Γ=v0v1v2v4v3v5;圖2中最短路徑權(quán)aij(n-1)=a05(5)=10,最短路徑頂點(diǎn)集rij(n-1)=r05(5)=<0,0,0,1,3,5>,且該多重有序集對(duì)應(yīng)的單重有序集為<0,1,3,5>,則所求最短路徑為Γ=v0v1v3v5。分析圖1、圖2可知,圖2相比圖1只是邊<v1,v2>的權(quán)值從2變到4,但導(dǎo)致了Dijkstra算法得到了錯(cuò)誤的計(jì)算結(jié)