姜惠娟

(定西師范高等?？茖W(xué)校 計(jì)算機(jī)系，甘肅 定西 743000)

1 問(wèn)題的提出

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

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

2 Dijkstra 最短路徑算法分析

2.1 算法描述

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

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

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

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

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

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

2.2 算法時(shí)間效率分析

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

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

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

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

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

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

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

(1)計(jì)算所有結(jié)點(diǎn)的出度;

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

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

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

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

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

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

(1)計(jì)算各結(jié)點(diǎn)的入度;

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

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

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

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

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

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

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

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

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

證明:已知結(jié)點(diǎn)R 到結(jié)點(diǎn)T 的最短路徑為R，S，T;假設(shè)結(jié)點(diǎn)R 到結(jié)點(diǎn)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 算法去計(jì)算.

圖3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 小結(jié)

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

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

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

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

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

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