時間依賴網(wǎng)絡(luò)模型中最短路徑算法研究

時間依賴網(wǎng)絡(luò)模型中最短路徑算法研究

1tdn網(wǎng)絡(luò)的研究最短路徑算法（sp）算法在許多研究和應(yīng)用中起著核心作用，如網(wǎng)絡(luò)分析、交通規(guī)劃、通信、計(jì)算機(jī)科學(xué)等。大量問題可以抽象為最短路徑模型。許多問題的解決方案需要反復(fù)解決最短路徑問題。sp引起了科學(xué)、工程科學(xué)、通信、交通工程等領(lǐng)域的專家和科學(xué)家的廣泛興趣。在dijkat假設(shè)的工作中，提出了一種方法來解決最短路徑問題，其理論不斷發(fā)展，導(dǎo)致了大量算法。在文獻(xiàn)中，17個最短路徑算法進(jìn)行了理論分析和實(shí)驗(yàn)評估。在文獻(xiàn)中，20多種最短路徑算法進(jìn)行了分析和評估，包括建立規(guī)范方法、規(guī)范審查方法、動態(tài)規(guī)劃方法、基于線性代數(shù)方法的快速啟動和雙向啟動算法以及基于運(yùn)動神經(jīng)網(wǎng)絡(luò)的算法。這些算法屬于靜態(tài)算法，即處理固定網(wǎng)絡(luò)拓?fù)浜凸潭?quán)重。這些靜態(tài)假設(shè)在許多應(yīng)用中是不確定的。計(jì)算機(jī)網(wǎng)絡(luò)和通信、分布式處理和智能網(wǎng)絡(luò)系統(tǒng)（as）的繁榮給這一傳統(tǒng)研究課程帶來了新的轉(zhuǎn)折點(diǎn)：時間依賴網(wǎng)絡(luò)中任何弧段的運(yùn)行時間是時間的函數(shù)。時間依賴的網(wǎng)絡(luò)(以下簡稱TDN網(wǎng)絡(luò))中最短路徑問題比傳統(tǒng)的最短路徑問題更具有現(xiàn)實(shí)意義,吸引了許多研究者的興趣.許多研究者認(rèn)識到TDN網(wǎng)絡(luò)與靜態(tài)網(wǎng)絡(luò)的差異性,從各自從事的研究領(lǐng)域、不同的側(cè)面研究這一問題.作者對TDN網(wǎng)絡(luò)研究進(jìn)展層次分為:(1)認(rèn)為傳統(tǒng)的最短路徑算法可以應(yīng)用到TDN網(wǎng)絡(luò),代表性的算法是Dreyfus給出的改進(jìn)Dijkstra算法求解TDN網(wǎng)絡(luò)最小時間路徑問題的方法,并斷言該方法會像靜態(tài)最短路徑問題一樣有效.(2)給出“病態(tài)”實(shí)例說明傳統(tǒng)的最短路徑算法的局限性.代表性的工作是Kaufman和Smith給出的Dreyfus算法在TDN網(wǎng)絡(luò)中是不正確的反例,建立了嚴(yán)格的一致性條件來限制“病態(tài)”實(shí)例的出現(xiàn).文獻(xiàn)的核心內(nèi)容是在一致性約束條件下,證明傳統(tǒng)的最短路徑算法可以求解一類時間依賴的網(wǎng)絡(luò)中最短路徑問題.文獻(xiàn)研究的網(wǎng)絡(luò)是本文給出的FIFO網(wǎng)絡(luò),但是對于非FIFO網(wǎng)絡(luò)并沒有進(jìn)行研究.文獻(xiàn)給出了TDN網(wǎng)絡(luò)在NPP(Non-PassingProperty)條件下,基于流速的SP算法,它與Dreyfus算法有同樣的缺陷.(3)對“病態(tài)”實(shí)例的情況不加限制,代表性的論文是Orda和Rom給出的三種類型的網(wǎng)絡(luò)模型:提出了不受限制的等待模型;禁止等待模型和源等待模型.當(dāng)訪問的結(jié)點(diǎn)允許等待時,這種方法可以確定最優(yōu)等待時間或者如果在其它結(jié)點(diǎn)不允許等待而在源結(jié)點(diǎn)的最優(yōu)等待時間.如果每一結(jié)點(diǎn)都不允許等待,Orda和Rom方法不能找到最優(yōu)路徑.Orda的方法在計(jì)算機(jī)通信網(wǎng)絡(luò)中是有效的;但是,在交通網(wǎng)絡(luò)中是無效的,因?yàn)榻煌ňW(wǎng)絡(luò)結(jié)點(diǎn)處等待是沒有意義的,交叉路口是不允許等待的.文獻(xiàn)的方法類似于Orda和Rom的方法.(4)在沒有任何限制性條件下,建立一套完整的理論和算法解決各種情況的問題;這正是本文的研究內(nèi)容.本文從最短路徑算法的理論基礎(chǔ)入手,從理論上證明了傳統(tǒng)最短路徑算法,如Dijkstra算法和標(biāo)號設(shè)置算法,在TDN網(wǎng)絡(luò)上不能有效地求解最短路徑問題;并且,在沒有任何限制性條件下,給出了TDN網(wǎng)絡(luò)模型、理論基礎(chǔ)、求解最小時間路徑的優(yōu)化條件和SPTDN算法.本文的其它部分組織如下:第2節(jié)給出了TDN網(wǎng)絡(luò)形式化模型和理論基礎(chǔ);第3節(jié)提出兩個網(wǎng)絡(luò)模型下的最小時間路徑算法;第4節(jié)討論TDN網(wǎng)絡(luò)應(yīng)用實(shí)例;最后是結(jié)束語.2時間依賴網(wǎng)絡(luò)模型和理論基礎(chǔ)2.1tdn網(wǎng)絡(luò)模型將時間依賴網(wǎng)絡(luò)(TDN網(wǎng)絡(luò))表達(dá)為(V,A,T),其中V={v1,v2,…,vN}是有限結(jié)點(diǎn)集,A是有限弧集,A?V×V;T=(gij(t))是對于每一弧(vi,vj)∈A,在時間t∈[t0,tm]?R區(qū)間上定義的矩陣函數(shù);gij(t)是非負(fù)實(shí)數(shù),表示從結(jié)點(diǎn)vi在t時刻出發(fā)到達(dá)結(jié)點(diǎn)vj的走行時間;[t0,tm]是感興趣的時間閉區(qū)間,使得?t∈[t0,tm],t+gij(t)有定義;t0是網(wǎng)絡(luò)中結(jié)點(diǎn)最早的出發(fā)時間,tm是感興趣區(qū)間的端點(diǎn).在邊界處,假設(shè)gij(t)=∞,t>tm.對于離散時間情況,TDN網(wǎng)絡(luò)模型為(V×S,A,T),其中,S是將時間離散化后的時間間隔,是感興趣的時間定義域,即S={t0,t0+Δ,t0+2Δ,…,t0+(M-1)Δ};t0是網(wǎng)絡(luò)中從任一結(jié)點(diǎn)出發(fā)的最早時間;Δ是較小的時間間隔,在該間隔內(nèi)弧的條件不發(fā)生變化,在交通網(wǎng)絡(luò)中通常取5min;M是使得t0到t0+(M-1)Δ成為感興趣時間段(例如,交通高峰期間)的最大整數(shù).?t∈S,gij(t)是非負(fù)實(shí)數(shù),t+gij(t)總是有定義;對于t>t0+(M-1)Δ,定義gij(t)=∞.V×S={(vi,tj)|vi∈V且tj∈S},表示結(jié)點(diǎn)的狀態(tài)空間,有序?qū)?vi,tj)表示結(jié)點(diǎn)的一個狀態(tài).同樣一個結(jié)點(diǎn),但是處在該結(jié)點(diǎn)的時間不同,那么結(jié)點(diǎn)的狀態(tài)也不同.這種表示法與傳統(tǒng)的網(wǎng)絡(luò)模型不同.對于靜態(tài)路徑問題,傳統(tǒng)模型下的結(jié)點(diǎn)狀態(tài)既可以描述優(yōu)化過程的演變特征,又能滿足無后效性,即馬爾克夫性.在TDN網(wǎng)絡(luò)模型中仍然采用傳統(tǒng)的網(wǎng)絡(luò)模型表示法,則根據(jù)當(dāng)前的狀態(tài)不能確定下一步的決策,而必須知道以前的一系列結(jié)點(diǎn)的狀態(tài),才能做出決策.顯然這種模型不滿足馬爾科夫性.我們給出的網(wǎng)絡(luò)模型表示法克服了這一缺陷.在TDN網(wǎng)絡(luò)中,用表示從源結(jié)點(diǎn)vs在t0時刻出發(fā)到達(dá)結(jié)點(diǎn)vi的路徑,用表示從結(jié)點(diǎn)vi在ti時刻出發(fā)到達(dá)目的地結(jié)點(diǎn)vN的路徑.即,ti是到達(dá)結(jié)點(diǎn)vi的時間;.最小時間路徑是指從一個結(jié)點(diǎn)在t時刻出發(fā)到達(dá)另一個結(jié)點(diǎn)的所有路徑中走行時間最少的路徑.2.2出現(xiàn)在源控制至終點(diǎn)的最優(yōu)路徑TDN網(wǎng)絡(luò)與傳統(tǒng)的靜態(tài)網(wǎng)絡(luò)相比,發(fā)生了本質(zhì)變化.在傳統(tǒng)網(wǎng)絡(luò)中定理1和定理2成立.定理1.如果網(wǎng)絡(luò)中每個圈的長度為非負(fù),則網(wǎng)絡(luò)中每條路徑的長度不小于相應(yīng)的最短路徑長度;且每條最短路徑的子路徑也是最短路徑.在文獻(xiàn)中,網(wǎng)絡(luò)N=(V,E,W)中從源點(diǎn)s到v的最短路徑長度記為L(v);W(u,v)表示弧(u,v)的權(quán)值.定理2.設(shè)L(v0),L(v1),…,L(vk)已求得,T={v0,v1,…,vk},由下面公式可求得L(vk+1):L(vk+1)=min{L(vi)+W(viv′)};vi∈T,v′∈V-T.定理1和定理2就是著名的Dijkstra最短路徑算法和標(biāo)號設(shè)置算法的理論基礎(chǔ).TDN網(wǎng)絡(luò)的動態(tài)性使得上面的理論出現(xiàn)了錯誤結(jié)論.我們給出下面的理論基礎(chǔ)來研究這一新的動態(tài)網(wǎng)絡(luò)模型.定理3.在時間依賴的網(wǎng)絡(luò)(V,A,T)中,如果存在一條弧(i,j)∈A的走行時間函數(shù)gij(t)滿足:gij(t)>Δt+gij(t+Δt),那么定理1和定理2不一定成立.證明.假設(shè)在連續(xù)情況下,gij(t)連續(xù)、處處可微,我們構(gòu)造一個輔助函數(shù)φ(t)=t+giN(t),表示φ(t)是從源結(jié)點(diǎn)經(jīng)結(jié)點(diǎn)vi,并從vi在t時刻出發(fā)到達(dá)鄰接目的地結(jié)點(diǎn)vN的最小走行時間函數(shù).如果定理1和定理2成立,則最短路徑的子路徑也是最短路徑,即ti是從源結(jié)點(diǎn)到結(jié)點(diǎn)vi的最優(yōu)路徑的最小時間;從而在問題的時間區(qū)間(0,T)內(nèi),φ(t)在ti取最小值,由極值的定義可知該最小值一定是極小值,即φ′(t)|t=ti=0.我們只要證明在定理3的條件下φ′(t)|t=ti≠0即可.因?yàn)槿绻鹓iN(t)滿足定理3的條件,那么limΔt→0-[giΝ(t+Δt)-giΝ(t)]Δt=-g′iΝlimΔt→0?[giN(t+Δt)?giN(t)]Δt=?g′iN(t)>1,得g′iN(t)<-1;由φ′(t)|t=ti=1+g′iN(ti),得到φ′(t)|t=ti<0.同理,假設(shè)定理3的條件發(fā)生在路徑中間的任何弧上,按照上面的推導(dǎo)也可推出定理1和定理2是不正確的結(jié)論.對于離散時間情況:設(shè)從源結(jié)點(diǎn)vs在時刻ts出發(fā)到達(dá)目的結(jié)點(diǎn)vN的兩條路徑為與目的結(jié)點(diǎn)vN鄰接的前一個結(jié)點(diǎn)為vi;ti,t′i是到達(dá)vi的兩個不同時間,ti≠t′i.假設(shè)是1Ν1N最小時間路徑,即tN<t′N.由定理1和定理2可知從1Ν1N源結(jié)點(diǎn)vs在時刻ts出發(fā)到結(jié)點(diǎn)vi的子路徑也一定是最小時間路徑,即有ti<t′i.定理3的條件意味著:當(dāng)ti<t′i時,giN(ti)>t′i-ti+giN(t′i).而tN=ti+giN(ti)>t′i+giN(t′i)=t′N,這樣得到tN>t′N,矛盾.如果是2Ν最小時間路徑,而子路徑{(vs,ts),(v′1,t′1),…,(vi,t′i)}又不是最小時間路徑,這與定理1,2相矛盾.同理假設(shè)定理3的條件發(fā)生在路徑中間的任何弧上,按照上面的推導(dǎo)也可推出上面的結(jié)論.綜上,定理3得證.由定理3顯然有下面的推論成立.推論1.Dijkstra最短路徑算法和標(biāo)號設(shè)置算法在時間依賴的網(wǎng)絡(luò)中不能有效地求解最短路徑問題.定理3的意義不僅僅從理論上證明了傳統(tǒng)的最短路徑算法,如Dreyfus,Dijkstra算法等的局限性;而且,對于其它領(lǐng)域中類似算法的正確性,如人工智能中的A*算法,也有相同的結(jié)論.下面給出違反定理1、定理2,并使得推論成立的兩個時間依賴的網(wǎng)絡(luò)例子.圖1的實(shí)例來源于文獻(xiàn),但是文獻(xiàn)用這個實(shí)例來說明動態(tài)最優(yōu)化原理在TDN網(wǎng)絡(luò)中是不正確的.作者認(rèn)為這是錯誤的,因?yàn)樗`反了動態(tài)最優(yōu)化原理的順序形式,而并不違反最優(yōu)化原理的逆序形式.離散時間情況下的一個例子如圖1所示.從結(jié)點(diǎn)1在0時刻出發(fā)到結(jié)點(diǎn)4的最優(yōu)路徑按照傳統(tǒng)的Dijkstra方法或者標(biāo)號設(shè)置算法是(1,3,4),走行時間是30;但是路徑(1,2,3,4)具有最小走行時間25.連續(xù)時間情況下的一個例子如圖2所示.從結(jié)點(diǎn)1在0時刻出發(fā)到結(jié)點(diǎn)4的最優(yōu)路徑按照傳統(tǒng)Dijkstra方法或者標(biāo)號設(shè)置算法是(1,3,4),走行時間是17;但是路徑(1,2,3,4)具有最小走行時間1+4+g34(5)=5+[1+(5-5)2]=6.我們將時間依賴的網(wǎng)絡(luò)模型分成兩類:FIFO網(wǎng)絡(luò)模型和非FIFO網(wǎng)絡(luò)模型.在時間依賴的網(wǎng)絡(luò)模型中,如果gij(t)連續(xù),處處可微并且?t,gij≤Δt+gij(t+Δt);則稱弧(vi,vj)為FIFO弧.在離散情況下,如果對于任何(vi,vj)∈A,s+gij(s)<t+gij(t),s<t,?s,t∈S;則稱弧(vi,vj)為FIFO弧;不具有這種特性的弧稱為非FIFO弧.如果網(wǎng)絡(luò)中所有的弧都是FIFO的,則該網(wǎng)絡(luò)稱為FIFO網(wǎng)絡(luò);至少包含一條非FIFO弧的網(wǎng)絡(luò)稱為非FIFO網(wǎng)絡(luò).對于不同的gij(t)情況,將導(dǎo)致不同的網(wǎng)絡(luò)特性.傳統(tǒng)的最短路徑的性質(zhì)可以推廣到FIFO網(wǎng)絡(luò)中.性質(zhì)1.如果是從源結(jié)點(diǎn)vs在ts時刻出發(fā),以最小時間tj到達(dá)結(jié)點(diǎn)vj的最小時間路徑,則對于任何結(jié)點(diǎn)vq,q=2,3,…,i;子路徑均是從源結(jié)點(diǎn)在ts時刻以最小時間tq到達(dá)結(jié)點(diǎn)vq的最小時間路徑.證明.在FIFO網(wǎng)絡(luò)中,在沒有負(fù)圈的情況下,一定存在.假設(shè)子路徑不是最小時間路徑,那么假設(shè)是從源結(jié)點(diǎn)vs在ts時刻,以最小時間t′q到達(dá)結(jié)點(diǎn)vq的最小時間路徑.因?yàn)?當(dāng)q=i時,t′j=t′q+gqj(t′q),又因?yàn)槭亲顑?yōu)的,所以t′q<ti,并且有t′j=t′q+gqj(t′q)<ti+gij(ti)=tj(FIFO網(wǎng)絡(luò)定義),即t′j<tj,也就是說也不是最小時間路徑,矛盾,因此是最小時間路徑.同理可證q=i-1,…,2時上面的結(jié)論也成立.證畢.定理4.在時間依賴的FIFO網(wǎng)絡(luò)中,設(shè)fi(t)是網(wǎng)絡(luò)中從源結(jié)點(diǎn)在時間t出發(fā)到達(dá)結(jié)點(diǎn)vi的最小時間,是從源結(jié)點(diǎn)在時間t出發(fā)到達(dá)結(jié)點(diǎn)vi的最小時間路徑的充分必要條件是,對于中的每條弧(vp,vq)都滿足fq(t)=fp(t)+gpq(fp(t)).證明.必要性,由性質(zhì)1可知如果是從源結(jié)點(diǎn)在t時刻出發(fā)到達(dá)結(jié)點(diǎn)vi的最小時間路徑,則中的每一條弧(vp,vq)都滿足fq(t)=fp(t)+gpq(fp(t)).充分性:設(shè)是FIFO網(wǎng)絡(luò)中的一條路經(jīng),如果該路徑的每一條弧(vp,vq)都滿足fq(t)=fp(t)+gpq(fp(t)),則有fi(t)=(fi(ti)-fi-1(ti-1))+(fi-1(ti-1)-fi-2(ti-2))+…+(f1(t1)-fs(t)).因?yàn)閒s(t)=0,又fq(t)=fp(t)+gpq(fp(t)),所以fq(t)-fp(t)=gpq(fp(t));因此,得到fi(t)=gi-1i(ti-1)+gi-2i-1(ti-2)+?+gs1(t).顯然,上式的下標(biāo)構(gòu)成了結(jié)點(diǎn)的有序集合{(vs,t),(v1,t1),(v2,t2),…,(vi,ti)},即.它是從源結(jié)點(diǎn)vs在t時刻出發(fā)到達(dá)結(jié)點(diǎn)vi的一條時間依賴的路徑.因?yàn)閒i(t)表示從結(jié)點(diǎn)vs在t時刻出發(fā)到達(dá)結(jié)點(diǎn)vi的最小時間,因此,是最小時間路徑.非FIFO網(wǎng)絡(luò)出現(xiàn)了新的動態(tài)特性,由定理3的證明可得到非FIFO網(wǎng)絡(luò)具有性質(zhì)2.性質(zhì)2.如果是從源結(jié)點(diǎn)vs在t時刻出發(fā),以最小時間tj到達(dá)結(jié)點(diǎn)vj的最小時間路徑,則對于任何結(jié)點(diǎn)q=2,3,…,i;子路徑不一定是從源結(jié)點(diǎn)在t時刻,以最小時間tq到達(dá)結(jié)點(diǎn)vq的最小時間路徑.性質(zhì)2就是傳統(tǒng)的Dijkstra算法或者標(biāo)號設(shè)置算法不能有效地求解非FIFO網(wǎng)絡(luò)最小時間路徑的根本原因.定理5(時間依賴網(wǎng)絡(luò)的優(yōu)化條件).對于每一個結(jié)點(diǎn)vi,每一時間t∈S,設(shè)fi(t)表示從結(jié)點(diǎn)vi在時間t出發(fā)到達(dá)目的地結(jié)點(diǎn)vN的時間,各結(jié)點(diǎn)的標(biāo)記fi(t)集合表示從結(jié)點(diǎn)vi在t時刻出發(fā)到達(dá)目的結(jié)點(diǎn)vN的最小時間的充分必要條件是對于所有的弧(vi,vj)∈A,fi(t)≤gij(t)+fj(t+gij(t)).證明.必要性.如果fi(t)集合表示從結(jié)點(diǎn)vi在t時刻出發(fā)到達(dá)目的結(jié)點(diǎn)vN的最小時間路徑的最小時間,那么fi(t)≤gij(t)+fj(t+gij(t)),否則,可以找到從vi結(jié)點(diǎn)在t時刻出發(fā)經(jīng)過vj結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)vN的更優(yōu)路徑,其走行時間比fi(t)還小,這與fi(t)是從結(jié)點(diǎn)vi在t時刻出發(fā)到達(dá)目的結(jié)點(diǎn)vN的最小時間相矛盾.充分性.如果fi(t)≤gij(t)+fj(t+gij(t))成立,設(shè)表示從結(jié)點(diǎn)vi在t時刻出發(fā)到達(dá)目的結(jié)點(diǎn)vN的任何時間依賴的路徑.那么,因?yàn)閒N(tN)=0,將這些不等式兩邊相加得到fi(t)≤gi1(t)+g12(t1)+g23(t2)+…+gN-1N(tN-1).這樣fi(t)是從結(jié)點(diǎn)i在t時刻出發(fā)到達(dá)目的結(jié)點(diǎn)vN的任何時間依賴的路徑的走行時間下界,因?yàn)閒i(t)是從結(jié)點(diǎn)vi在t時刻出發(fā)到達(dá)目的結(jié)點(diǎn)vN的時間依賴的路徑走行時間,它也是最小時間路徑的走行時間上界.因此fi(t)是最小時間路徑的最小走行時間.證畢.3t+gijt我們將時間依賴網(wǎng)絡(luò)分成FIFO網(wǎng)絡(luò)和非FIFO網(wǎng)絡(luò).在FIFO網(wǎng)絡(luò)中,由性質(zhì)1和定理4,我們很容易利用Dreyfus算法求解最小時間路徑.由性質(zhì)2和定理3我們知道Dreyfus算法、Dijkstra算法和標(biāo)號設(shè)置算法不能正確地求解非FIFO網(wǎng)絡(luò)的最小時間路徑.根據(jù)定理5,我們給出既適合于FIFO網(wǎng)絡(luò),也適合非FIFO網(wǎng)絡(luò)的最小時間路徑算法.設(shè)fi(t)表示從結(jié)點(diǎn)vi在時間t出發(fā)到達(dá)目的地結(jié)點(diǎn)vN的時間.我們首先建立一個隊(duì)列,記作LIST;A-1(i)表示弧(vj,vi)的起點(diǎn)vj的集合;succ(j)∶=i表示結(jié)點(diǎn)vj的后繼結(jié)點(diǎn)是vi.SPTDN算法.上述算法結(jié)束后,fi(t)即為t時刻從結(jié)點(diǎn)vi出發(fā)到達(dá)目的結(jié)點(diǎn)vN的最優(yōu)路徑的最小時間;succ(i)∶=j操作建立了最短路徑的生成樹.算法正確性證明.定理6.在算法的中間階段,對于任意時間t∈S,結(jié)點(diǎn)vi的fi(t)=∞或者fi(t)≥gij(t)+fj(t+gij(t));算法結(jié)束后,對于每一個結(jié)點(diǎn)vi,每一時間t∈S,各結(jié)點(diǎn)的標(biāo)記fi(t)集合滿足時間依賴網(wǎng)絡(luò)的最優(yōu)化條件.證明.如果網(wǎng)絡(luò)中不存在從結(jié)點(diǎn)vi通往目的結(jié)點(diǎn)的路徑,顯然fi(t)=∞.算法在執(zhí)行過程中,?t∈S,總是選擇違反時間依賴網(wǎng)絡(luò)的最優(yōu)化條件的弧(vi,vj)來更新結(jié)點(diǎn)vi的fi(t)值.因此,如果結(jié)點(diǎn)vi的fi(t)≠∞,那么在算法計(jì)算過程中,?t∈S,?vj按fi(t)=gij(t)+fj(t+gij(t))更新了結(jié)點(diǎn)vi的fi(t)值.在算法以后的計(jì)算中,?t∈S,fi(t)值不變或者繼續(xù)根據(jù)新的當(dāng)前結(jié)點(diǎn)vj按fi(t)=gij(t)+fj(t+gij(t))更新了結(jié)點(diǎn)vi的fi(t)值.但是,有可能?t∈S,?vj∈LIST,使得fi(t)>gij(t)+fj(t+gij(t)),而vj還沒成為當(dāng)前結(jié)點(diǎn),所以算法還沒有執(zhí)行更新fi(t)值的操作,這時弧(vi,vj)不滿足定理5的優(yōu)化條件.綜上,?t∈S,fi(t)≥gij(t)+fj(t+gij(t))成立.算法結(jié)束后,假設(shè)?t∈S,?vi∈A-1(j),使得fi(t)>gij(t)+fj(t+gij(t)),那么算法將不會結(jié)束,因?yàn)檫€沒有掃描到結(jié)點(diǎn)vj,結(jié)點(diǎn)vj仍然在LIST表中,這與算法結(jié)束相矛盾.因此,算法結(jié)束后,對于每一個結(jié)點(diǎn)vi,每一時間t∈S,各結(jié)點(diǎn)的標(biāo)記fi(t)集合滿足時間依賴網(wǎng)絡(luò)的最優(yōu)化條件.證畢.定理7.SPTDN算法求解時間依賴的網(wǎng)絡(luò)的最小時間路徑的復(fù)雜性是O(nmM2C),其中n是網(wǎng)絡(luò)的結(jié)點(diǎn)數(shù),m是弧的數(shù)目,M是時間段數(shù)目,C是所有弧中最大的權(quán)值.證明.首先證明算法在有限步驟內(nèi)收斂.算法的終止條件是LIST為空,我們用反證法來證明這一點(diǎn).假設(shè)在有限步驟內(nèi)LIST不為空,這意味著至少有一個結(jié)點(diǎn)vi反復(fù)插入到LIST表中,這又意味著在網(wǎng)絡(luò)中至少有一條最小走行時間的弧無限地減小結(jié)點(diǎn)vi的fi(t)值.最終導(dǎo)致fi(t)為負(fù)值,這與fi(t)是正的實(shí)數(shù),0是其下限相矛盾.因?yàn)樵趎個結(jié)點(diǎn)的網(wǎng)絡(luò)中,一條路徑至多包含n-1條弧,因此每個結(jié)點(diǎn)fi(t)的上界是nC,算法至多nC次減少每一結(jié)點(diǎn)fi(t)值(因?yàn)槊看螠p少的數(shù)量至少為1個單位).從算法中,我們看到當(dāng)一個結(jié)點(diǎn)vi的fi(t)={fi(t0),fi(t0+Δ),fi(t0+2Δ),…,fi(t0+(M-1)Δ)}至少有一個改變并且vi?LIST時,則將該結(jié)點(diǎn)加入到LIST表中.算法在以后的迭代中將選擇結(jié)點(diǎn)vi并且掃描指向結(jié)點(diǎn)vi的弧的集合A-1(i).由時間依賴的網(wǎng)絡(luò)的定義,我們看到它是傳統(tǒng)網(wǎng)絡(luò)模型的擴(kuò)展,即結(jié)點(diǎn)數(shù)為n,弧的數(shù)目為m的網(wǎng)絡(luò)在時間依賴的網(wǎng)絡(luò)模型中等價于n×M個結(jié)點(diǎn)和m×M條弧的網(wǎng)絡(luò).因此,算法對每一結(jié)點(diǎn)的更新至多為nMC次,對所有結(jié)點(diǎn)掃描次數(shù)的總和的上界是.證畢.應(yīng)用上述算法我們得到了圖1和圖2的最小時間路徑均是1,2,3,4;最小時間是25和6.4基于saos的交通誘導(dǎo)非FIFO網(wǎng)絡(luò)在許多領(lǐng)域具有潛在的應(yīng)用,例如,考慮計(jì)算機(jī)網(wǎng)絡(luò)通信中有一條鏈路由兩個物理通信頻道構(gòu)成的,其中一個比另一個快一些.如果鏈路管理的策略是利用第一個可用頻道發(fā)送信息,則在較慢的頻道上先發(fā)送的信息會比較快的頻道上后發(fā)送的信息滯后到達(dá)目的結(jié)點(diǎn).這意味著信息在以一種非FIFO的方式傳送.在交通網(wǎng)絡(luò)中的一個例子是:一位旅客站在火車站的站臺上,考慮是乘坐停在他前面的慢車去目的地還是等待一列快車去目的地,伴隨可能的行為是非FIFO.另一個例子是:假設(shè)一輛車先到達(dá)一條路段的交叉口,并停下來等待信號燈從紅燈變成綠燈,而第二輛車剛好在信號燈改變發(fā)生后到達(dá)交叉路口,第二輛車將不必停下來并且很容易地超過第一輛車,到達(dá)下一個信號燈,即下一個路段的端點(diǎn).這里簡單地給出我們提出的算法在智能交通系統(tǒng)(ITS)中的一個應(yīng)用.ITS的核心部分是交通誘導(dǎo)系統(tǒng).交通誘導(dǎo)方式一般分為路邊顯示版式和車