【正文】 B1 (v1,v2,v3,v5)， NB4 – S = (v2,v3,v5)， ∪ NB4S = (v2,v3,v5)； 19 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， ∴ 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é)點已標識，則算法終止。 j∈ NBs S Step3：選定 NBi S(i∈ S)中的 wj最小值，并將其劃歸到 s中： wk = min wj； S = S ∪ {k}；若 │s│= n；所有節(jié)點已標識，則算法終止， j∈∪ NBs–S i∈ S 否則，轉(zhuǎn)到 Step2． 圖 G7，對 G7分別用 Dijkstra算法和優(yōu)化了的 Dijkstra算法進行求解，則可得從 v1到其余各節(jié)點的最短路徑。 Step1：若 dsk = min dsj ，則 S = S ∪ { k}。 設(shè) NBi為節(jié)點 i的鄰居集合； S為標識集合； wj是從源點 s到節(jié)點 j的最短路徑長度； pj是從 s到 j的最短路徑中 j點的前一節(jié)點； dij是節(jié)點 i到節(jié)點 j的距離。然后對 k鄰居集合與標識集合的差集 (NBk S)中節(jié)點的值進行更新，從標識集合 s中所有節(jié)點的鄰居集合 的并集與標識集合的差集 (∪ NBs S， i∈ S)中選擇一個 wk值最小的節(jié)點作為下一個轉(zhuǎn)接點，并劃歸到標識集合 S中。 通過分析傳統(tǒng) Dijkstra算法的基本思路，傳統(tǒng) Dijkstra算法存在如下兩點不足： 16 (1)當從未標記節(jié)點集合 T中選定一個節(jié)點 k作為轉(zhuǎn)接點后時，需掃描未標記節(jié)點集合 T中的節(jié)點 j并更新其 wj值，而未標記節(jié)點集合 T中往往包含 大量與轉(zhuǎn)接節(jié)點 k 不直接相連的節(jié)點 i(即 dki = ∞)； (2)在未標記節(jié)點集合 T中選擇一個 w值最小的節(jié)點作為下一個轉(zhuǎn)接節(jié)點，然而下一個轉(zhuǎn)接節(jié)點往往是與標記節(jié)點集合 S中的節(jié)點直接相連的。 (可從與 s直接相連的 j中考慮 ) 若 dsi = min dsj j與 s直接相連，則將 i劃歸到 S中，即 S ={s， i}， T = T{i}； j∈ T pi =s。 S是標識集合； T是未標識集合； M是節(jié)點集合． 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算法的改進，本文在對傳統(tǒng) Dijkstra算法分析的基礎(chǔ)上，對其進行了優(yōu)化，優(yōu)化算法只對最短路徑上節(jié)點的鄰居做處理，而不涉及到其他節(jié)點。 優(yōu)化算法的目標 Dijkstra算法用來求解圖上從任 一節(jié)點 (源點 )到其余各節(jié)點的最短路徑。使用 Hashtable最大的優(yōu)點就是大大降低數(shù)據(jù)存儲和查找的時間花費，幾乎可看成是常數(shù)時間。 .NET框架包含特殊類，比如通常所說的集合類用于存儲對象。但鄰接表卻難 以判斷兩節(jié)點之間的關(guān)系，因此本文提出利用。通常的地理網(wǎng)絡(luò)，盡管節(jié)點很多，但與節(jié)點相關(guān)聯(lián)的節(jié)點數(shù)目并不多，一般都為稀疏圖，將會浪費大量的空間。網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)使用的是 ―邊和節(jié)點 ‖的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)是建立在圖論的基礎(chǔ)上，節(jié)點可用來定義邊的連接關(guān)系。利用 MapObjects2組件提供 的 (expression)記錄集篩選方法，根據(jù)案發(fā)地段 (終點 )的不同，動態(tài)選取案發(fā)地段所在轄區(qū)及相鄰轄區(qū)的道路圖層及派出所圖層數(shù)據(jù)進行最短路徑查詢，從而有效地減少了拓撲圖中節(jié)點總數(shù) n的值。 14 第 3章 Dijkstra優(yōu)化算法研究 多種 Dijkstra 優(yōu)化算法的研究 [6] 第一類優(yōu)化算法 ——減小算法中成功搜索的搜索范圍 減小算法中成功搜索的搜索范圍以盡 快到達目標節(jié)點。表中括號外數(shù)據(jù)為各算法實際得到最短路徑數(shù)，括號內(nèi)數(shù)據(jù)則為各算法實際得到路徑數(shù)和應(yīng)該規(guī)劃出的最短路徑數(shù) n1之比。 搜索成功率比較 對于具有 n個節(jié)點的地圖，其待規(guī)劃節(jié)點的個數(shù)為 n1（除起點節(jié)點外，其他均可作為待規(guī)劃節(jié)點），由于每個待規(guī)劃節(jié)點對應(yīng)于一條最短路徑，所以對每張具有n個節(jié)點的 地圖而言，應(yīng)該規(guī)劃出 n1條最短路徑。 表 三種算法在搜索速度上的對比 節(jié)點數(shù) 搜索速度 Dijkstra算法 A*算法 遺傳算法 16 1 1 2 32 4 2 4 43 7 3 6 62 15 5 9 78 25 7 12 由表 ：當?shù)貓D節(jié)點個數(shù)和弧的條數(shù)比較少時，三種算法所花費的時間差不多，當節(jié)點個數(shù)和弧的條數(shù)比較多時， A*算法最快，遺傳算法其次，Dijkstra算法最慢，而且這種差距將隨節(jié)點和弧數(shù)量的增加而變得更加明顯。后面的各步也都出現(xiàn)類似的情況 (后略 )，尤其是當圖的邊數(shù)相對較少時更為明顯。 圖 權(quán)圖 G 解： wi表示由源 v1到點 vi的最短距離； S表示已求出最短路徑的頂點集合，其初始值為 S{v1}； k表示剛選出的頂點的編號；選出 vk后修改 U中各頂點的距離的方法為：wi=min{wi， dki}； 下表通過 Dijkstra算法來求解圖 ： v1 初始 第一步 第二步 第三步 … v2 15 9 v3 ∞ ∞ v4 4 v5 ∞ ∞ v6 ∞ 10 v7 ∞ ∞ S={v1} v4 v2 k 12 w S v1,v4 v1,v2,v4 在上表中選出頂點 v4加入到 S時一共進行了 6次比較，其中四次是與 ∞作比較，也就是說這四次完全沒有必要進行比較。在實際應(yīng)用當中，使用 Dijkstra算法查找最短路徑時耗費大量的時間進行數(shù)據(jù)的比較，本文對 Dijkstra算法進行分析，通過改變算法實現(xiàn)減少不必要節(jié)點計算的時間，提高算法的效率達到對其進行優(yōu)化。 例 : 找所有未標號中距離最短的頂點為 醫(yī)院 1,將 1做標號 ,更新與 1相鄰的 2和 3的距離 醫(yī)院 1 未標號 距離 0 醫(yī)院 2 未標號 距離 ∞ 醫(yī)院 3 未標號 距離 ∞ 醫(yī)院 4 未標號 距離 ∞ 12 4 5 6 9 找所有未標號中距離最短的頂點為 醫(yī)院 3,將 3做標號 ,更新與 1相鄰的 4的距離 找所有未標號中距離最短的頂點為 醫(yī)院 4,將 4做標號 ,更新與 1相鄰的 2的距離 (因為距離 4+邊 2,4 的長度 距離 2,所以不更新 ) 醫(yī)院 1 已 標號 距離 0 醫(yī)院 2 未標號 距離 ∞ 醫(yī)院 3 已 標號 距離 4 醫(yī)院 4 未標號 距離 9 12 4 5 6 醫(yī)院 1 已 標號 距離 0 醫(yī)院 2 未標號 距離 ∞ 醫(yī)院 3 未標號 距離 4 醫(yī)院 4 未標號 距離 ∞ 12 4 5 6 10 找所 有未標號中距離最短的頂點為 醫(yī)院 2,將 2做標號 ,已沒有與 2相鄰的未標號頂點需要更新了 再次找所有未標號中距離最短的頂點已找不到 ,得結(jié)果 d(2)=12,d(3)=4,d(4)=9. Dijkstra算法的優(yōu)缺點 Dijkstra 算法能夠保證 100%找到最優(yōu)解，但其搜索速度較慢，搜索效率非常低，時間花費較多，一般只能用于離線的路徑規(guī)劃問題。 4)轉(zhuǎn) 2。 3)更改所有與 i直接相鄰的未標號頂點的最短路徑。 2)在所有未標號的頂點中找出最短路徑最短的頂點 i?，F(xiàn)在 ,黨和政府交給了你一個光榮而艱巨的任務(wù) ,計算出小湯山到市內(nèi)各收治醫(yī)院的最短路徑 ,為抗非事業(yè)做出你應(yīng)有的 貢獻?，F(xiàn)在 ,在北京市內(nèi)有若干家收治非典病人的醫(yī)院。 7 Dijkstra算法最短路徑應(yīng)用演示 圖 Dijkstra算法最短路徑應(yīng)用 演示圖 表 從 0節(jié)點到 4節(jié)點的最短路徑 循環(huán) 紅點集 S K D{0} D{1} D{2} D{3} D{4} P{0} P{1} P{2} P{3} P{4} 初始化 {0} 0 10 ∞ 30 100 1 0 1 0 0 1 {0,1} 1 0 10 60 30 100 1 0 1 0 0 2 {0,1,3} 3 0 10 50 30 90 1 0 3 0 3 3 {0,1,3,2} 2 0 10 50 30 60 1 0 3 0 2 4 {0,1,3,2,4} 4 0 10 50 30 60 1 0 3 0 2 Dijkstra算法應(yīng)用 給定簡單無向圖 G,指定一頂點 Vi為起點 ,對于任意 Vj∈ G 且 i≠j,求 Vi到 Vj 的最短路徑的長度。 5)標記點 i。 4)找到點 i的前一點。 3)選取下一個點。起源點設(shè)置為： ① ws=0, ps為空； ② 所有其他點 : wi=∞, pi=?； ③ 標記起源點 s，記 k=s,其他所有點設(shè)為未標記的。 假設(shè)每個點都有一對標號 (wj, pj)，其中 wj 是從起源點 s到點 j的最短路徑的長度 (從頂點到其本身的最短路徑是零路 (沒有弧的路 )，其長度等于零 )； pj 則是從 s到 j的最短路徑中 j點的前一點。原始的 Dijkstra算法將網(wǎng)絡(luò)結(jié)點分成 3部分：未標記結(jié)點、臨時標記結(jié)點和永久標記結(jié)點。 ④ 改進數(shù)據(jù)的組織結(jié)構(gòu)，用類或結(jié)構(gòu)體來組織節(jié)點、線路并建立拓撲關(guān)系可以提高數(shù)據(jù)搜索效率。 ② 由于現(xiàn)實中只需要查詢起點和終點間的最短路徑，而不需要求出起點到多有節(jié)點的最短路徑，所以根據(jù)需要只要找到起 點到終點的最短距離即可退出循環(huán)處理過程，縮短查詢時間。然后對 k 另據(jù)集合與表示集合的差集，（ NBk S）中節(jié)點 j 的 wj值進行更新，從標識集合 S 中所有節(jié)點的鄰居集合的并集與標識集合 S 的差集（ ∪ NBi S,i∈ S）中選擇一個 wk值最小的節(jié)點作為下一個轉(zhuǎn)接點，并劃歸為到標識集合 S 中。所以針對地理信息中的海量信息需要尋求算法優(yōu)化，對 Dijkstra 算法優(yōu)化的思 5 路主要有： ① 縮小節(jié)點的搜索范圍，只對最短路徑上節(jié)點的鄰居作處理，而不涉及相離節(jié)點的其他節(jié)點。 本文研究目標和內(nèi)容 Dijkstra 算法的空間復(fù)雜度 O(N2)，采用鄰接矩陣存儲網(wǎng)絡(luò)拓撲結(jié)構(gòu)，需要（ NN）的存儲空間，查詢速率較快，在數(shù)秒內(nèi)即可完成查詢，所用時間在用戶的容忍范圍內(nèi)。由此可見對最短路徑問題的研究是非常有意義的。 研究的意義 隨著社會的不斷進步，最短路徑算法在人們的日常生活顯得越來越重要。網(wǎng)絡(luò)中所有節(jié)點首先初始化為未標記節(jié)點，在搜索過程中和最短路徑節(jié)點相連通的節(jié)點為臨時標記節(jié)點，每一次循環(huán)都是從臨時標記節(jié)點中搜索距離原點路徑長度最短的節(jié)點作為永久標記節(jié)點，直至找到目標節(jié)點或者所有節(jié)點都成為永久標記節(jié)點才結(jié)束算法。 Y 問題的初始（侯選）解