Dijkstra算法優(yōu)化綜述

【摘 要】文章簡述了Dijkstra經(jīng)典算法的提出及應(yīng)用，討論了算法的基本原理及不足之處。列舉了國內(nèi)外對(duì)Dijkstra經(jīng)典算法的優(yōu)化進(jìn)展，同時(shí)列舉了其應(yīng)用領(lǐng)域，指出進(jìn)一步的研究方向，為Dijkstra經(jīng)典算法優(yōu)化的相關(guān)研究提供參考。

【關(guān)鍵詞】Dijkstra算法；優(yōu)化

【Abstract】The papaer described the application of the classical Dijkstra algorithm and discussed the basic prnciple and shortcomings of algorithm. Listing the progress of optimization of the classical algorithm Dijkstra at home and abroad and its application field and pointing out rhe directions for the further study， providing a reference for the related research of classical Dijkstra algorithm.

【Key words】Dijkstra algorithm， optimization

1 引言

Dijkstra經(jīng)典算法是由計(jì)算機(jī)科學(xué)家Edsger Dijkstra在文獻(xiàn)中提出的。它是一個(gè)圖的搜索算法，解決帶非負(fù)權(quán)重圖的單元最短路徑問題并產(chǎn)生一棵最短路徑樹。該算法經(jīng)常使用在網(wǎng)絡(luò)路由和地理信息系統(tǒng)中。

2 Dijkstra算法原理

（1）算法分配給每個(gè)節(jié)點(diǎn)一個(gè)初步的距離值：設(shè)置初始節(jié)點(diǎn)為零和其他節(jié)點(diǎn)為無窮；

（2）將當(dāng)前訪問節(jié)點(diǎn)設(shè)置為初始節(jié)點(diǎn)，其他的所有節(jié)點(diǎn)設(shè)置為未訪問節(jié)點(diǎn)，并創(chuàng)建一個(gè)未訪問節(jié)點(diǎn)集合；

（3）針對(duì)當(dāng)前節(jié)點(diǎn)，計(jì)算其與所有鄰接節(jié)點(diǎn)的距離。將計(jì)算出來的距離值與當(dāng)前值進(jìn)行比較，指定較小的一個(gè)。

（4）當(dāng)我們考慮完當(dāng)前節(jié)點(diǎn)的所有鄰接節(jié)點(diǎn)，標(biāo)記當(dāng)前為已訪問，并將其從未訪問集合刪除。已訪問節(jié)點(diǎn)將永遠(yuǎn)不會(huì)被訪問；

（5）選擇為訪問過的標(biāo)記最小試探距離的節(jié)點(diǎn)，并將其作為新的當(dāng)前節(jié)點(diǎn)，然后回到步驟3；

（6）如果終止節(jié)點(diǎn)已標(biāo)記訪問或者最小試探性距離在未設(shè)置節(jié)點(diǎn)之間是無限的，該算法已完成。

3 Dijkstra算法優(yōu)化

在Dijkstra算法中，一般采用一個(gè)可更新排序的優(yōu)先隊(duì)列來實(shí)現(xiàn)對(duì)已經(jīng)計(jì)算過距離中距離最小的節(jié)點(diǎn)。因此，如何實(shí)現(xiàn)Dijkstra算法的優(yōu)先隊(duì)列結(jié)構(gòu)，就成為提高Dijkstra算法性能的關(guān)鍵。

Dijkstra算法的優(yōu)先隊(duì)列需要進(jìn)行INSERT（插入）、EXTRACT-MIN（調(diào)整最小）、DECREASE-KEY（降級(jí)）三個(gè)基本操作。對(duì)于圖（V，E），經(jīng)典Dijkstra算法每次INSERT和DECREASE-KEY操作的執(zhí)行時(shí)間為O（1），每次EXTRACT-MIN的操作時(shí)間為O（V）（因?yàn)樾枰阉髡麄€(gè)為訪問節(jié)點(diǎn)數(shù)組），算法的總運(yùn)行時(shí)間為O（V2+E）= O（V2）。

由Donald B. Johnson 在文獻(xiàn)提出來采用的d-堆每個(gè)節(jié)點(diǎn)有d個(gè)兒子，這使得插入和降級(jí)操作的時(shí)間復(fù)雜度改進(jìn)為O（logdV），但調(diào)整最小的時(shí)間復(fù)雜度只提高到O（dlogdV）。因此，它在最好情況下可以把Dijkstra算法的時(shí)間復(fù)雜度提高到O（Elog（2+（E/V）V）。

由Michael L. Fredman，Robert Endre Tarjan 在文獻(xiàn)提出的斐波那契堆，使得插入操作時(shí)間復(fù)雜度為O（1），降級(jí)的攤還時(shí)間復(fù)雜度為O（1），調(diào)整最小的攤還時(shí)間復(fù)雜度為O（logV），Dijkstra算法的時(shí)間復(fù)雜度為O（E+VlogV）。

由Henzinger MR，Rao S，Subramanian S，Klein P在文獻(xiàn)提出來采用二叉堆的優(yōu)先隊(duì)列的所有操作時(shí)間復(fù)雜度為O（logV），Dijkstra算法的時(shí)間復(fù)雜度為O（ElogV）。

由于經(jīng)典Dijkstra算法在每次迭代中都需要掃描所有未標(biāo)記節(jié)點(diǎn)，面對(duì)海量的數(shù)據(jù)，算法執(zhí)行效率非常低。因此單單只通過上述優(yōu)化數(shù)據(jù)結(jié)構(gòu)已經(jīng)不夠，還需要減少搜索量。

這方面的優(yōu)化有：（1）使用評(píng)估函數(shù)來接近目標(biāo)地節(jié)點(diǎn)；（2）利用當(dāng)前目標(biāo)地之間的夾角關(guān)系，使當(dāng)前節(jié)點(diǎn)趨向于目標(biāo)節(jié)點(diǎn)；（3）用限制區(qū)域來減少遍歷節(jié)點(diǎn)；（4）處理交匯路徑減少搜索路徑。這些優(yōu)化方法有的利用特定信息，有的則是在特殊情況下的優(yōu)化效果明顯。因此，今后的優(yōu)化方向應(yīng)當(dāng)在優(yōu)化經(jīng)典Dijkstra算法結(jié)構(gòu)的同時(shí)，根據(jù)數(shù)據(jù)的不同情況進(jìn)行細(xì)分，期望達(dá)到最優(yōu)。

4 結(jié)束語

Dijkstra算法是求單源最短路徑的經(jīng)典算法，主要應(yīng)用于網(wǎng)絡(luò)路由和地理信息系統(tǒng)的最優(yōu)路徑求解。但是，隨著數(shù)據(jù)的海量式增長，經(jīng)典Dijkstra算法的運(yùn)行效率已經(jīng)無法人們的需求，滿足需要從各方面進(jìn)行優(yōu)化。本文給出了國內(nèi)外研究Dijkstra算法的主要研究方向，通過對(duì)比總結(jié)出今后優(yōu)化的方向，希望對(duì)廣大研究人員有參考意義。

參考文獻(xiàn)：

[1]E. W. Dijkstra. A note on two problems in connexion with graphs [J]. Numerische Mathematik， 1959.

[2]Donald B. Johnson.Priority queues with update and finding minimum spanning trees [J].Information Processing Letters， 1975.

[3]Michael L. Fredman，Robert Endre Tarjan [J]. Journal of the ACM， 1987.

[4]Henzinger MR，Rao S，Subramanian S，Klein P.Faster shortest-path algorithms for planar graphs [J].Journal of Computer and System Sciences， 1997.

[5]Robert Sedgewick ，Jeffrey Scott Vitter. Shortest paths in euclidean graphs[J].Algorithmica， 1986.

[6]嚴(yán)寒冰，劉迎春. 基于GIS的城市道路網(wǎng)最短路徑算法探討[J]. 計(jì)算機(jī)學(xué)報(bào)， 2000.

[7]盧冬梅，崔偉宏. 交通網(wǎng)絡(luò)限制搜索區(qū)域時(shí)間最短路徑算法[J]. 中國圖像圖形學(xué)報(bào)， 1999.

[8]劉剛，李永樹，楊駿. 一種Dijkstra算法改進(jìn)方法的研究與實(shí)現(xiàn)[J]. 測繪科學(xué)，2011.