李寬榮　陸通　高勇

摘 要：最短路徑分析是網(wǎng)絡拓撲中的一個重要的應用，它在地理信息系統(tǒng)、計算機網(wǎng)絡路由等方面發(fā)揮著至關重要的作用。解決最短路徑問題的經(jīng)典方法是Dijkstra算法，時間復雜度為O（n2），在大數(shù)據(jù)量下效率低下而且使用鄰接矩陣存儲圖形數(shù)據(jù)在一定程度上造成了空間浪費。該文在分析了Dijkstra算法的基礎上提出來一種改進方法，該法使用STL容器來代替鄰接矩陣來存儲圖形數(shù)據(jù)提高了查詢效率，并且利用雙隊列來存儲節(jié)點降低了內(nèi)循環(huán)次數(shù)，減少了很多不必要的計算，從而降低了算法時間復雜度。STL容器的應用使得最短路徑算法得到了擴展，在求解最短路徑的同時還支持添加障礙點，增加開關節(jié)點等應用。

關鍵詞：最短路徑分析 Dijkstra STL

中圖分類號：TP301.6 文獻標識碼：A 文章編號：1674-098X（2014）04（c）-0037-02

Dijkstra算法的最大不足之處是在于求解的是一點到網(wǎng)絡中所有點的最短距離，而實際應用中更多的是求解指定兩點之間的最短距離。求解到所有點的距離完全沒有必要，從計算代價來講也是一種極大的浪費。Dijkstra 算法中使用矩陣來存儲圖像數(shù)據(jù)，對于有N個節(jié)點的圖形，需要存儲N*N個數(shù)據(jù)，雖然可以使用對稱性來減少數(shù)量，但在大數(shù)據(jù)量下仍不能很好解決問題。目前，很多基于Dijstra的算法都是在數(shù)據(jù)結構和分析效率兩個方面來優(yōu)化。

該文在分析了Dijkstra算法的基礎上，利用STL的map和multimap容器來存儲圖形數(shù)據(jù)，方便了數(shù)據(jù)的存取，也節(jié)省了內(nèi)存占用。在求解的過程中使用兩個優(yōu)先級隊列來存儲待處理的節(jié)點，減少了內(nèi)循環(huán)次數(shù)，降低了算法的時間復雜度。同時，引入STL map作狀態(tài)容器，使其支持對障礙點的分析。而STL multimap的引入又可以使原有的節(jié)點增加開關屬性，從而支持對電力拓撲網(wǎng)絡的分析。

1 Dijkstra算法優(yōu)化

1.1 存儲圖形數(shù)據(jù)

由于網(wǎng)絡中的節(jié)點之間的關系是多對多的關系，每一個節(jié)點可能關聯(lián)多個節(jié)點，所以使用STL multimap來存儲節(jié)點之間的關聯(lián)關系。同時，為每一個節(jié)點建立一個狀態(tài)標志，使用STL map來存儲。Multimap和map使用的是紅黑樹結構來存儲節(jié)點，所以具有較高的查詢效率，而且內(nèi)存空間是動態(tài)擴展的不需要事先計算需要的內(nèi)存空間，能很好的解決從數(shù)據(jù)庫中讀取未知數(shù)量的數(shù)據(jù)的情況。

另外，multimap支持結構體來作鍵值，所以可以存儲更多信息。比如，考慮到電力網(wǎng)絡的節(jié)點，可以存儲開關節(jié)點的狀態(tài)信息。Dijkstra算法只是求解最短路徑長度，但并不能得到具體的路徑。而使用map來存儲節(jié)點的狀態(tài)信息StateInfo，可以用一個標識來記錄最短路徑上每個節(jié)點的前一節(jié)點。這樣通過從目的點開始依次查詢其前一節(jié)點直到起始點就能獲取最短路徑。StateInfo的引用使得求解最短距離算法得到進一步的擴展，比如，可以設置障礙點，所求的最短距離必須繞過障礙點。只需要設置給障礙點設置一個新的狀態(tài)，就可以實現(xiàn)。

1.2 雙隊列的應用

另外一種數(shù)據(jù)結構是隊列，用來存儲即將進行探測的節(jié)點。本文中用了兩個隊列，并以優(yōu)先級的高低區(qū)分。高優(yōu)先級隊列存放已經(jīng)探測過但是最短路徑需要更新的節(jié)點，低優(yōu)先級隊列存放第一次探測到的節(jié)點。高優(yōu)先級的隊列中的節(jié)點會被優(yōu)先取出進行探測，因為高優(yōu)先級節(jié)點有更高的概率到達目標節(jié)點。

1.3 高效算法的提出

為了進一步的提高計算速度，采用雙隊列來存儲當前計算的節(jié)點信息，一個是高優(yōu)先級對列HighQueue，一個是低優(yōu)先級隊列LowQueue。基本步驟如下：

（1）首先，利用STL multimap和map定義數(shù)據(jù)結構JointRealtionInfo，StateInfo來存儲節(jié)點之間的關聯(lián)關系和狀態(tài)信息。然后，讀取數(shù)據(jù)庫信息到數(shù)據(jù)結構中，設定每個節(jié)點的狀態(tài)信息初始值為Unchecked。

（2）定義兩個隊列：HighQueue、LowQueue，并將起始節(jié)點srcJointID加入LowQueue中，同時修改StateInfo中起點的狀態(tài)StateInfo[srcJointID].state =checking，修改長度標簽為0，表示當前節(jié)點距離起始節(jié)點的距離為0。

（3）判斷HighQueue或LowQueue是否為空，若都為空，則直接返回終點節(jié)點DesJoint的長度標簽值。若有一個不為空，則繼續(xù)執(zhí)行下一步。

（4）優(yōu)先判斷HighQueue是否為空，在為空的前提下再判斷LowQueue。無論如何取不為空的隊列的第一個元素值，賦值給臨時變量TempJoint。

（5）統(tǒng)計JointRelationInfo中以TempJoint為鍵的個數(shù)amount（這里使用multimap：：count（）來統(tǒng)計）。使用multimap：：find（）來返回一個迭代器Iter指向第一個以TempJoint為鍵的鍵值對，通過Iter可以找到對應的值，即與TempJoint相鄰的下一個節(jié)點的ID，以及TempJoint本身的長度和開關狀態(tài)，若存在另外一個相鄰節(jié)點，則使Iter++即能找到，這就是multimap的便利之處。

（6）判斷如果amout>0，首先通過Iter找出第一個相鄰的節(jié)點AbutJoint，并獲取其自身的長度abutLen，將其與TempJointD的距離標簽值相加得到NewMarkLen。并與AbutJoint的距離標簽值abutMarkLen作比較。若大于，說明經(jīng)過TempJoint到達AbutJoint的路徑并不比當前AbutJoint的路徑短，此時執(zhí)行步驟（7）。若小于，說明經(jīng)過TempJoint到達AbutJoint的路徑要比AbutJoint原本的路徑更短。此時執(zhí)行步驟（8）。如果amount=0，說明TempJoint的相鄰節(jié)點都已經(jīng)遍歷完，接下來執(zhí)行步驟（11）。endprint

（7）使amount--，Iter++，并繼續(xù)執(zhí)行（6）。

（8）首先要判斷TempJoint開關狀態(tài)，若是打開，則說明此路不通。若是閉合則繼續(xù)。修改AbutJoint的距離標簽值為NewMarkLen，同時將AbutJoint的當前路徑上的前一個節(jié)點priorJoint設為TempJoint。判斷AbutJoint當前狀態(tài)AbutState，若AbutState=CHECKED，則執(zhí)行步驟（9）。若AbutState=UNCHECKED，則執(zhí)行步驟（10）。

（9）AbutJoint狀態(tài)為CHECKED說明已經(jīng)存在從SrcJoint到AbutJoint的路徑，但是經(jīng)過TempJoint的路徑要比之前的路徑更短，所以需要更新原有的路徑。判斷當前的AbutJoint是否是目標節(jié)點DesJoint，若不是，則將AbutJoint加入到HighQueue中等待進一步的處理。然后，更新AbutJoint的狀態(tài)為CHECKEING。執(zhí)行步驟（7）。

（10）AbutJointz狀態(tài)為UNCHE CKED，說明從原點SrcJoint開始探測的路徑尚未有經(jīng)過AbutJoint。此時判斷AbutJoint是否是目標節(jié)點DesJoint，若不是將其加入到LowQueue中，并修改AbutJoint的狀態(tài)為CHECKING。執(zhí)行步驟（7）。

（11）設置TempJoint的狀態(tài)為CHECKED，檢測DesJoint的狀態(tài)，判斷目標點DesJoint是否已經(jīng)被探測到，也就是說已經(jīng)存在一條從原點SrcJoint到目標點DesJoint的路徑。若DesJoint的狀態(tài)為CHECKING，獲取DesJoint的距離標簽DesMarkLen，即SrcJoint到DesJoint的距離，執(zhí)行步驟（12）。若為CHECKED或UNCHECKED，執(zhí)行步驟（3）。

（12）經(jīng)過上述11個步驟就可以完成從原點到目標點的最短路徑搜索，為了進一步的優(yōu)化，當目標點已經(jīng)找到以后，將其距離標簽DesMarkLen與當前HighQueue、LowQueue內(nèi)節(jié)點的距離標簽進行逐一比較，若隊列中的節(jié)點的距離標簽都要比DesMarkLen大，說明當前找到的起始點到目標點的最短路徑即為最短的路徑，不肯能再存在更短的路徑。若隊列中存在距離標簽小于DesMarkLen的節(jié)點，則說明有可能存在到達目標節(jié)點更短的路徑，不作任何處理繼續(xù)。

2 結語

該文通過使用STL容器來存儲圖形中節(jié)點之間的關系，在降低內(nèi)存占用的同時也加快了查詢的速度，而且使原有的算法不再是單純的求解兩點之間的最短路徑，還可以增加開關節(jié)點以及對障礙點的分析。采用高低優(yōu)先級雙隊列，分解了算法的規(guī)模，降低了時間復雜度，進一步提高了求解最短距離的效率。

參考文獻

[1] Stefano. Pallottino. Shortest-path methods： Complexity， interrelations and new propositions[J].Networks，1984（14）.

[2] 侯捷.STL源碼剖析[M].華中科技大學出版社，2002.

[3] 王志和，凌云.Dijkstra最短路徑算法的優(yōu)化及其實現(xiàn)[J].微計算機信息， 2007，11（3）：275-278.

[4] 寧建紅.最短路徑算法效率研究[J].上海電機學院學報，2006（3）：38-41.

[5] 張紅科.基于鏈表的Dijkstra算法優(yōu)化研究[J].電腦知識與技術，2008（26）.endprint