【正文】 } RoutePlanResult result = new RoutePlanResult(pa。 i 。 } string[] passedNodeIDs = new string[]。 if ( == ) { RoutePlanResult result1 = new RoutePlanResult(null, )。 } endregion //表示規(guī)劃結束 return (planCourse, destID)。 } } } //標志為已處理 planCourse[].BeProcessed = true。 i++) { ([i].ToString()) 。 for (int i = 0。 if (tempWeight ) { = tempWeight。//從ＨＡＳＨ中取回ＮＯＤＥＩＤ節(jié)點的 PassedPath foreach (Edge edge in ) { if ( != originID) //過濾掉源節(jié)點 { PassedPath targetPath = planCourse[]。 Node curNode = (planCourse, nodeList, originID)。 31 using 。 using 。 } set { edgeList = value。 } public string ID { get { return 。//Edge的集合－－出邊表 public Node(string id ) { = id 。 namespace WindowsApplication1 { /// summary /// 節(jié)點類 /// /summary class Node //節(jié)點則抽象成 Node類，一個節(jié)點上掛著以此節(jié) 點作為起點的 ―出邊 ‖ { private string iD 。 using 。 30 } } } } 節(jié)點類， class Node//抽象節(jié)點類，用于描述具體地點 using System。 } } public double Weight { get { return 。 } } public string EndNodeID { get { return 。 //權值，代價 public string StartNodeID { get { return 。 //起點ＩＤ private string s_EndNodeID = N/A。 using 。 27 參考文獻 [1] 羅理，王鋒 .基于 Dijkstra 的最短路徑改進算法 [N].湖北汽車工業(yè)學院學報 . 2020 年 6月 ,第 21卷第 2 期 . [2] 徐寅峰，劉明，蘇兵 .不完全信息下交通網絡最短路徑的求解方法 [J].中國科技論文在線 . [3] 焦學軍，秦奮，王海鷹 . A 星算法在城鎮(zhèn)地價評估中的應用 [J]. 科苑論談． [4] 張寧 .遺傳算法的特點及其應用 [Z]. [5] 李擎，謝四江，童新海，王志良 . 一種用于車輛最短路徑規(guī)劃的自適應遺傳算法機器與 Dijkstra 和 A*算法的比較 [N].北京科技大學學報 .2020 年 11 月，第 28卷第 11 期 . [6] 董鑫，鄭逢斌，李莘莘 . Dijkstra 算法的改進及其在警用 GIS中的實現(xiàn) [N]. 鄭州輕工業(yè)學院學報 (自然科學版 ). 2020 年 lO 月，第 22 卷第 5 期 . [7] 章永龍 .Dijkstra 最短路徑算法優(yōu)化 [N]. 南昌工程學院學報 , 2020 年 8 月 ,第 25 卷第 3 期 . [8] 陳尹軍，王翠玲 .基于 Dijkstra 算法的公路網最短路徑查詢實現(xiàn) [J]. 中國科技論文在線 . [9] 夏華麗，寧書年 .Dijkstra 算法在物流配送運輸規(guī)劃中的最短路徑研究 [J].中國科技論文在線 . [10] 古凌嵐 .GIS 最短路徑分析中 Dijkstra 算法的優(yōu)化 [J].計算機與數(shù)字工程 .2020，第 34 卷第 12期 . [11] 馮桂蓮 .基于 Dijkstra 算法的最短路徑的實現(xiàn) [N].青海大學學報 (自然科學版 ).2020 年 2月，第 25卷第 1期 . [12] 陳益富，盧 瀟，丁豪杰 . 對 Dijkstra 算法的優(yōu)化策略研究 [N]. 計算機技術與發(fā)展 . 2020, 第 l6 卷第 9期 . [13] 王 濤 ,李偉生 .最短路徑子圖 [N].北方 交通大學學報 .2020 年 ,第 28 卷第 2 期 . 28 [14] 李玲，劉正綱，張強 . 基于 Mapx 的最短路徑選擇算法的實現(xiàn) [J]. 中國科技論文在線 . [15] 曹陽 . 數(shù)據(jù)結構中最短路徑算法的實現(xiàn) [N]. 宜賓學院學報 .2020，第 6 期 . 29 附 錄 有向邊類， class Edge//抽象邊類，用于描述道路 using System。實際上，在一個網絡中，盡管節(jié)點和邊很多，但與網絡中某一節(jié)點相關的邊和節(jié)點卻是有限的。優(yōu) 化算法只對最短路徑上節(jié)點的鄰居做處理，而不涉及到其他節(jié)點，每個搜索過程不必全部遍歷或者較少地遍歷臨時標記點，既縮小了搜索范圍，又保證了遍歷搜索 100%的搜索成功率，從而提高了搜索效率，節(jié)省了時間， 適應網絡拓撲的變化，性能穩(wěn)定 。 通過 表可看出在起終點距離較遠時，優(yōu)化后的 Dijkstra 算法在保持經典算法 100%搜索成功率的基礎上，大大加快了搜索速度，提高了搜索效率，在道路節(jié)點路段數(shù)量多的空間拓撲結構中尤為適用。46616339。測試結果如表 。 圖 地圖功能展示 24 程序運行后，首先載入網絡拓撲，讀取數(shù)據(jù)庫信息： 載入網絡拓撲 載入網絡拓撲 ↓ ↓ 載入原始節(jié)點 ↓ ↓ 載入原始邊 ↓ ↓ 完成（空間拓撲共有 60828 個節(jié)點） 圖 網絡拓撲載入過程 例：我們選取同區(qū)域不相鄰兩節(jié)點進行算法實現(xiàn)，設置起點 46616300077，終點 46616300087，實驗結果如圖 、 ： 圖 經典 Dijkstra 算法實現(xiàn) 圖 Dijkstra 優(yōu)化算法實現(xiàn) 如圖 、 ，相同的起點終點，所得最短路徑長度均為 30，經典 Dijkstra 算法經過對區(qū)域編號為 46616含有 5563 個節(jié)點的區(qū)域進行節(jié)點遍歷后共用時 12秒，而 Dijkstra 優(yōu)化算法對 S 內節(jié)點的鄰居節(jié)點進行遍歷后只用時 8 秒，提高了搜索效率 。這樣，設結果顯示最短路徑為 10，可知起點終點之間經過 10個路段長度，經過 9個中間轉折點。 節(jié)點表（ NSHANGHAI）包含了上海市各節(jié)點信息，主要包括節(jié)點編號、所在區(qū)域、與其相鄰的路段等其他相關信息，結構設計如表 ： 表 節(jié)點表（ NSHANGHAI） 字段名稱 字段類型 字段解釋 MapID char 區(qū)域編號 ID char 節(jié)點編號 Node_LID char 相鄰路段編號 邊表（ RSHANGHAI）包含了上海市各路段信息，只要包括路段編號、所在區(qū)域、路段起點、路段終點等其他相關信息，結構設計如表 ： 表 邊表（ RSHANGHAI） 字段名稱 字段類型 字段解釋 MapID char 區(qū)域編號 ID char 路段編號 SnodeID char 起點編號 EnodeID char 終點編號 本實驗采用節(jié)點命名規(guī)則：節(jié)點 ID前 6位表示區(qū)域 MapID，如： 46616300077節(jié)點的前 6位 466163表示節(jié)點所在區(qū)域 MapID為 466163，后 5位根據(jù)節(jié)點個性命名。 圖 上海市地圖 22 屬性數(shù)據(jù)庫設計 本系統(tǒng)屬 性數(shù)據(jù)用關系數(shù)據(jù)庫 SQLSERVER2020 統(tǒng)一管理，我們將 81339 條弧、 60828 個節(jié)點按上海市實際情況劃分 92 個區(qū)域。鑒于其節(jié)點多路段復雜的特性，我們以上海市地圖為例。當網絡的規(guī)模較大及其關聯(lián)矩陣為一個稀疏矩陣時，本文提出 的優(yōu)化算法，與傳統(tǒng) Dijkstra算法相比，能大大減少了計算次數(shù)及比較次數(shù)，提高了運算效率。當網絡拓撲結構圖具有的節(jié)點數(shù)， v較大且其關聯(lián)矩陣為一個稀疏矩陣時，相對傳統(tǒng) Dijkstra算法，優(yōu)化算法大大減少了計算次數(shù)與比較次數(shù)，在一定程度上提高了運算速度。因此，算法的時間復雜度為 O(ne)。優(yōu)化算法空間復 雜度為 O(np)，其中 P是常量，為結點對象所占用的空間。它采用線性數(shù)組結構存儲其關聯(lián)矩陣，在提取最短路徑節(jié)點時需要訪問所有的未標記節(jié)點，算法的運行時間為 O(n2)。 最終結果為 w2 = 2， w3=4， w4=2， w5=3， w6=4， w7=5， w6=4， w7=5。 優(yōu)化 Dijkstra算法求解過程： 表 優(yōu)化的 Dijkstra算法求解 v1 到其他各節(jié)點最短路徑的過程 迭代次數(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) (v1,v2,v3,v4,v5) (v6) (v6,v7) 5 ③ 5 v6 w6=4 (v3,v5,v7) (v1,v2,v3,v4,v5,v6) (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)， NB4 = j∈ N