王兆南

(浙江大學(xué)理學(xué)院，浙江杭州3100127)

基于Dijkstra算法改進(jìn)的海量數(shù)據(jù)最優(yōu)路徑計(jì)算方法研究與實(shí)現(xiàn)

王兆南

(浙江大學(xué)理學(xué)院，浙江杭州3100127)

針對(duì)傳統(tǒng)Dijkstra算法在應(yīng)用中存在的不足，提出一種面向海量數(shù)據(jù)的基于傳統(tǒng)Dijkstra算法的最優(yōu)路徑搜索方法，以避免大量無(wú)用節(jié)點(diǎn)參與計(jì)算，嚴(yán)重制約計(jì)算效率。通過(guò)對(duì)路網(wǎng)關(guān)系制表來(lái)表達(dá)節(jié)點(diǎn)與路段的關(guān)系，解決使用相鄰矩陣計(jì)算量大的問(wèn)題。此外，利用監(jiān)測(cè)得到的實(shí)時(shí)速度進(jìn)行加權(quán)，實(shí)現(xiàn)最短時(shí)間路徑的計(jì)算。

Dijkstra算法;海量數(shù)據(jù);最優(yōu)路徑

一、引 言

面對(duì)城市的日益發(fā)展和人們生活水平的提高，城市汽車不斷增加，過(guò)多的車輛給道路交通帶來(lái)了過(guò)重的負(fù)荷。車道的頻繁整修，節(jié)假日的交通管制，都會(huì)給道路帶來(lái)一定的改變，但是交通部門并不能及時(shí)地公布一些車道施工的信息，或者居民不能及時(shí)得到已經(jīng)發(fā)布下來(lái)的信息，都給居民生活帶來(lái)了一些麻煩。通過(guò)道路監(jiān)測(cè)與發(fā)布系統(tǒng)的建立來(lái)及時(shí)獲取和發(fā)布道路信息將方便人們的出行。本文中的最優(yōu)路徑分為距離最短路徑和時(shí)間最短路徑兩種，其中后者算法是在前者算法基礎(chǔ)上拓展得到的。目前，最短路徑的算法有很多，本系統(tǒng)從最基本的最短路徑的計(jì)算方法——Dijkstra算法出發(fā)，尋找出一種適合海量數(shù)據(jù)運(yùn)算的方法。

二、經(jīng)典Dijkstra算法的主要思想［1］

Dijkstra算法的基本思路是：假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào)(dj，pj)。其中，dj是從起源點(diǎn)s到點(diǎn)j的最短路徑的長(zhǎng)度;pj則是從s到j(luò)的最短路徑中j點(diǎn)的前一點(diǎn)。求解從起源點(diǎn)s到點(diǎn)j的最短路徑算法的基本過(guò)程如下：

1)初始化。起源點(diǎn)設(shè)置為：① ds=0，ps為空;②所有其他點(diǎn)：di=∞，pi為空;③標(biāo)記起源點(diǎn)s，記k=s，其他所有點(diǎn)設(shè)為未標(biāo)記的。

2)檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置

式中，lkj是從點(diǎn)k到j(luò)的直接連接距離。

3)選取下一個(gè)點(diǎn)。從所有未標(biāo)記的結(jié)點(diǎn)集M中，選取dj中最小的一個(gè)i：di=min(dj，M)。點(diǎn)i就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的。

4)找到點(diǎn)i的前一點(diǎn)。從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i的點(diǎn)j*，作為前一點(diǎn)，設(shè)置：i=j*。

5)標(biāo)記點(diǎn)i。如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到步驟2)再繼續(xù)。

三、本系統(tǒng)最短路徑的實(shí)現(xiàn)

可以看出，在按標(biāo)記法實(shí)現(xiàn)Dijkstra算法的過(guò)程中，核心步驟就是從未標(biāo)記的點(diǎn)中選擇一個(gè)權(quán)值最小的弧段，即上面所述算法的步驟2)～步驟5)。這是一個(gè)循環(huán)比較的過(guò)程，如果不采用任何技巧，未標(biāo)記點(diǎn)將以無(wú)序的形式存放在一個(gè)鏈表或數(shù)組中，那么要選擇一個(gè)權(quán)值最小的距離就必須把所有的點(diǎn)都掃描一遍，在大數(shù)據(jù)量的情況下，這將嚴(yán)重制約計(jì)算速度。要解決這個(gè)問(wèn)題，最有效的做法就是將這些要掃描的點(diǎn)按其所在邊進(jìn)行順序排列，這樣每循環(huán)一次只能取到符合條件的點(diǎn)，排除了大量不相連的點(diǎn)，可大大提高算法的執(zhí)行效率。此外，線路要進(jìn)行最短路徑的計(jì)算，就必須構(gòu)建網(wǎng)絡(luò)的拓?fù)潢P(guān)系。如果用一個(gè)矩陣來(lái)表示這個(gè)網(wǎng)絡(luò)，不但所需空間巨大，而且效率會(huì)很低。

本文采用的算法在原有的Dijkstra進(jìn)行了優(yōu)化［2］。利用Access數(shù)據(jù)庫(kù)A表達(dá)路網(wǎng)的拓?fù)潢P(guān)系，記錄了節(jié)點(diǎn)與路段間的關(guān)系和路段的長(zhǎng)度，由于是單向路網(wǎng)，為了便于計(jì)算，分別以起始節(jié)點(diǎn)SNode和終點(diǎn)節(jié)點(diǎn)Enode進(jìn)行排序，并得到兩組數(shù)據(jù)，一起組成“起終點(diǎn)連接數(shù)據(jù).dbm”文件。利用Access數(shù)據(jù)庫(kù)B記錄1～555節(jié)點(diǎn)的相鄰連接點(diǎn)的個(gè)數(shù)和累計(jì)的節(jié)點(diǎn)個(gè)數(shù)，累計(jì)節(jié)點(diǎn)數(shù)主要是為了方便算法的實(shí)現(xiàn)。本系統(tǒng)的實(shí)現(xiàn)過(guò)程如下。

首先需要進(jìn)行數(shù)據(jù)庫(kù)連接，將數(shù)據(jù)庫(kù)中的數(shù)據(jù)賦到相應(yīng)的變量中。AA1、BB1、CC1、DD1是以起始節(jié)點(diǎn)SNode排序生成的一維數(shù)組，其中，AA1對(duì)應(yīng)起始節(jié)點(diǎn)SNode;BB1對(duì)應(yīng)終點(diǎn)節(jié)點(diǎn)Enode;CC1對(duì)應(yīng)路段長(zhǎng)度;DD1對(duì)應(yīng)路段編號(hào)。AA2、BB2、CC2、DD2是以ENode排序生成的一維數(shù)組，其中，AA2對(duì)應(yīng)ENode;BB2對(duì)應(yīng)SNode;CC2對(duì)應(yīng)路段長(zhǎng)度; DD2對(duì)應(yīng)路段編號(hào)。IndexA1()和IndexA2()為二維數(shù)組，其中，IndexA1()的第1項(xiàng)對(duì)應(yīng)累計(jì)數(shù)1，第2項(xiàng)對(duì)應(yīng)某一起點(diǎn)與其相鄰的終點(diǎn)的個(gè)數(shù);IndexA2()的第1項(xiàng)對(duì)應(yīng)累計(jì)數(shù)2，第2項(xiàng)對(duì)應(yīng)某一終點(diǎn)與其相連的起點(diǎn)的個(gè)數(shù)。變量與數(shù)據(jù)庫(kù)字段的相關(guān)關(guān)系見(jiàn)表1和表2。

表1 數(shù)據(jù)庫(kù)A中獲取的變量

表2 數(shù)據(jù)庫(kù)B中獲取的變量

1.空間最短路徑

空間最短路徑的算法的流程圖如圖1所示。

搜索與ll相連接的點(diǎn)，是先以ll為起點(diǎn)，尋找與ll相連的終點(diǎn)，而以ll為起點(diǎn)得到的終點(diǎn)搜到之后，再以ll為終點(diǎn)，尋找與ll相連的起點(diǎn)的點(diǎn)，算法過(guò)程與上面一樣。經(jīng)過(guò)兩個(gè)循環(huán)便將與ll相連的點(diǎn)全部找出，再?gòu)闹姓页鲩L(zhǎng)度最短的點(diǎn)，賦給Min-Point。如此循環(huán)完成空間上最短路徑的搜索。

2.時(shí)間最短路徑

時(shí)間最短路徑的算法和空間最短路徑算法的流程基本相同，其算法流程圖如圖2所示。

圖1 空間最短路徑算法流程圖

圖2 時(shí)間最短路徑算法流程

主要代碼思想如下：首先進(jìn)行初始化，初始化過(guò)程與空間最短路徑的過(guò)程一樣，開(kāi)始搜索與ll相連接的點(diǎn)，先以ll為起點(diǎn)，尋找與ll相連的終點(diǎn)，主要代碼和空間最短路徑的過(guò)程類似。在過(guò)程中要對(duì)路況監(jiān)督時(shí)得到的速度進(jìn)行匹配，以解決兩個(gè)模塊使用的表順序不一致的問(wèn)題。速度求得之后，便可進(jìn)行時(shí)間的計(jì)算。求出的是走到此點(diǎn)所花的累積時(shí)間S1，再以ll為起點(diǎn)搜到終點(diǎn)之后，再以ll為終點(diǎn)，尋找與ll相連的起點(diǎn)的點(diǎn)，算法過(guò)程與上面一樣。經(jīng)過(guò)兩個(gè)循環(huán)便將與ll相連的點(diǎn)全部找出，再?gòu)闹兄赋鰰r(shí)間最短的點(diǎn)，賦給MinPoint。

如此循環(huán)完成時(shí)間上的最短路徑的搜索。

四、最短路徑功能實(shí)現(xiàn)

最短路徑的搜索及結(jié)果在地圖上顯示的全過(guò)程如圖3所示。

圖3 路徑選擇實(shí)現(xiàn)過(guò)程流程圖

主要實(shí)現(xiàn)的功能有：在組合框中利用模糊匹配進(jìn)行選擇路口的選擇;在列表框中顯示選擇的要經(jīng)過(guò)的路口的信息;對(duì)列表框中的信息進(jìn)行刪除、上移、下移基本操作;實(shí)現(xiàn)空間時(shí)間最短路徑的計(jì)算;在地圖上實(shí)現(xiàn)最短路徑的高亮顯示。

1.最短路徑計(jì)算

對(duì)于空間最短路徑的計(jì)算，依照ListView中所選擇的點(diǎn)的順序多次調(diào)用ShortPath()過(guò)程實(shí)現(xiàn)，時(shí)間最短路徑的計(jì)算調(diào)用TShortPath()過(guò)程實(shí)現(xiàn)。

2.結(jié)果的地圖顯示

最短路徑計(jì)算結(jié)束后，經(jīng)過(guò)的路段的編號(hào)以字符串的形式儲(chǔ)存在SumPath的變量中，利用Split將SumPath中的路段號(hào)提取出來(lái)放入一個(gè)數(shù)組。給搜索的路段進(jìn)行著色，將最短路徑進(jìn)行高亮顯示，渲染后的效果如圖4所示。若是空間最短，在最短路徑的窗口的查詢結(jié)果中展現(xiàn)整段路程的最短長(zhǎng)度;若是時(shí)間最短，記錄下所花的最短的時(shí)間。

圖4 地圖高亮顯示的效果

如要從四平路國(guó)泰路出發(fā)經(jīng)過(guò)控江路軍工路，最后抵達(dá)軍工路殷行路，需要知道空間上的最短路徑。打開(kāi)主界面的路徑選擇菜單，在選擇最短路徑類型欄中選擇空間最短，按照順序?qū)?個(gè)路口的名稱輸入，單擊計(jì)算，便出現(xiàn)如圖4所示的結(jié)果。系統(tǒng)會(huì)在最短路徑頁(yè)面的最下方查詢結(jié)果的文本框中顯示“從起點(diǎn)四平路國(guó)泰路到終點(diǎn)軍工路殷行路空間的最短路程為8 797.934 m”。同時(shí)，在主界面的地圖上還會(huì)用橙色標(biāo)出最短路徑經(jīng)過(guò)的路線。

五、結(jié)束語(yǔ)

本文通過(guò)對(duì)路網(wǎng)關(guān)系制表來(lái)表達(dá)節(jié)點(diǎn)與路段的關(guān)系，解決了使用相鄰矩陣計(jì)算量大的問(wèn)題。此外，利用監(jiān)測(cè)得到的實(shí)時(shí)速度進(jìn)行了加權(quán)，實(shí)現(xiàn)了最短時(shí)間路徑的計(jì)算，并對(duì)最短路徑進(jìn)行高亮顯示，使路線一目了然。但是，本方法實(shí)現(xiàn)的過(guò)程還有可以改進(jìn)的地方，如最短路徑的模型相對(duì)簡(jiǎn)單，可以加入車道信息和轉(zhuǎn)向信息等。

［1］ 樂(lè)陽(yáng)，龔健雅.Dijkstra最短路徑算法的一種高效率實(shí)現(xiàn)［J］.武漢測(cè)繪科技大學(xué)學(xué)報(bào)，1999，24(3)：209-211.

［2］ 孫慶珍，李宏偉.GIS中最短路徑算法的研究以及在VB中的代碼［J］.電腦編程與維護(hù)，2005(8)：30-32.

Mass Data Optimal Path Searching Using an Improved Dijkstra Algorithm

WANG Zhaonan

0494-0911(2012)09-0032-03

P208

B

2012-07-16

王兆南(1990—)，男，山東肥城人，主要研究方向?yàn)榈乩硇畔⑾到y(tǒng)應(yīng)用與開(kāi)發(fā)。