Dijkstra 最短路徑算法的優(yōu)化及在應(yīng)急交通中的應(yīng)用

姜惠娟

(定西師范高等專科學(xué)校 計算機系，甘肅 定西 743000)

1 問題的提出

隨著城市規(guī)模的快速發(fā)展，城市交通也越來越復(fù)雜，在緊急救援物資運輸、醫(yī)療急救、110 報警、火警等應(yīng)急交通中一般要求能在盡可能短的時間內(nèi)找到到達(dá)目標(biāo)地的最佳路線，而且在行車途中通常需要實時計算車輛前方的路線、路況，這就要求能計算任意兩個節(jié)點間的最短路徑，而且問題的解決是高效的.而傳統(tǒng)的Dijkstra 算法解決的是從一定點到其他各節(jié)點的最短路徑，且計算時間長、所需存儲空間大.筆者在分析Dijkstra 算法特征的基礎(chǔ)上，從兩個方面對算法進行改進.將改進后的算法應(yīng)用于應(yīng)急交通系統(tǒng)中搜索最佳路徑，實踐證明，該方法提高了效率.

我們通常所說的最短路徑不僅指距離最短，還可以指時間最短、費用最小、線路容量最小等.相應(yīng)地，最短路徑問題就成為最快路徑問題、最低費用等問題，即:最優(yōu)路徑問題實質(zhì)是求加權(quán)圖G=＜V、E、W ＞中給定兩點間的最短路徑，而迪克斯特拉(Dijkstra)算法就是求最短路徑的著名算法之一［1］.

2 Dijkstra 最短路徑算法分析

2.1 算法描述

帶權(quán)有向圖用G=＜V，E ＞表示，其中V 是頂點集，E 是邊的集合，該算法的核心是按照路徑長度遞增的次序產(chǎn)生最短路徑.圖中的頂點集合V 分成兩組，用M 表示已求出最短路徑的頂點集合，用N 表示尚未確定最短路徑的頂點集合，用數(shù)組T［N］表示某步中從vi到vk的最短路徑.算法核心步驟可歸納為:

(1)初始時，M={vi}，N=V－{vi}，如果vi到vk有弧，T［k］等于該弧上的權(quán)值;如果無弧存在，則T［k］等于無窮大;

(2)從N 中找T［k］最小的vk加入M，并將其從N 中刪除，若N 為空，算法結(jié)束，否則進行步驟(3);

(3)將k 結(jié)點與N 中其他結(jié)點比較，若T［j］＞T［k］+arcs［k］［j］(?。紇j，vk＞上的權(quán)值)，那么用T［k］+arcs［k］［j］代替原來的T［j］，重復(fù)步驟(2);

(4)算法結(jié)束，這時T［k］中存放的即為從vi到vj的最短路徑.

某地區(qū)部分交通線路圖如圖1 所示，采用Dijkstra 算法尋找從v0到v7的最短路徑，圖2 中加粗部分表示已經(jīng)找到的最短路徑.對于已經(jīng)找到的每條路徑長加上相鄰頂點和已知路徑中相應(yīng)頂點間的距離和作比較，選出最接近起點vo的下一條頂點v8，然后將?。紇5，v8＞加入到已知的最短路徑中，采用同樣的方法循環(huán)，直到查找到所有的最短路徑.

2.2 算法時間效率分析

首先，Dijkstra 算法產(chǎn)生的是一棵以源點v0為根的樹，算法執(zhí)行則該樹向四周延伸，其中有些分支對求最短路徑是沒有幫助的;其次，算法的每次循環(huán)就是從待處理的節(jié)點集合N 中取距離最小的一個節(jié)點加入M 中，使最優(yōu)路徑擴大一個節(jié)點，從而保證一步最優(yōu)，但整體效果并未最優(yōu)［2］.

Dijkstra 算法本身時間復(fù)雜度為Ο(n2)，如果要求任意兩個結(jié)點間的最短路徑，則需要重復(fù)執(zhí)行Dijkstra 算法n 次［3］，所以總的時間復(fù)雜度為Ο(n3).當(dāng)網(wǎng)絡(luò)節(jié)點數(shù)n 增大時，計算時間會成倍或冪次增大.因此，在交通線路非常復(fù)雜的情況下，該算法運算時間長、求解效率低，很難滿足應(yīng)急交通系統(tǒng)的實際要求.

3 優(yōu)化Dijkstra 最短路徑算法

3.1 根據(jù)圖節(jié)點的出、入度優(yōu)化算法

3.1.1 根據(jù)節(jié)點的出度優(yōu)化算法

優(yōu)化思想:若結(jié)點vi的出度為1，則它只有唯一的后繼節(jié)點vj，那么vi到vj的最短路徑即為?。紇i，vj＞上的權(quán)值［3］;vi到其他各結(jié)點的最短路徑就等于vj到其他各結(jié)點的最短路徑加上弧＜vi，vj＞上的權(quán)值即可.

根據(jù)以上思想，優(yōu)化后算法的具體步驟可以總結(jié)如下:

(1)計算所有結(jié)點的出度;

(2)將出度為1 的結(jié)點用si表示;

(3)如果一個節(jié)點的出度為1，則不必求從此結(jié)點出發(fā)的最短路徑，先求其后繼結(jié)點到其他節(jié)點的最短路徑，在此基礎(chǔ)上加上si節(jié)點的唯一出度邊的權(quán)值則可得到從該si節(jié)點出發(fā)到其他節(jié)點的最短路徑;

(4)重復(fù)步驟(2)、(3)，直到?jīng)]有出度為1 的結(jié)點.

如圖1 中，結(jié)點v1、v6的出度為1，v1的唯一后繼結(jié)點為v2，v6的唯一后繼結(jié)點為v7，因此不必先求這兩點到其他結(jié)點的最短路徑，只需先求出v2、v7結(jié)點到其他結(jié)點的最短路徑，v1到其他結(jié)點的最短路徑即為v2到相應(yīng)結(jié)點的最短路徑加上?。紇1，v2＞上的權(quán)值;v6到其他結(jié)點的最短路徑即為v7到相應(yīng)結(jié)點的最短路徑加上?。紇1，v2＞上的權(quán)值.

3.1.2 根據(jù)節(jié)點的入度優(yōu)化算法

優(yōu)化思想:如果某結(jié)點的入度為0，則其他結(jié)點到該結(jié)點均不可到達(dá)，因此其他節(jié)點到該節(jié)點的最短路徑均為無窮大，而且該節(jié)點不會出現(xiàn)在其他任意兩個結(jié)點間的最短路徑上，所以在計算其他各結(jié)點間的最短路徑時，可以將入度為0 的結(jié)點先刪除.根據(jù)此優(yōu)化思路，以下是優(yōu)化后算法的具體步驟:

(1)計算各結(jié)點的入度;

(2)將入度為0 的結(jié)點用vi表示;

(3)采用Dijkstra 算法計算從vi到其他各結(jié)點的最短路徑;

(4)求完最短路徑后如果結(jié)點vi的入度為0，則將該結(jié)點從圖中刪除，以簡化有向圖，從而簡化了后面的計算過程;

(5)重復(fù)步驟(2)、(3)，直到?jīng)]有入度為0 的節(jié)點.

如圖1 所示，v0的入度為0，當(dāng)計算出以v0結(jié)點出發(fā)到其他各結(jié)點的最短路徑后，再計算其他結(jié)點間的最短路徑時，就可以將結(jié)點A 刪除，并把其他結(jié)點到v0結(jié)點的最短路徑標(biāo)為無窮大.

通過算法優(yōu)化，提前消減了圖中無益于求最短路徑的分支，提高了效率.

注意，不管是從入度還是從出度優(yōu)化，都必須考慮出入度為1 的多個結(jié)點，而且要注意該節(jié)點的前驅(qū)結(jié)點的次序.

3.2 根據(jù)已知的最短路徑快速計算其他最短路徑

如果R，S，T 是從R 到T 的最短路徑，則R 到S 的最短路徑、S 到T 的最短路徑不必再采用Dijkstra算法去計算，而可以通過已經(jīng)得到的R 到T 的最短路徑直接得到:R 到S 的最短路徑為R，S，S 到T 的最短路徑為S，T［4］.

證明:已知結(jié)點R 到結(jié)點T 的最短路徑為R，S，T;假設(shè)結(jié)點R 到結(jié)點S 的最短路徑不是R，S;而是R，…，S;那么可得出R，S，…，T;此路徑比路徑R，S，T 更短，這與已知條件R 到T 的最短路徑為R，S，T相矛盾.于是，得到R 到S 的最短路徑一定為R，S;同理可以得到S 到T 的最短路徑為S，T.

在圖3 中，如果O 到Q 的最短路徑已經(jīng)算出為:O，P，S，Q，則直接可以得出O 到P 的最短路徑為:O，P;O 到S 的最短路徑為:O，P，S;P 到S 的最短路徑為:P，S;P 到Q 的最短路徑為:P，S，Q，而不需要再采用Dijkstra 算法去計算.

圖3

采用此優(yōu)化策略對圖3 中任意兩結(jié)點快速計算最短路徑的具體步驟如下所示:

O 到Q 的最短路徑:O，P，S，Q——直接由Dijkstra 算法計算得到;

O 到P 的最短路徑:O，P——由已知最短路徑直接得到;*

O 到S 的最短路徑:O，P，S——由已知最短路徑直接得到;*

P 到S 的最短路徑:P，S——由已知最短路徑直接得到;*

P 到Q 的最短路徑:P，S，Q——由已知最短路徑直接得到;*

P 到R 的最短路徑:P，O，R——直接由Dijkstra 算法計算得到;

P 到O 的最短路徑:P，O——由已知最短路徑直接得到;*

O 到R 的最短路徑:O，R——由已知最短路徑直接得到;*

R 到Q 的最短路徑:R，S，Q——直接由Dijkstra 算法計算得到;

R 到S 的最短路徑:R，S——由已知最短路徑直接得到;*

S 到Q 的最短路徑:S，Q——由已知最短路徑直接得到;*

Q 到S 的最短路徑:Q，R，S——直接由Dijkstra 算法計算得到;

Q 到R 的最短路徑:Q，R——由已知最短路徑直接得到;*

R 到S 的最短路徑:R，S——由已知最短路徑直接得到;*

S 到R 的最短路徑:S，Q，R——直接由Dijkstra 算法計算得到;

S 到Q 的最短路徑:S，Q——由已知最短路徑直接得到;*

Q 到R 的最短路徑:Q，R——由已知最短路徑直接得到.*

從優(yōu)化后的算法可以看出17 組結(jié)點間的最短路徑，只有末用星號標(biāo)注的組是直接采用Dijkstra 算法計算到，其他均采用已經(jīng)得到的最短路徑直接得出，最短路徑的查找效率提高了許多［5］.

4 小結(jié)

隨著最短路徑算法在人們實際生活中的應(yīng)用越來越廣泛，研究高效的最短路徑算法很有價值.本文對Dijkstra 經(jīng)典算法的執(zhí)行過程分析后，針對該算法存在的計算時間長、效率低等問題，從節(jié)點的出、入度信息和全局最優(yōu)化兩個角度對Dijkstra 算法進行優(yōu)化，給出了算法的實現(xiàn)過程.實踐證明，將優(yōu)化后的算法應(yīng)用于應(yīng)急交通系統(tǒng)中有效地減少了最短路徑的計算時間，提高了查找效率.

［1］嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)［M］.北京:清華大學(xué)出版社，2007.

［2］鄧春燕.兩種最短路徑算法比較［J］.電腦知識與技術(shù)，2008，15(12):511－513.

［3］田豐.圖與網(wǎng)絡(luò)流理論［M］.北京:科學(xué)出版社，1987.

［4］龍光正，楊建軍.改進的最短路算法［J］.系統(tǒng)工程與電子技術(shù)，2009，24(6):106－108.

［5］土?xí)詵|，陳國龍，林柏鋼.網(wǎng)絡(luò)最短路問題的改進算法［J］.小型微型計算機系統(tǒng)，2009，23(9):1083－1087.