【正文】 i++) { passedNodeIDs[i] = [i].ToString()。 return result1。 //獲取下一個(gè)未處理節(jié)點(diǎn) curNode = (planCourse, nodeList, originID)。 i 。 double tempWeight = + 。 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)。 } } } } 計(jì)算最小路徑， RoutePlanResult 方法，用于獲取權(quán)值最小的路徑 using System。 = new ArrayList() 。 using 。 } set { = value。 } set { = value。 namespace WindowsApplication1 { /// summary /// 有向邊類 /// /summary class Edge //抽象邊類 { private string s_StartNodeID=N/A。以鄰接矩陣或關(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)存。 26 第 5章 總結(jié)與展望 全文總結(jié) 本文基于 Dijkstra算法，針對(duì) Dijkstra算法在實(shí)際應(yīng)用中 搜索速度慢，搜索效率低，時(shí)間花費(fèi)多 的的缺陷，對(duì)其進(jìn)行了優(yōu)化。 表 算法優(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。程序設(shè)置地圖拖動(dòng)、放大、縮小、載入空間拓?fù)?、?jì)算最短路徑等功能，如圖 。系統(tǒng)屬性數(shù)據(jù)主要包括兩類：節(jié)點(diǎn)表數(shù)據(jù)，邊表數(shù)據(jù)。 21 第 4章 優(yōu)化 Dijkstra算法的應(yīng)用 優(yōu)化算法在上海市物流中的實(shí)現(xiàn) 地圖說明 上海，中國最繁華的城市之一，是我國的優(yōu)秀旅游城市。 優(yōu)化 Dijkstra 算法與原 Dijkstra 經(jīng)典算法比較 由 圖 G7的求解可以看出，優(yōu)化了的 dijkstra算法在Step2和 Step3中較經(jīng)典的 Dijkstra算法減少了步驟 ()()()()，減少了計(jì)算次數(shù)，提高了搜索速度。 本文提出的優(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ù) )。 至此，所有節(jié)點(diǎn)已標(biāo)識(shí)，則算法終止。 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。算法步驟如下： Step0：初始化 S = {s}； wi = dsi(i∈ NBs)；否則 = ∞(I ? NBs)； pi=s。 優(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})。 Step1：在 T中找到節(jié)點(diǎn) i，使 s到 i的距離最小，并將 i劃歸到 S。其時(shí)間復(fù)雜度為 O(N2)；采用鄰接矩陣存儲(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，需要 (NN)的存儲(chǔ)空間，隨著節(jié)點(diǎn)數(shù) N的增大，其計(jì)算效率和存儲(chǔ)效率越低。與數(shù)組類似，集合類可以把對(duì)象放入容器中，然后再取出．但集合的使用方法與數(shù)組不同，擁有用于插入和刪除項(xiàng)的專用方法。若采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其存儲(chǔ)量為 E(E為節(jié)點(diǎn)列表中，同節(jié)點(diǎn)關(guān)聯(lián)的所有邊的數(shù)目 )，可節(jié)省大量的存儲(chǔ)空間，尤其是在表示與節(jié)點(diǎn)和邊相關(guān)信息較多的地理網(wǎng)絡(luò)時(shí)，更為有效。 第二類優(yōu)化算法 ——改進(jìn)算法的存儲(chǔ)結(jié)構(gòu) 在實(shí)際工作中，還要建立起空間數(shù)據(jù)結(jié)構(gòu)。 表 三種算法在搜索質(zhì)量方面的對(duì)比 節(jié)點(diǎn)數(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%) 由表 ：當(dāng)?shù)貓D節(jié)點(diǎn)個(gè)數(shù)和弧數(shù)量比較多時(shí)， Dijkstra算法是一種遍歷算法，每次能保證 100%搜索到最短路徑，遺傳算法搜索到最短路徑的成功率比Dijkstra算法低一些， A*算法最低，且這種差距在節(jié)點(diǎn)數(shù)和弧數(shù)量越大時(shí)更加明顯。對(duì)于實(shí)際地圖而言，由于節(jié)點(diǎn)與道路的數(shù)量一般都很的大， Dijkstra算法在搜索速度方 13 面弱勢(shì)明顯。當(dāng)選出 v4后，需要對(duì) U中的各個(gè)頂點(diǎn)的距離進(jìn)行調(diào)整，在調(diào)整過程中利用到 wi =min{wi， w4+d4i}其中 i≠1， 4(1， 4已經(jīng)在 S中 )即需要對(duì) wi和 w4+d4i進(jìn)行比較，但我們?cè)趯?duì) w3,w5,w7進(jìn)行調(diào)整時(shí)可以發(fā)現(xiàn)由于 d43，d45， d47 ? E(G)即它們的權(quán)值為 ∞，所以調(diào)整時(shí)是沒有必要進(jìn)行 比較的，在這里多進(jìn)行了 3次比較。 如節(jié)點(diǎn)數(shù)為 n的圖，用 Dijkstra算法計(jì)算最短路徑總共需要迭代 n一 1次，每次迭代都新加一個(gè)節(jié)點(diǎn)到臨時(shí)節(jié)點(diǎn)集合中 ，由于第 i次迭代時(shí)不在臨時(shí)節(jié)點(diǎn)集合中的節(jié)醫(yī)院 1 已 標(biāo)號(hào) 距離 0 醫(yī)院 2 已 標(biāo)號(hào) 距離 ∞ 醫(yī)院 3 已 標(biāo)號(hào) 距離 4 醫(yī)院 4 已 標(biāo)號(hào) 距離 9 12 4 5 6 醫(yī)院 1 已 標(biāo)號(hào) 距離 0 醫(yī)院 2 未標(biāo)號(hào) 距離 12 醫(yī)院 3 已 標(biāo)號(hào) 距離 4 醫(yī)院 4 以 標(biāo)號(hào) 距離 9 12 4 5 6 11 點(diǎn) 數(shù)為 ni．即第 i次迭代需對(duì) ni個(gè)節(jié)點(diǎn)進(jìn)行處理，因此其所需的處理數(shù)為11( 1)() 2ninnni?????? ，對(duì) n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的時(shí)間復(fù)雜度是 O(n2)。更新方法如下： 如果 i的最短路徑邊 ij 的長(zhǎng)度 j目前的最短路徑，則 j的最短路徑更新為 i的最短路徑邊 ij的長(zhǎng)度，否則不變（也就是意味著通過 i走向 j比原來的方向走向 j能獲得更短的路徑）。 8 給定問題的算法分析 : 1)初始化：起點(diǎn)的最短路徑為 0，其他頂點(diǎn)的最短路徑為 ∞，所有頂點(diǎn)未標(biāo)號(hào)。 例 :北京的小湯山醫(yī)院已經(jīng)投入使用了 ,在抗擊非典的戰(zhàn)役中發(fā)揮了重要的作用。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn) i的點(diǎn) j*，作為前一點(diǎn) ， 設(shè)置： i=j*。 2)檢驗(yàn)從所有已標(biāo)記的點(diǎn) k 到其直接連接的未標(biāo)記的點(diǎn) j的距離，并設(shè)置：wj=min{ wj, wk+dkj }式中， dkj 是從點(diǎn) k到 j的直接連接距離。網(wǎng)絡(luò)中所有結(jié)點(diǎn)首先初始化為未標(biāo)記結(jié)點(diǎn)，在搜索過程中和最短路徑中的結(jié)點(diǎn)相連通的結(jié)點(diǎn)為臨時(shí)標(biāo)記結(jié)點(diǎn)，每次循環(huán)都是從臨時(shí)標(biāo)記結(jié)點(diǎn)中搜索距源點(diǎn)路徑長(zhǎng)度最短的結(jié)點(diǎn)作為永久標(biāo)記結(jié)點(diǎn)，直至找到目標(biāo)結(jié)點(diǎn)或者所有的結(jié)點(diǎn)都成為永久標(biāo)記結(jié)點(diǎn)來結(jié)束算法。 ③ Dijkstra 算法的核心步驟，即從具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)中搜索與起點(diǎn)距離最小的節(jié)點(diǎn)，如果具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)無序地存放在數(shù)組中，則每次迭代都要把所有未獲得永久標(biāo)號(hào)的都掃描一遍，所以將具有臨時(shí)標(biāo)號(hào)的節(jié)點(diǎn)按與起點(diǎn)距離大小進(jìn)行排序則可以節(jié)省每次掃描的時(shí)間，提高查詢速率。算法優(yōu)化思想：首先從與起點(diǎn) s 直接相連的相鄰節(jié)點(diǎn)幾個(gè) NBk 中選擇距離最小的節(jié)點(diǎn) k 作為轉(zhuǎn)接點(diǎn)，同時(shí)將 k 劃歸為表示集合 S（初始時(shí)， S 為 {s}）。 最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，其算法有很多種，其中傳統(tǒng)的 Dijkstra 算法一般用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小代價(jià)路徑，并且能夠適應(yīng)網(wǎng)絡(luò)拓