一種基于STL的高效最短路徑算法

李寬榮　陸通　高勇

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

關(guān)鍵詞：最短路徑分析 Dijkstra STL

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1674-098X（2014）04（c）-0037-02

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

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

1 Dijkstra算法優(yōu)化

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

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

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

1.2 雙隊(duì)列的應(yīng)用

另外一種數(shù)據(jù)結(jié)構(gòu)是隊(duì)列，用來存儲(chǔ)即將進(jìn)行探測的節(jié)點(diǎn)。本文中用了兩個(gè)隊(duì)列，并以優(yōu)先級的高低區(qū)分。高優(yōu)先級隊(duì)列存放已經(jīng)探測過但是最短路徑需要更新的節(jié)點(diǎn)，低優(yōu)先級隊(duì)列存放第一次探測到的節(jié)點(diǎn)。高優(yōu)先級的隊(duì)列中的節(jié)點(diǎn)會(huì)被優(yōu)先取出進(jìn)行探測，因?yàn)楦邇?yōu)先級節(jié)點(diǎn)有更高的概率到達(dá)目標(biāo)節(jié)點(diǎn)。

1.3 高效算法的提出

為了進(jìn)一步的提高計(jì)算速度，采用雙隊(duì)列來存儲(chǔ)當(dāng)前計(jì)算的節(jié)點(diǎn)信息，一個(gè)是高優(yōu)先級對列HighQueue，一個(gè)是低優(yōu)先級隊(duì)列LowQueue。基本步驟如下：

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

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

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

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

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

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

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

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

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

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

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

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

2 結(jié)語

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

參考文獻(xiàn)

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

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

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

[4] 寧建紅.最短路徑算法效率研究[J].上海電機(jī)學(xué)院學(xué)報(bào)，2006（3）：38-41.

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