【正文】 短路徑的過程 迭代代數(shù) V1 V2 V3 V4 V5 V6 V7 選定點 Wi NBi S NBIS ∪ NBIS 0 1 2 5 2 V1 W1=0 (V2,V3,V4) (V1) 1 2 5 ① V4 W4=2 (V1,V2,V3,V5) (V1,V4) (V2,V3,V5) (V2,V3,V5) 2 ① 4 3 V2 W2=2 (V1,V3,V4) (V1,V2,V4) (V3) (V3,V5) 3 4 ② V5 W5=3 (V3,V4,V6,V7) (V1,V2,V4,V5) (V3,V6,V7) (V3,V6,V7) 4 ③ 4 5 V3 W3=4 (V1,V2,V4,V5,V6) (V,1V2,V3,V4,V5) (V6) (V6,V7) 5 ③ 5 V6 W6=4 (V3,V5,V7) (V1,V2,V3,V4,V5,V6,V7) (V7) (V7) 6 ④ V7 W7=5 (V5,V6) (V1,V2,V3,V4,V5,V6,V7) ? ? Step0：初始化 S = (v1)，與 v1直接相連的點有 v2v3v4， NB1 = (v2,v3,v4)， w1 = 0； Step1： w4 = d14 = mind1j = 2（ d12 = d14，任選其一，本文選 v4）， S = (v1,v4)， j∈ NB1 NB4=(v1,v2,v3,v5)， NB4 – S = (v2,v3,v5)， ∪ NB4S = (v2,v3,v5)； Step2： j∈ NB4 – S = (v2,v3,v5) w2 = min{w2,w4 + d42}= min{2,4}= 2， w3 = min{w3,w4 + d43}= min{5,5} = 5 2 = w2， w5 = min{w5,w4 + d45} = {∞,3} = 3 2 = w2 ∵ minwj =w2 = 2， ∴ S = (v1,v2,v4)， NB2 = (v1,v3,v4)， NB2S = (v3)， ∪ NB2S = (v3,v5)； Step3： j∈∪ NB2S = (v3,v5) w3 = min{w3,w2 + d23} = min{5,5} = 5， w5 = 3 5 = w3， ∵ minwj = w5 = 3， 19 ∴ S = (v1,v2,v4,v5)， NB5 = (v3,v4,v6,v7)， NB5S = (v3,v6,v7)， ∪ NB5S = (v3,v6,v7)； Step4： j∈ NB4 – S = (v3,v6,v7) w3 = min{w3,w5 + d53} = min{5,4} = 4， w6 = min{w6,w5 + d56} = {∞,4} = 4 = w3， w7 = min{w7,w5 + d57} = {∞,5} = 5 4 = w3 = w6， ∵ minwj = w3 = w6 = 4，任選其一，若為 w3， ∴ S = (v1,v2,v3,v4,v5)， NB3 = (v1,v2,v4,v5,v6)， NB3S = (v6)， ∪ NB3S = (v6,v7)； Step5： j∈∪ NB3S = (v6,v7) w6 = 4 w7 = 5 4 = w6， ∵ minwj = w6 = 4， ∴ S = (v1,v2,v3,v4,v5,v6)， NB6 = (v3,v5,v7)， NB6S = (v7)， ∪ NB6S = (v7)； Step6： j∈ NB6 – S = (v7) w7 = min{w7,w6 + d67} = {5,6} = 5。 至此，所有節(jié)點已標(biāo)識，則算法終止。 j∈ NBs S Step3：選定 NBi S(i∈ S)中的 wj最小值，并將其劃歸到 s中： wk = min wj； S = S ∪ {k}；若 │s│= n；所有節(jié)點已標(biāo)識，則算法終止， j∈∪ NBs–S i∈ S 否則，轉(zhuǎn)到 Step2． 圖 31為帶權(quán)值的無向圖 G7，對 G7分別用 Dijkstra算法和優(yōu)化了的 Dijkstra算法進行求解，則可得從 v1到其余各節(jié)點的最短路徑 [9]。 Step1：若 dsk = min dsj ，則 S = S ∪ { k}。 設(shè) NBi為節(jié)點 i的鄰居集合； S為標(biāo)識集合； wj是從源點 s到節(jié)點 j的最短路徑長度； pj是從 s到 j的最短路徑中 j點的前一節(jié)點； dij是節(jié)點 i到節(jié)點 j的距離。然后對 k鄰居集合與標(biāo)識集合的差集 [8](NBk S)中節(jié)點的值進行更新，從標(biāo)識集合 s中所有節(jié)點的鄰居集合的并集與標(biāo)識集合的差集(∪ NBsS， i∈ S)中選擇一個 wk值最 小的節(jié)點作為下一個轉(zhuǎn)接點，并劃歸到標(biāo)識集合 S中。 通過分析傳統(tǒng) Dijkstra算法的基本思路，傳統(tǒng) Dijkstra算法存在如下兩點不足： (1)當(dāng)從未標(biāo)記節(jié)點集合 T中選定一個節(jié)點 k作為轉(zhuǎn)接點后時，需掃描未標(biāo)記節(jié)點集合 T中的節(jié)點 j并更新其 wj值，而未標(biāo)記節(jié)點集合 T中往往包含大量與轉(zhuǎn)接節(jié)點 k 不直接相連的節(jié)點i(即 dki =∞)； (2)在未標(biāo)記節(jié)點集合 T中選擇一個 w值最小的節(jié)點作為下一個轉(zhuǎn)接節(jié)點，然而下一個轉(zhuǎn)接節(jié)點往往是與標(biāo)記節(jié)點集合 S中的節(jié)點直接相連的。 (可從與 s直接相連的 j中考慮 ) 若 dsi = min dsj j與 s直接相連，則將 i劃歸到 S中，即 S ={s， i}， T = T{i}； j∈ T pi =s。 dij提節(jié)點 i到節(jié)點 j的距離 (i與 j直接相連，否則 dij = ∞)． 算法步驟如下： Step0： S = {s}； T = MS； wj = dij(j∈ T， s與 j直接相連 )或 wj = ∞(j ∈ T， s與 j不直接相連 )。 （二） 思路 Dijkstra算法基本方法：設(shè) wj是從源點 s到節(jié)點 j的最短路徑長度； pj是從 s到 j的最短路徑中 j點的前一節(jié)點。其時間復(fù)雜度為 O(N2)；采 用鄰接矩陣存儲網(wǎng)絡(luò)拓撲結(jié)構(gòu)，需要 (N N)的存儲空間，隨著節(jié)點數(shù)N 的增大，其計算效率和存儲效率越低。 二、 本文對 Dijlstra 優(yōu)化算法研究 本文采用第一類優(yōu)化算法減小搜索范圍的思路對 Dijkstra 算法進行優(yōu)化。與數(shù)組類似，集合類可以把對象放入容器中，然后再取出．但集合的使用方法與數(shù)組不同，擁有用于插入和刪除項的專用方法。 NET框架提供的特殊 類 Hashtable。若采用鄰接表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，其存儲量為 E(E為節(jié)點列表中，同節(jié)點關(guān)聯(lián)的所有邊的數(shù)目 )，可節(jié)省大量的存儲空間，尤其是在表示與節(jié)點和邊相關(guān)信息較多的地理網(wǎng)絡(luò)時，更為有效。對于網(wǎng)絡(luò)數(shù)據(jù)的存儲，傳統(tǒng)的是采用圖論中的鄰接矩陣方法，其存儲量為 NN(N為網(wǎng)絡(luò)中節(jié)點數(shù) )。 （二） 改進算法的存儲結(jié)構(gòu) 在實際工作中，還要建立起空間數(shù)據(jù)結(jié)構(gòu)。在對現(xiàn)實問題中的交通圖初始化為網(wǎng)絡(luò)拓 撲圖時，雖然終點已知，而源點 尚未確定，但依據(jù)常識離案發(fā)地段最近的派出所應(yīng)為案發(fā)地段所在轄區(qū) 派出所，或其周邊派出所，也就是源點的選取范圍可以確定。 13 表 24 三種算法在搜索質(zhì)量方面的對比 節(jié)點數(shù) Dijkstra A*算法 遺傳算法 16 15(100%) 12(80%) 15(100%) 32 31(100%) 25(81%) 29(94%) 43 42(100%) 32(76%) 38(90%) 62 61(100%) 40(66%) 56(92%) 78 77(100%) 45(58%) 71(92%) 由表 24可以看出：當(dāng)?shù)貓D節(jié)點個數(shù)和弧數(shù)量比較多時， Dijkstra算法是一種遍歷算法，每次能保證 100%搜索到最短路徑，遺傳算法搜索到最短路徑的成功率比 Dijkstra算法低一些， A*算法最低，且這種差距在節(jié)點數(shù)和弧數(shù)量越大時更加明顯。 對 5張地圖分別采用三種算法進行路徑規(guī)劃，三者各自搜索到最短路徑的情況如表24所示。對于實際地圖而言，由于節(jié)點與道路的數(shù)量一般都很的大， Dijkstra算法在搜索速度方面弱勢明顯。 二、 Dijkstra 算法與其他主流算法的比較 （一） 搜索速度比較 對 5張圖分別采用 Dijkstra算法、 A*算法 [3]、遺傳算法 [4]進行路徑規(guī)劃，他們各自花費的時間如表 23所示。當(dāng)選出 v4后，需要對 U中的各個頂點的距離進行調(diào)整，在調(diào)整過程中利用到 wi =min{wi,w4+d4i}其中 i≠1， 4(1， 4已經(jīng)在 S中 )即需要對 wi和w4+d4i進行比較，但我們在對 w3,w5,w7進行調(diào)整時可以發(fā)現(xiàn)由于 d43,d45,d47? E(G)即它們的權(quán)值為 ∞，所以調(diào)整時是沒有必要進行比較的，在這里多進行了 3次比較。 下一個例子說明 Dijkstra算法存在的缺陷： 例：圖 27所示為一帶權(quán)圖 G(V， E， W)，求從 v1出發(fā)到其它各個頂點的最短路徑長度。 如節(jié)點數(shù)為 n的圖，用 Dijkstra算法計算最短路徑總共需要迭代 n一 1次，每次迭代都醫(yī)院 1 已 標(biāo)號 距離 0 醫(yī)院 2 已 標(biāo)號 距離 ∞ 醫(yī)院 3 已 標(biāo)號 距離 4 醫(yī)院 4 已 標(biāo)號 距離 9 12 4 5 6 醫(yī)院 1 已 標(biāo)號 距離 0 醫(yī)院 2 未標(biāo)號 距離 12 醫(yī)院 3 已 標(biāo)號 距離 4 醫(yī)院 4 以 標(biāo)號 距離 9 12 4 5 6 10 新加一個節(jié)點到臨時節(jié)點集合中，由于第 i次迭代時不在臨時節(jié)點集合中的節(jié)點 數(shù)為ni．即第 i次迭代需對 ni個節(jié)點進行處理，因此其所需的處理數(shù)為 11( 1)() 2ninnni?????? ，對 n個節(jié)點網(wǎng)絡(luò)的時間復(fù)雜度是 O(n2)。 5)輸出結(jié)果。更新方法如下： 如果 i的最短路徑邊 ij 的長度 j目前的最短路徑，則 j的最短路徑更新為 i的最短路徑邊ij的長度，否則不變（也就是意味著通過 i走向 j比原來的方向走向 j能獲得 更短的路徑）。若無法找到，則說明所有頂點已標(biāo)號，或者所有的未標(biāo)號頂點都是無法到達的，轉(zhuǎn) 5)。 0 1 4 2 3 100 7 給定問題的算法分析 : 1)初始化：起點的最短路徑為 0，其他頂點的最短路徑為 ∞，所有頂點未標(biāo)號。各個醫(yī)院之間的路程和各醫(yī)院到小湯山之間的路程已知 (有可能沒有直通道路 ),由于非典病人的特殊性 ,在往小湯山轉(zhuǎn)運的過程中只能在收治病人的醫(yī)院中轉(zhuǎn)。 例 :北京的小湯山醫(yī)院已經(jīng)投入使用了 ,在抗擊非典的戰(zhàn)役中發(fā)揮了重要的作用。如果所有點已標(biāo)記，則算法完全推出，否則，記 k=i，轉(zhuǎn)到 2)再繼續(xù)。從已標(biāo)記的點中找到直接連接到點 i的點 j*，作為前一點 ， 設(shè)置： i=j*。從所有未標(biāo)記的結(jié)點中，選取 wj中最小的一個 i:wi=min wj，（所有未 6 標(biāo)記的點 j） ， 點 i就被選為最短路徑中的一點，并設(shè)為已標(biāo)記的。 2)檢驗從所有已標(biāo)記的點 k到其直接連接的未標(biāo)記的點 j的距離，并設(shè)置： wj=min{wj, wk+dkj }式中， dkj 是從點 k到 j的直接連接距離。求解從起源點 s到點 j的最短路徑算法的基本過程如下： 1)初始化。網(wǎng)絡(luò)中所有結(jié)點首先初始化為未標(biāo)記結(jié)點，在搜索過程中和最短路徑中的結(jié)點相連通的結(jié)點為臨時標(biāo)記結(jié)點，每次循環(huán)都是從臨時標(biāo)記結(jié)點中搜索距源點路徑長度最短的結(jié)點作為永久標(biāo)記結(jié)點，直至找到目標(biāo)結(jié)點或者所有的結(jié)點都成為永久標(biāo)記結(jié)點來結(jié)束算法。 （一） 原理 Dijkstra算法是 1959年由 E． W． Dijkstra提出的圖論中求最短路徑的一個著名的算法，使用其可以求得圖中一點到其他各頂點的最短路徑。 Dijkstra 一般的表述通常有兩種方式，一種用永久和臨時標(biāo)號方式，一種是用 OPEN, CLOSE 表的方式，這里均采用永久和臨時標(biāo)號的方式。主要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。 Dijkstra 算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低 [2]。 5 第二章 Dijkstra 經(jīng)典算法 Dijkstra 算法是典型最短路算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。由此可見對最短路徑問題的研究是非常有意義的。 4 三 、 本文研究 的 內(nèi)容及意義 隨著社會的不斷進步，最短路徑算法在人們的日常生活顯得越來越重要。網(wǎng)絡(luò)中所有節(jié)點首先初始化為未標(biāo)記節(jié)點，在搜索過程中和最短路徑節(jié)點相連通的節(jié)點為臨時標(biāo)記節(jié)點，每一次循環(huán)都是從臨時標(biāo)記節(jié)點中搜索距離原點路徑長度最短的節(jié)點作為永久標(biāo)記節(jié) 點，直至找到目標(biāo)節(jié)點或者所有節(jié)點都成為永久標(biāo)