【正文】 ，使 s到 i的距離最小，并將 i劃歸到 S。 Step2：修改 T中 j節(jié)點的 wj值： wj = min(wj,wi + dij)；若 wj值改變，則 pj = i． j∈ T i∈ S Step3：選定所有的 wj最小值，并將其劃歸到 S中： wi = min wj； S=S∪ {i}； T=T{i}；若 │S│= n, 所有節(jié)點已標(biāo)識，則算法終 j∈ T 止，否則，轉(zhuǎn)人 Step2。 優(yōu)化算法描述 基于上述兩點不足，對傳統(tǒng) Dijkstra算法進行優(yōu)化，算法優(yōu)化思路為：首先從源點 s的鄰居集合 NBS(與 s直接相連的節(jié)點集合 )中選擇距離最小的鄰居節(jié)點 k作為轉(zhuǎn)接點，同時將劃歸到標(biāo)識集合 S(初始時， S為 {s})。重復(fù)上述過程，直到所有的節(jié)點都被標(biāo)識過，即 │S│=n，算法結(jié)束。算法步驟如下： Step0：初始化 S = {s}； wi = dsi(i∈ NBs)；否則 = ∞(I ? NBs)； pi=s。 j∈ NBs Step2：修改 NBk S中的 wj值： wj = min { wj,wk +dkj }；若 wj值改變，則 pj = k。 17 圖 非負權(quán)值圖 經(jīng)典 Dijkstra算法求解過程： Step0：初始化 S = (v1)， w1 = 0， T = (v2,v4, v3,v5, v6,v7)； Step1： w4 = d14 = mind1j = 2（ d12 = d14，任選其一，本文選 v4）， S = (v1,v4)， T = j∈ T (v2,v3,v5,v6,v7)； Step2： T = (v2,v3,v5,v6,v7) 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， w6 = min{w6， w4 + d46} = ∞， () w7 = min{w7， w4 + d47} = ∞， () ∵ minwj =w2 = 2， ∴ S = (v1,v2,v4)， T = (v3,v5,v6,v7)； Step3： T = (v3,v5,v6,v7) w3 = min{w3， w2 + d23} = min{5,5} = 5， w5 = min{w5， w2 + d25} = min{3, ∞} = 3 5 = w3， w6 = min{w6， w4 + d46} = ∞， () w7 = min{w7， w4 + d47} = ∞， () ∵ minwj = w5 = 3， ∴ S = (v1,v2,v4,v5)， T = (v3,v6,v7)； Step4： T = (v3,v6,v7) 18 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)， T = (v6,v7)； Step5： T = (v6,v7) w6 = min{w6， w3+d36}= min{4， ∞} = 4， w7 = min{w7， w3 + d37} = {5， ∞} = 5 4 = w3 = w6， ∵ minwj = w6 = 4， ∴ S = (v1,v2,v3,v4,v5,v6)， T = (v7)； Step6： T = (v7) w7 = min{w7， w6 + d67} = {5， 6} = 5。 最終結(jié)果為 w2 = 2， w3=4， w4=2， w5=3， w6=4， w7=5， w6=4， w7=5。 至此，所有節(jié)點已標(biāo)識，則算法終止。 優(yōu)化算法的特點 傳統(tǒng) Dijkstra算法基于廣度優(yōu)先的搜索策略，從指定節(jié)點出發(fā)，通過權(quán)值迭代 20 遍歷所有其他節(jié)點后，最后得到從指定節(jié)點到其他各節(jié)點的最短路徑樹。 本文提出的優(yōu)化算法在更新最短路徑值與選擇最短路徑值最小的節(jié)點時，僅僅涉及到節(jié)點的鄰居集合及已標(biāo)識集合中所有節(jié)點的鄰居集合與已標(biāo)識集合的差集，其運行時間取決于轉(zhuǎn)接點的鄰居集合的元素數(shù)量多少 (而該數(shù)量值往往小于未標(biāo)識集合中的元素個數(shù) )。另外，根據(jù)圖中頂點和邊的個數(shù)，可以求出頂點的平均出度 e=m／ n(m為邊數(shù)， n為頂點數(shù) )，一般在 GIS的網(wǎng)絡(luò)圖中， e∈ [2， 5]，由于 Step Step3都是搜索與 Vi(i=l， 2， 3,? ， n)相鄰的結(jié)點操作，時間復(fù)雜度均為 O(Ne)； Step3的時間復(fù)雜度為 O(m)，即 O(ne)；步驟 (5)的時間復(fù)雜度為 O(ne)。 優(yōu)化 Dijkstra 算法與原 Dijkstra 經(jīng)典算法比較 由 圖 G7的求解可以看出，優(yōu)化了的 dijkstra算法在Step2和 Step3中較經(jīng)典的 Dijkstra算法減少了步驟 ()()()()，減少了計算次數(shù)，提高了搜索速度。在分析傳統(tǒng) Dijkstra算法的基礎(chǔ)上，針對傳統(tǒng)Dijkstra算法存在的兩點不足之處，對其進行了優(yōu)化處理。 21 第 4章 優(yōu)化 Dijkstra算法的應(yīng)用 優(yōu)化算法在上海市物流中的實現(xiàn) 地圖說明 上海，中國最繁華的城市之一，是我國的優(yōu)秀旅游城市。本文采用 C語言實現(xiàn)了改進算法，并在 Intel P4M、 512RAM運行環(huán)境下，對總共有 81339條弧、 60828個節(jié)點的上海市地圖進行實際測試，上海市交通道路組成如圖 。系統(tǒng)屬性數(shù)據(jù)主要包括兩類：節(jié)點表數(shù)據(jù)，邊表數(shù)據(jù)。 23 算法實現(xiàn) 為方便起見我們將任意相鄰兩點間是距離預(yù)設(shè)為 1，即 dij = 1。程序設(shè)置地圖拖動、放大、縮小、載入空間拓撲、計算最短路徑等功能，如圖 。 25 算法優(yōu)化前后對比 以上海地圖為原型對原 Dijkstra 經(jīng)典算法和優(yōu)化算法在不同節(jié)點范圍內(nèi)進行了 5 次測試，我們均以節(jié)點 46616300077 為起始節(jié)點，選取遠近不同的終節(jié)點。 表 算法優(yōu)化前后搜索測試 實驗 編號 起點 終點 構(gòu)建空間拓撲時間（秒） 搜索時間（秒） 最短路徑 長度 經(jīng)典 優(yōu)化 1 46616300077 46616300090 42 7 7 1 2 46616300077 46616300087 42 12 8 30 3 46616300077 46616400035 53 1017 56 51 4 46616300077 46617600009 53 1570 71 79 5 46616300077 46617000006 53 1960 92 96 注：由于 4661630007 46616300090、 46616300087 節(jié)點處于同一 466163 區(qū)域， 2 次實驗通過 SqlCommand myCommand = new SqlCommand(select * from NSHANGHAI where MAPID=39。, myConnection)語句修改空間拓撲 MAPID 為 466163 的區(qū)域，構(gòu)建空間拓撲時間為 42 秒， 5 次實驗空間拓撲為整個上海市地圖。 26 第 5章 總結(jié)與展望 全文總結(jié) 本文基于 Dijkstra算法，針對 Dijkstra算法在實際應(yīng)用中 搜索速度慢，搜索效率低，時間花費多 的的缺陷，對其進行了優(yōu)化。 展望 目前基于 Dijkstra 算法的優(yōu)化算法很多，但是這些優(yōu)化算法大多只對它進行了單方面的優(yōu)化。以鄰接矩陣或關(guān)聯(lián)矩陣為基礎(chǔ)的算法，有大量的 0元素或 ∞元素，這些無效元素占用了大量的計算機內(nèi)存，所以需在此 基礎(chǔ)上進行數(shù)據(jù)存儲的優(yōu)化，如果在記錄網(wǎng)絡(luò)結(jié)構(gòu)的關(guān)系時，只記錄與網(wǎng)絡(luò)節(jié)點相關(guān)的節(jié)點和邊，則可以大大減少矩陣的行或列名這樣一來構(gòu)成的點 邊關(guān)系矩陣也大大減少了0 元素或 ∞元素，從而起到節(jié)約內(nèi)存。 using 。 namespace WindowsApplication1 { /// summary /// 有向邊類 /// /summary class Edge //抽象邊類 { private string s_StartNodeID=N/A。 //終點ＩＤ private double s_Weight=1。 } set { = value。 } set { = value。 } set { = value。 using 。 using 。 private ArrayList edgeList 。 = new ArrayList() 。 } } public ArrayList EdgeList { get { return 。 } } } } 計算最小路徑， RoutePlanResult 方法，用于獲取權(quán)值最小的路徑 using System。 using 。 namespace WindowsApplication1 { class RoutePlanner { public RoutePlanner() { } region Paln //獲取權(quán)值最小的路徑 public RoutePlanResult Paln(ArrayList nodeList, string originID, string destID) { PlanCourse planCourse = new PlanCourse(nodeList, originID)。 region 計算過程 while (curNode != null) { PassedPath curPath = planCourse[]。 double tempWeight = + 。 ()。 i 。 } ()。 //獲取下一個未處理節(jié)點 curNode = (planCourse, nodeList, originID)。 } 32 endregion region private method region GetResult //從 PlanCourse表中取出目標(biāo)節(jié)點的 PassedPath，這個 PassedPath即是規(guī)劃結(jié)果 private RoutePlanResult GetResult(PlanCourse planCourse, string destID) { PassedPath pPath = planCourse[destID]。 return result1。 for (int i = 0。 i++) { passedNodeIDs[i] = [i].ToString