基于Dijkstra算法的優(yōu)化研究

易文靜　田俊峰

摘要：最短路徑算法的研究及其應(yīng)用在各個(gè)領(lǐng)域都起著重要作用，例如交通領(lǐng)域的最優(yōu)路線，軍事領(lǐng)域的行軍路線，網(wǎng)絡(luò)通信領(lǐng)域的路由選擇等。該文將對(duì)最短路徑問(wèn)題中最經(jīng)典的Dijkstra（迪杰斯特拉）算法進(jìn)行介紹和優(yōu)化改進(jìn)。筆者將這種優(yōu)化改進(jìn)后的算法稱之為：DJ_ray算法，意思是對(duì)Dijkstra算法進(jìn)行發(fā)散性思想優(yōu)化。該文將會(huì)對(duì)傳統(tǒng)的Dijkstra算法與優(yōu)化后的DJ_ray算法，在思想、原理、實(shí)現(xiàn)方法、數(shù)據(jù)結(jié)構(gòu)上進(jìn)行說(shuō)明比較，并從時(shí)間及其空間復(fù)雜度上進(jìn)行分析對(duì)比。同時(shí)，為了更好地展示DJ_ray算法在實(shí)際應(yīng)用中的優(yōu)點(diǎn)，文本將以DJ_ray算法優(yōu)化火車交通網(wǎng)絡(luò)路線為案例來(lái)進(jìn)行闡述。

關(guān)鍵詞：最短路徑；交通路線；Dijkstra算法；DJ_ray算法

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）23-0166-03

Abstract： Research and application of the shortest path algorithm plays an important role in every field， such as the optimal route in the field of transportation， travel route in the field of military， routing in the field of network communication， etc.As a result， the efficiency of the shortest path algorithm in practical application of product development still need to continuously improve.This article will be to the shortest path problem is one of the most classical Dijkstra （Dijkstra） algorithm is introduced and the optimization improvement.I will improve after this optimization algorithm called： DJ_ray algorithm ，meaning： the Dijkstra algorithm to optimize divergent thinking.This article will be to the traditional Dijkstra algorithm and the optimization of the improved DJ_ray algorithm， in the thought， principle， method， data structure are compared， and explain and analysis comparison from time and space complexity.At the same time， in order to better display DJ_ray algorithm advantages in practical application， the text will be DJ_ray algorithm in GIS， the train traffic network route as a case， through a combination of theory and practice for everyone.

Key words： shortest path； traffic routes； Dijkstra algorithm； DJ_ray algorithm

1 緒論

最短路徑問(wèn)題是圖論中非常重要的最優(yōu)化問(wèn)題之一，也一直是計(jì)算機(jī)科學(xué)、交通工程學(xué)、地理信息系統(tǒng)（GIS）、運(yùn)籌學(xué)等學(xué)科領(lǐng)域研究的熱點(diǎn)。為了清晰的向大家展示其作用，以下我將通過(guò)火車最優(yōu)路線選擇的案例進(jìn)行闡述Dijkstra算法。該算法是目前交通網(wǎng)絡(luò)圖在單源最短路徑問(wèn)題上運(yùn)用最普遍、完善的算法之一，也是目前公認(rèn)在非負(fù)權(quán)值，且所有的權(quán)大于等于零時(shí)，尋求最短路問(wèn)題最好的算法，但是這樣的方法依舊存在一些缺陷，如果不對(duì)這些缺陷進(jìn)行完善改進(jìn)而直接投入實(shí)際生產(chǎn)中，必將會(huì)造成不必要的損失。

本文將分為以下四個(gè)部分：第一部分概述Dijkstra算法在案例中實(shí)現(xiàn)的意義。第二部分介紹Dijkstra算法，并提出算法優(yōu)化改進(jìn)的方案—DJ_ray算法。第三部分描述DJ_ray算法的實(shí)現(xiàn)過(guò)程和復(fù)雜度分析。最后總結(jié)，指出文章的意義。

2 Dijkstra算法在案例中實(shí)現(xiàn)的意義

火車最優(yōu)路線選擇主要體現(xiàn)在以下三個(gè)方面：費(fèi)用最少、里程最短、換乘次數(shù)最少。而這三個(gè)都可以通過(guò)Dijkstra算法計(jì)算得到，其中里程最短這個(gè)功能最為突出。Dijkstra算法實(shí)際上給出了尋求從一個(gè)給定點(diǎn)vi到任意一個(gè)點(diǎn)vs的最短路徑。因此，先明確出發(fā)地與目的地兩者之間火車能經(jīng)過(guò)的所有地方，將它們看作是定點(diǎn)，其次知道火車所經(jīng)過(guò)相鄰兩地方的里程，將里程看作是兩點(diǎn)的權(quán)值，之后便可以用Dijkstra算法進(jìn)行運(yùn)算得出最短路徑，即行程的最短路線。

3 介紹Dijkstra算法和提出算法優(yōu)化改進(jìn)方案

3.1 介紹Dijkstra算法

3.2 提出算法優(yōu)化改進(jìn)方案—DJ_ray算法

在上述的判斷過(guò)程中，v4、v6和v10都當(dāng)做過(guò)P標(biāo)號(hào)，也對(duì)這些結(jié)點(diǎn)下所在的弧統(tǒng)統(tǒng)進(jìn)行運(yùn)算判斷，可是在運(yùn)算過(guò)程之前完整的查閱一遍整個(gè)網(wǎng)絡(luò)圖，就可以清楚地發(fā)現(xiàn)v4、v6和v10所在弧的軌跡明顯偏離了正在求解的最短路徑這條軌跡，但是出于這些點(diǎn)都是P標(biāo)號(hào)點(diǎn)，用Dijkstra算法進(jìn)行運(yùn)算求解就必須對(duì)這些結(jié)點(diǎn)進(jìn)行搜索判斷，直到它們不符合運(yùn)算要求了，才將它們篩除出列。由于傳統(tǒng)的Dijkstra算法在每次判斷最小權(quán)值的結(jié)點(diǎn)時(shí)，都需要對(duì)所有具有P標(biāo)號(hào)點(diǎn)下的弧進(jìn)行求解判斷，而這些具有P標(biāo)號(hào)的結(jié)點(diǎn)又是無(wú)序分布的，因此在判斷過(guò)程中，會(huì)出現(xiàn)某些結(jié)點(diǎn)被多次判定的情況，甚至出現(xiàn)上述呈現(xiàn)的具有P標(biāo)號(hào)的結(jié)點(diǎn)并不能到達(dá)最終結(jié)點(diǎn)的現(xiàn)象，對(duì)于以上種種情況要是在大的數(shù)據(jù)量下求解，必將會(huì)增加更大額外運(yùn)算量，花費(fèi)更多的排查時(shí)間，使該算法在解決實(shí)際問(wèn)題中的效率大大減低。

為了使Dijkstra算法在實(shí)際運(yùn)用過(guò)程效率更大化，對(duì)Dijkstra算法進(jìn)行發(fā)散性思維的優(yōu)化，并將優(yōu)化后的算法命名為DJ_ray算法。以下是DJ_ray算法優(yōu)化的兩大方向：第一點(diǎn)，傳統(tǒng)的Dijkstra算法是對(duì)圖中所經(jīng)過(guò)的每一個(gè)點(diǎn)都進(jìn)行了判斷，倘若在求解最短路徑之前對(duì)所有的結(jié)點(diǎn)對(duì)象進(jìn)行一個(gè)排序的預(yù)處理，使得每次求解最小權(quán)值時(shí)不需要對(duì)所有的P結(jié)點(diǎn)進(jìn)行判定。而這種預(yù)處理方法可以運(yùn)用數(shù)據(jù)結(jié)構(gòu)中圖的遍歷中的深度優(yōu)先搜索，從起點(diǎn)出發(fā)到終點(diǎn)結(jié)束，引出若干條連通的線段，將各線段上的結(jié)點(diǎn)作為最短路徑問(wèn)題求解所涉及的結(jié)點(diǎn)選出，之后對(duì)這些結(jié)點(diǎn)進(jìn)行廣度優(yōu)先搜索，層次排序。 第二點(diǎn)，將上述所選擇的這些結(jié)點(diǎn)作為數(shù)據(jù)結(jié)構(gòu)中單鏈表的結(jié)點(diǎn)，然后先將各個(gè)結(jié)點(diǎn)進(jìn)行面向?qū)ο蟮姆庋b，之后通過(guò)map（key，object）方法將封裝好的類的key鍵放入在單鏈表的指針域next中，將映射出來(lái)的object對(duì)象（即封裝類數(shù)據(jù)）作為單鏈表結(jié)點(diǎn)中的數(shù)據(jù)域data值。這樣就可以在搜索過(guò)程中，不必花費(fèi)大量的時(shí)間和存儲(chǔ)空間， 從而大大提高算法的效率。

4 DJ_ray算法的實(shí)現(xiàn)過(guò)程和復(fù)雜度分析

4.1 DJ_ray算法的實(shí)現(xiàn)過(guò)程

1）深度優(yōu)先搜索

通過(guò)圖2與圖1進(jìn)行比較可以看出結(jié)點(diǎn)v4、v6、v9和v10已經(jīng)在深度優(yōu)先搜索中直接篩除出列，事實(shí)上，從圖1便可以很清楚地看見這四個(gè)結(jié)點(diǎn)所在的路線并不能抵達(dá)終點(diǎn)v8.所以，進(jìn)行該優(yōu)化步驟能避免傳統(tǒng)的Dijkstra算法盲目取點(diǎn)搜索缺陷，不僅減少運(yùn)算量、縮短時(shí)間，還減少存儲(chǔ)空間資源。

2）廣度優(yōu)先搜索

然后對(duì)進(jìn)行了深度優(yōu)先搜索的起點(diǎn)vi到終點(diǎn)vs連通子圖進(jìn)行廣度優(yōu)先搜索，其搜索目的在于確定各結(jié)點(diǎn)在子圖中的層次關(guān)系，需對(duì)各結(jié)點(diǎn)做合理的分層安排。DJ_ray算法對(duì)分層問(wèn)題也進(jìn)行了最優(yōu)分層處理。所謂的最優(yōu)分層是指，將子圖中涉及求解的所有結(jié)點(diǎn)分布在離起點(diǎn)最近的一層。如圖3列車單行線廣度優(yōu)先搜索子圖。

廣度優(yōu)先搜索先用最優(yōu)分層排序法，確定各結(jié)點(diǎn)所在的層次，再確定各層結(jié)點(diǎn)間是否存在聯(lián)系，為后續(xù)結(jié)點(diǎn)對(duì)象存儲(chǔ)在單鏈表提供方便。在使用Dijkstra算法求解最短路徑時(shí)，是根據(jù)各結(jié)點(diǎn)間的權(quán)值來(lái)判定最終選哪個(gè)結(jié)點(diǎn)作為下一個(gè)P標(biāo)號(hào)，DJ_ray算法也不例外，而將各結(jié)點(diǎn)放置在離起點(diǎn)最近的層次，這樣該點(diǎn)若是在最終的最短路徑線路上也可以最快地找到，比它權(quán)值大的結(jié)點(diǎn)均可直接篩除出列，這種方法即快捷又人性化。

3）面向?qū)ο蠓庋b

最后采用Java語(yǔ)言的面向?qū)ο蟮乃枷耄浜蠁捂湵淼拇鎯?chǔ)結(jié)構(gòu)，使案例中交通網(wǎng)絡(luò)圖在搜索過(guò)程即快捷又準(zhǔn)確。根據(jù)對(duì)象具有封裝性、繼承性、多態(tài)性特征，有利于清晰地表達(dá)多個(gè)不同類型的數(shù)據(jù)域，創(chuàng)建一個(gè)空對(duì)象，把篩選好的其中一個(gè)結(jié)點(diǎn)位置、結(jié)點(diǎn)的相鄰邊、結(jié)點(diǎn)的相鄰結(jié)點(diǎn)、起點(diǎn)到該結(jié)點(diǎn)的最短路徑長(zhǎng)度等多種信息，設(shè)置在這個(gè)空對(duì)象中進(jìn)行封裝。然后使用Java語(yǔ)言中的Map（key，value）方法，將value（即封裝好的對(duì)象數(shù)據(jù)）通過(guò)key鍵映射出來(lái)。接著將key鍵指向單鏈表上結(jié)點(diǎn)的指針域，value值則映射在單鏈表中結(jié)點(diǎn)的數(shù)據(jù)域中。由于封裝后的對(duì)象具有復(fù)用性，可以避免一個(gè)結(jié)點(diǎn)在多次判定是進(jìn)行多次運(yùn)算求解，這種方式既節(jié)省了許多存儲(chǔ)空間，又大大縮短了運(yùn)算的時(shí)間。

4.2 DJ_ray算法復(fù)雜度分析

5 結(jié)束語(yǔ)

通過(guò)火車最優(yōu)路線選擇案例，介紹了一種優(yōu)化后的求解最短路徑問(wèn)題的算法——DJ_ray算法，該算法是通過(guò)對(duì)Dijkstra算法在物理結(jié)構(gòu)、數(shù)據(jù)結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)上進(jìn)行優(yōu)化改進(jìn)后創(chuàng)建的新算法。先通過(guò)兩種優(yōu)先搜索方式對(duì)網(wǎng)絡(luò)圖中的結(jié)點(diǎn)進(jìn)行排余、排序處理，然后再用面向?qū)ο蟮奶匦詫?duì)篩選后的結(jié)點(diǎn)進(jìn)行封裝管理，接著參照Dijkstra算法的基本思想通過(guò)鍵值對(duì)的方式，將鍵指向作為存儲(chǔ)結(jié)構(gòu)的單鏈表結(jié)點(diǎn)指針域上，而值則映射在單鏈表結(jié)點(diǎn)數(shù)據(jù)域中。DJ_ray算法不僅能縮短運(yùn)算周期，還減少了存儲(chǔ)空間，在實(shí)際運(yùn)用中能高效的處理問(wèn)題。本文只是對(duì)交通網(wǎng)絡(luò)圖的單行線路進(jìn)行了Dijkstra算法的優(yōu)化改進(jìn)，至于雙向線路網(wǎng)絡(luò)圖效果如何？或是使用何種算法更有效的處理雙向線路圖？如何對(duì)這種算法進(jìn)行優(yōu)化改進(jìn)？而這些種種問(wèn)題都需要我們?nèi)パ芯?、去發(fā)現(xiàn)。

參考文獻(xiàn)：

[1] 吳祈宗. 運(yùn)籌學(xué)[M]. 3版.北京： 機(jī)械工業(yè)出版社， 2013.

[2] 耿國(guó)華. 數(shù)據(jù)結(jié)構(gòu)（用C語(yǔ)言描述）[M]. 北京： 高等教育出版社， 2011.

[3] 龔櫪. 圖論與網(wǎng)絡(luò)最優(yōu)化算法[M]. 重慶： 重慶大學(xué)出版社， 2009.

[4] 賀景. 交通咨詢系統(tǒng)的最短路徑算法與實(shí)現(xiàn)[J]. 西安財(cái)經(jīng)學(xué)院學(xué)報(bào)， 2015（5）.

[5] 古凌嵐. GIS最短路徑分析中Dijkstra算法的優(yōu)化[J]. 廣東： 計(jì)算機(jī)與數(shù)字工程， 2006，34（12）：53-55.

[6] Michael King.A mini max method for finding the best differentiated paths[J]. Geographical Analysis， 1997，29（4）：298-313.

[7] 程理民.運(yùn)籌學(xué)模型與方法教程[M]. 北京： 清華大學(xué)出版社， 2002.

[8] 董俊， 黃傳河. 改進(jìn)Dijkstra算法在GIS導(dǎo)航應(yīng)用中最短路徑搜索研究[J]. 武漢大學(xué)計(jì)算機(jī)學(xué)院學(xué)刊， 2012，39（10）：245-247.