易文靜　田俊峰

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

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

中圖分類號：TP311 文獻標識碼：A 文章編號：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 緒論

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

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

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

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

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

3.1 介紹Dijkstra算法

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

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

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

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

4.1 DJ_ray算法的實現(xiàn)過程

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

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

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

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

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

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

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

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

5 結(jié)束語

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

參考文獻：

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

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

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

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

[5] 古凌嵐. GIS最短路徑分析中Dijkstra算法的優(yōu)化[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] 程理民.運籌學(xué)模型與方法教程[M]. 北京： 清華大學(xué)出版社， 2002.

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