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