基于Dijkstra算法過必經(jīng)點的最短路徑設計

王小會， 薛延剛， 李曉青

(蘭州工業(yè)學院 電氣工程學院，甘肅 蘭州 730000)

隨著車輛的廣泛普及和交通網(wǎng)絡的不斷發(fā)展，智能交通誘導系統(tǒng)的作用將顯得更為突出。智能交通誘導系統(tǒng)是將先進的計算機處理技術、信息技術、數(shù)據(jù)通信技術及電子自動控制技術等有效地綜合運用于整個系統(tǒng)當中，建立起的一種在大范圍內、全方位發(fā)揮作用的實時、準確、高效的最優(yōu)出行路線系統(tǒng)[1-6]。

交通誘導系統(tǒng)可根據(jù)駕駛員的意愿為其提供最佳行駛路線來達到誘導出行行為，減少車輛在路上的行駛時間[7-8]。對用戶來說，除了最優(yōu)路線外，次優(yōu)、再次優(yōu)等路線[9-10]也同樣重要，這樣可以使用戶擁有更大的選擇空間。同時，為了進一步提供更人性化的服務，誘導系統(tǒng)還應設置多個必經(jīng)點以滿足用戶在出行途中的需要，比如要途徑超市、加油站等，故必經(jīng)點的考慮也必將是未來智能交通誘導系統(tǒng)的發(fā)展趨勢[11-16]。因此，本文在基本Dijkstra算法上提出過K個必經(jīng)點的N條最短路徑算法，有效擴充了最短路徑的數(shù)量，滿足用戶選擇需求。

1 交通誘導系統(tǒng)的設計

1.1 系統(tǒng)設計

首先通過建立路網(wǎng)節(jié)點屬性數(shù)據(jù)庫保存相關節(jié)點信息，并將路網(wǎng)信息數(shù)據(jù)導入到數(shù)據(jù)庫，完善路網(wǎng)結構信息；其次，通過Dijkstra算法查找出符合要求的最短路徑；最后在界面上顯示相關的路徑信息。具體流程如圖1所示。

圖1 系統(tǒng)設計流程

圖2 一個路網(wǎng)

圖3 子網(wǎng)集合

1.2 數(shù)據(jù)處理

為提高數(shù)據(jù)運算效率，采用分塊式處理的方式，主要包括對路網(wǎng)的結構、路網(wǎng)節(jié)點屬性信息的處理和信息輸入接口的設置。對路網(wǎng)的拓撲結構采用序列化的方法存入硬盤中，路網(wǎng)節(jié)點屬性信息存放在Access數(shù)據(jù)庫中，并通過信息輸入接口實現(xiàn)對拓撲結構進行增加、刪除、修改、保存。圖3為以一個路網(wǎng)(圖2)的子網(wǎng)集合，其中路網(wǎng)的主站點代表道路的交叉口，輔助站點是相鄰交叉口之間的彎道點。

通過微軟基礎類庫(Microsoft Foundation Classes，MFC)中已有的CTypedPtrArray數(shù)組類模板實現(xiàn)路網(wǎng)的存儲、動態(tài)創(chuàng)建新元素、統(tǒng)計元素個數(shù)等功能。同時，通過數(shù)組類的封裝，把整個網(wǎng)絡劃分為各個子網(wǎng)的集合，每個子網(wǎng)均是數(shù)組類的一個元素，即包含一個節(jié)點與其所關聯(lián)的所有連接信息，這樣的改變無疑使網(wǎng)絡結構變得更為清晰，而且又充分利用了MFC本身所擁有的標準類。

數(shù)組類CTypedPtrArraym_CtypedptrArrayRouteWeb保存了整個網(wǎng)絡的信息，其中每個子網(wǎng)結構通過一個類CRouteWeb來實現(xiàn)存儲，具體存儲內容如圖4所示。

圖4 子網(wǎng)的數(shù)據(jù)存儲方式

這里的距離默認的是路程，行駛的速度用于衡量兩主站點之間路段的路況擁擠度，根據(jù)現(xiàn)實生活中各電子地圖的經(jīng)驗，分別以0～10 km/h、10～30 km/h、30 km/h以上代表路況的擁堵、緩慢、暢通。

本系統(tǒng)是選用開放數(shù)據(jù)庫連接(Open Database Connectivity，ODBC)關系型數(shù)據(jù)庫設計的，在系統(tǒng)中設計相關的數(shù)據(jù)庫包含如下3步：

(1)建立應用程序：通過MFC AppWizard建立MFC應用程序。

(2)建立節(jié)點屬性數(shù)據(jù)庫：Access文件作為系統(tǒng)的節(jié)點屬性數(shù)據(jù)庫，在文件中建立兩張數(shù)據(jù)表,分別是主站點表、輔助站點表，用于存儲主站點及輔助站點的屬性信息。主站數(shù)據(jù)表主要包括節(jié)點ID、節(jié)點坐標、節(jié)點所在街道名稱，其中ID為整型，作為主站數(shù)據(jù)表的唯一標識符。輔助站點表和主站數(shù)據(jù)表結構一致，這樣將提高對數(shù)據(jù)庫的可操作性。

(3)建立ODBC數(shù)據(jù)源：進入Windows系統(tǒng)中的管理工具選項，在ODBC中添加一個基于“Microsoft Access Driver(*.mdb，*.accdb)”的驅動程序，并在下一步操作中命名數(shù)據(jù)源名稱為“站點信息”，同時把第(2)步中建立的站點信息文件作為對象，通過以上步驟，即可完成對數(shù)據(jù)庫的建立與連接。

2 過必經(jīng)點的最短路徑設計

本文通過Dijkstra算法求解過K個必經(jīng)點的N條最短路徑算法。

2.1 基本原理

對于過K個必經(jīng)點的N條最短路徑算法，必須先求得過第一條K個必經(jīng)點的最短路徑，然后再通過斷開第一最短路徑所形成的子圖集對應的最短路徑集合求第二最短路徑，如此循環(huán)以致求得第N條最短路徑。

設G=(V，E)是一個帶權有向或無向圖，該圖是由節(jié)點和相連的弧線組成，兩個節(jié)點之間的不同連接方式組成了兩點間所有的路徑，每條路徑都與其所在的子圖相關，子圖可以是原圖斷開某些節(jié)點之間的連接或去掉若干個節(jié)點以及與這些節(jié)點相關的連接組成。在一個子圖中求過K個必經(jīng)點的最短路徑，可通過分段求解每一種排列的路徑后，去路徑最小值來確定最終的最短路徑。

對于一個沒有孤立節(jié)點的子圖，每兩個節(jié)點間存在最短路徑。假設圖中無孤立節(jié)點，那么從起始節(jié)點到目的節(jié)點之間存在若干條路徑。對于每一條路徑，該路徑有多少段(不同節(jié)點之間的連接)就可以通過斷開每一段形成多少個子圖，這些子圖中從起始節(jié)點到目的節(jié)點的路徑集合相并再并上原圖中被斷開的這條路徑所形成的集合，就等于原圖中起始節(jié)點到目的節(jié)點之間的路徑集合[3]。根據(jù)以上原理可知，只要在子圖中，起始節(jié)點和目的節(jié)點之間存在路徑即是存在最短路徑。故保持子圖所有節(jié)點和原圖一致，只是斷開路徑的不同，在原圖找到兩點之間的最短路徑后，斷開這條第一最短路徑后形成的眾子圖都分別存在起始節(jié)點和目的節(jié)點之間的最短路徑，倘若兩節(jié)點之間還存在連接。對于原圖來說第二最短路徑便是這些形成子圖的最短路徑中最短的，如果所有子圖中都不存在這兩點間的路徑時，表明只有第一最短路徑這一條。

因此，求過K個必經(jīng)節(jié)點的N條最短路徑就是對每次找到的過K個必經(jīng)點最短路徑的子圖進行再次分割，并且和已有子圖存在的過K個必經(jīng)點的最短路徑進行一一比較，找出最短的，這樣不斷地重復執(zhí)行，并在執(zhí)行過程中去除重復的路徑，直到路徑條數(shù)達到滿足或者已無路徑為止。

2.2 算法步驟

過K個必經(jīng)點的N條最短路徑步驟如下：

(1)求出第1條過K個必經(jīng)點的最短路徑。

(2)創(chuàng)建一個數(shù)組類arrWebShortestPaths，對第一條過K個必經(jīng)點的最短路徑進行添加；在該過K個必經(jīng)點的最短路徑對應的子圖中(第1條對應的子圖為原圖)，保持所有節(jié)點不變，按照該條路徑進行分段斷開，從而形成若干個對應的子圖，計算每個子圖對應的過K個必經(jīng)點的最短路徑；創(chuàng)建arrFormSubnetInfo數(shù)組類，用于把每個子圖對應的最短路徑的長度和從原圖形成該子圖所斷開的某兩個節(jié)點之間路段進行保存。

(3)刪除arrFormSubnetInfo此次中形成新子圖的母圖記錄，比較arrFormSubnetInfo每個元素對應最短路徑的長度，求最小長度，找出該元素，并從記錄中可知其最短路徑對應的子圖是通過原圖斷開哪幾段路段后形成的。創(chuàng)建一個數(shù)組比較類arrWebShortestPaths，用于新找出這條過K個必經(jīng)點最短路徑，和已存儲的所有最短路徑比較，若存在相同的，則不進行添加，反之，則添加。

(4)判斷數(shù)組類arrWebShortestPaths中已有的最短路徑是否有存在重復路段，把沒有重復路段的用整型變量作一標記，返回執(zhí)行第2步，直到該標記值和所需的最短路徑條數(shù)N相等或者已無最短路徑為止。

3 數(shù)值實驗

圖5為模擬道路情況的數(shù)據(jù)集，對其進行最短路徑求解。

圖5 26節(jié)點數(shù)據(jù)集

3.1 無必經(jīng)點的前N(N=20)條最短路徑

以節(jié)點2為起點，22為終點的無必經(jīng)點的前N(N=20)條最短路徑，求解結果如表1所示。

從實驗結果可以看出，在這20條路徑中，結果均不存在重復路徑，更不會在同一路徑中重復出現(xiàn)同一路段，這表明算法的思想和設計的程序是完全正確的。

3.2 過K個必經(jīng)點的N條最短路徑

以節(jié)點2為起點，22為終點，隨機選擇K(K=1，2，3，4)個必經(jīng)點的前N(N=1，2，3，4)條最短路徑，求解結果如表2所示。

通過表2可以確認，本文算法實現(xiàn)的過K個必經(jīng)點的前N條最短路徑，在K、N分別為不同值時，對應的N條路徑均是表1中已得到驗證的前20條最短路徑中最短的前N條；同時，對比過必經(jīng)點17和過必經(jīng)點13、17的第一最短路徑可知：如果增加的必經(jīng)點不是過原必經(jīng)點路徑上的點的話，必然會隨著必經(jīng)點的增加，而使路徑總長度變長。由此可見，該算法完全可以保證理論上的過K(K小于5)個必經(jīng)點的前N(N小于5)條最短路徑的實現(xiàn)。

本文使用的過必經(jīng)點的最短路徑算法，實質上是通過反復迭代基本Dijkstra算法改造而來的。因此，在時耗上受基本Dijkstra算法時間復雜度的影響，即受賦權圖規(guī)模的影響，賦權圖的結點越少，邊數(shù)越少，時間耗費越少，反之，則越多；而且隨著路徑條數(shù)和必經(jīng)點個數(shù)的增加，時耗會成倍地增長。本文采用的算法在包含必經(jīng)點的情況下幾乎可以完全保證理論上的前N條最短路徑的精確性，但是，在求解時也會由于起始點、必經(jīng)點及終止點之間的連接關系不同而產(chǎn)生時耗上的差異。在有必經(jīng)點的情況下，由于必經(jīng)點在起始點和終止點的相對位置上的差異，可能會引起算法路徑搜索上較大的區(qū)別，從而在時耗上也會相差很大，而且這種差別會隨著必經(jīng)點或路徑條數(shù)的增加而變得更明顯。

表1 無必經(jīng)點的前20條最短路徑

表2 過K個必經(jīng)點的N條最短路徑

4 結論

本文基于Dijkstra算法，設計了過K個必經(jīng)點的前N條最短路徑算法，通過數(shù)值實驗分析，驗證了該條件下理論上過必經(jīng)點的前N條最短路徑的正確性，為過K個必經(jīng)點的前N條最短路徑問題的算法切實可行提供了基礎，有效擴充了可行路徑的數(shù)量，解決了實際中交通誘導系統(tǒng)存在的問題，可以滿足用戶選擇需求。但是智能交通誘導系統(tǒng)是一個非常龐大的系統(tǒng)，本文所涉及到的研究僅是其中的一小部分，建立一個完善的智能交通誘導系統(tǒng)是一個相對復雜的過程，需要投入較多的資源進行開發(fā)。在城市交通線路日益增加的今天，智能交通誘導系統(tǒng)的發(fā)展擁有非常廣闊的前景。