東北電力大學(xué)本科畢業(yè)設(shè)計(jì)（論文）

1、<p>　　本科畢業(yè)設(shè)計(jì)（論文）</p><p>　　Dijkstra最短路徑算法的優(yōu)化和改進(jìn)</p><p><b>　　學(xué) 生 姓 名：</b></p><p><b>　　指 導(dǎo) 教 師： </b></p><p><b>　　專業(yè)、 班級(jí)：</b></p

2、><p><b>　　院 （系）：</b></p><p>　　2013 年 6 月 吉 林</p><p><b>　　摘 要</b></p><p>　　隨著計(jì)算機(jī)和地理信息科學(xué)的發(fā)展，GIS（地理信息系統(tǒng)）的應(yīng)用領(lǐng)域越來越廣．最短路徑分析是GIS地理網(wǎng)絡(luò)分析功能中的一個(gè)關(guān)鍵性的問

3、題．計(jì)算最短路徑的經(jīng)典算法之一就是Dijkstra算法，許多工程中解決最短路徑問題都是采用這種算法．然而，傳統(tǒng)的Dijkstra算法在求解節(jié)點(diǎn)間最短路徑時(shí)，對(duì)已標(biāo)識(shí)節(jié)點(diǎn)外的大量節(jié)點(diǎn)進(jìn)行了計(jì)算，從而影響了算法的速度．</p><p>　　該算法的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止．Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹．本文在傳統(tǒng)Dijkst

4、ra算法的基礎(chǔ)上，對(duì)其進(jìn)行了優(yōu)化，此優(yōu)化算法只對(duì)最短路徑上節(jié)點(diǎn)的鄰點(diǎn)做了一些處理，從而不涉及到其他的一些節(jié)點(diǎn)．提出的優(yōu)化算法在更新最短路徑值與選擇最短路徑值最小的節(jié)點(diǎn)時(shí)，僅僅涉及到節(jié)點(diǎn)的鄰居集合及已標(biāo)識(shí)集合中所有節(jié)點(diǎn)的鄰居集合與已標(biāo)識(shí)集合的差集，其運(yùn)行時(shí)間取決于轉(zhuǎn)接點(diǎn)的鄰居集合的元素?cái)?shù)量多少．通過減小算法中成功搜索的搜索范圍和改進(jìn)算法的存儲(chǔ)結(jié)構(gòu)這兩個(gè)主要的研究方向使算法得到優(yōu)化．因而，此優(yōu)化算法在計(jì)算的節(jié)點(diǎn)數(shù)較傳統(tǒng)算法大幅減少，提高了算

5、法的速度．本文通過實(shí)驗(yàn)和實(shí)際應(yīng)用對(duì)改進(jìn)后的算法進(jìn)行了簡(jiǎn)單的驗(yàn)證．之后將一些算法的改進(jìn)和實(shí)際例子相結(jié)合，這樣就能使文章中算法的優(yōu)化更為理想．</p><p>　　關(guān)鍵詞 最短路徑；Dijkstra；優(yōu)化算法</p><p><b>　　Abstract</b></p><p>　　With the development of computer

6、 and geographic information science, the applications of GIS (Geographic Information System) are becoming more and more widely. However, shortest path analysis is the key problem of network analyses, Dijkstra algorithm i

7、s a classic arithmetic for the shortest path. It is the academic foundation that many engineerings were solved in the shortest path is use. When a shortest path between nodes is searched with Dijkstra algorithm, a lot of

8、 nodes away from lagged node</p><p>　　Main features of the algorithm is the starting point as the center outward expansion layers until it extended to the end point. Dijkstra's algorithm is very represen

9、tative of the shortest path algorithm, in many professional courses in the basic content as described in detail. The proposed algorithm updates the shortest path in the value of the minimum value of the shortest path to

10、the node, only the set of neighbors of the node related to the identified set and a neighbor set of all nodes in th</p><p>　　Keywords The shortest path; Dijkstra; Optimization algorithm</p><p>

11、<b>　　目 錄</b></p><p><b>　　摘要I</b></p><p>　　AbstractII</p><p><b>　　目錄III</b></p><p><b>　　第1章 緒論1</b></p>&l

12、t;p>　　1.1 國(guó)內(nèi)外最短路徑算法的發(fā)展及其概況1</p><p>　　1.2 傳統(tǒng)Dijkstra算法仍然存在的一些問題1</p><p>　　1.3 本文工作2</p><p>　　第2章 Dijkstra經(jīng)典算法3</p><p><b>　　2.1 引言3</b></p>

13、<p>　　2.2 原理及應(yīng)用3</p><p>　　2.2.1 原理3</p><p>　　2.2.2 應(yīng)用5</p><p>　　2.3 Dijkstra算法與其他主流算法的比較6</p><p>　　2.3.1 搜索速度比較6</p><p>　　2.3.2 搜索成功率比較7

14、</p><p>　　2.3.3 Dijkstra算法的優(yōu)缺點(diǎn)8</p><p>　　第3章 兩點(diǎn)間最短路的改進(jìn)的Dijkstra算法及其MATLAB實(shí)現(xiàn)9</p><p>　　3.1 Dijkstra矩陣算法I9</p><p>　　3.2 Dijkstra矩陣算法II9</p><p>　　第4章

15、 基于Dijkstra算法的優(yōu)化算法的研究13</p><p>　　4.1 幾種優(yōu)化算法13</p><p>　　4.1.1 減小算法中成功搜索的搜索范圍13</p><p>　　4.1.2 改進(jìn)算法的存儲(chǔ)結(jié)構(gòu)13</p><p>　　4.2 本文對(duì)Dijlstra優(yōu)化算法研究14</p><p>　

16、　4.2.1 優(yōu)化目標(biāo)14</p><p>　　4.2.2 優(yōu)化思路14</p><p>　　4.2.3 問題描述15</p><p>　　4.2.4 算法特點(diǎn)19</p><p>　　4.3 優(yōu)化和改進(jìn)的結(jié)論20</p><p>　　第5章 Dijkstra算法在物流上的應(yīng)用21</p&

17、gt;<p>　　5.1 最優(yōu)配送路線選擇問題22</p><p>　　5.2 改進(jìn)的 Dijkstra 算法在最優(yōu)配送路線確定中的實(shí)例24</p><p>　　5.2.1 路徑優(yōu)化結(jié)果26</p><p><b>　　結(jié)論28</b></p><p><b>　　參考文獻(xiàn)29&l

18、t;/b></p><p><b>　　致謝30</b></p><p><b>　　附錄31</b></p><p><b>　　第1章 緒論</b></p><p>　　最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，其算法有很多種，其中傳統(tǒng)的Dijks

19、tra算法一般用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小代價(jià)路徑，并且能夠適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓?，性能穩(wěn)定，因而可以在運(yùn)輸路線規(guī)劃等領(lǐng)域都應(yīng)用廣泛．</p><p>　　1.1 國(guó)內(nèi)外最短路徑算法的發(fā)展及其概況</p><p>　　最短路徑在20世紀(jì)初開始受到人們的重視，關(guān)于它的求解方法，當(dāng)時(shí)有很多科學(xué)家在研究．但給出求解的基本思想的人直到1959年才出現(xiàn)，是一位名叫Edsger Wybe Di

20、jkstra（迪杰斯特拉）的荷蘭計(jì)算機(jī)科學(xué)家，他不僅給出了求解的基本思想，還給出了算法．他給出的算法主要解決的問題是從某一個(gè)固定的點(diǎn)到其他各點(diǎn)的最短路徑問題．后來這個(gè)算法被譽(yù)為一代經(jīng)典，被稱作Dijkstra算法．后來，人們逐漸從兩個(gè)方面來研究最短路徑，分為完全信息情況下和不確定情況下．確定情況下對(duì)最短路徑的研究的過程中，發(fā)展出了很多高效的算法，其中1958年的Bellman算法、1959年的Dijkstra算法、1969年的Dreyf

21、us算法已成為確定情況下的經(jīng)典算法[1]．而不確定情況下對(duì)最短問題的研究又分成了四個(gè)方面：研究路段長(zhǎng)度隨機(jī)變化的最短路徑問題，以Frank和Mirchandani為代表；研究不同費(fèi)用函數(shù)最短路徑問題，以Loui、Muethy和Sarkar為代表；研究時(shí)間獨(dú)立情況下的路段長(zhǎng)度隨機(jī)變化的最短路徑問題，Hall、LiPing Fu、L.R.Rilett、Elise和Hani為代表；研究路段長(zhǎng)度為區(qū)</p><p>　　

22、1.2 傳統(tǒng)Dijkstra算法仍然存在的一些問題</p><p>　　原始Dijkstra算法在存儲(chǔ)圖形數(shù)據(jù)和運(yùn)算時(shí)，基于網(wǎng)絡(luò)的權(quán)矩陣，需要根據(jù)其節(jié)點(diǎn)與距離之間的關(guān)系，形成關(guān)聯(lián)矩陣、鄰接矩陣與距離矩陣，需要定義的數(shù)組來存儲(chǔ)數(shù)據(jù)，其中為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較大時(shí)，將占用大量的計(jì)算機(jī)內(nèi)存．</p><p>　　原始Dijkstra算法在運(yùn)行時(shí)一般將網(wǎng)絡(luò)節(jié)點(diǎn)分為未標(biāo)記節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)

23、點(diǎn)和永久標(biāo)記節(jié)點(diǎn)3種類型．網(wǎng)絡(luò)中所有節(jié)點(diǎn)首先初始化為未標(biāo)記節(jié)點(diǎn)，在搜索過程中和最短路徑節(jié)點(diǎn)相連通的節(jié)點(diǎn)為臨時(shí)標(biāo)記節(jié)點(diǎn)，每一次循環(huán)都是從臨時(shí)標(biāo)記節(jié)點(diǎn)中搜索距離原點(diǎn)路徑長(zhǎng)度最短的節(jié)點(diǎn)作為永久標(biāo)記節(jié)點(diǎn)，直至找到目標(biāo)節(jié)點(diǎn)或者所有節(jié)點(diǎn)都成為永久標(biāo)記節(jié)點(diǎn)才結(jié)束算法．根據(jù)算法的描述可知對(duì)臨時(shí)標(biāo)記節(jié)點(diǎn)的遍歷成為Dijkstra算法的瓶頸，影響了算法的執(zhí)行效率．</p><p>　　1.3 本文工作 </p>&l

24、t;p>　　隨著社會(huì)的不斷進(jìn)步，最短路徑算法在人們的日常生活顯得越來越重要．每天開車去上班，應(yīng)該選擇哪條公路才能使自己到公司的費(fèi)用最低、時(shí)間最少，這是最短路徑的問題；在網(wǎng)絡(luò)路由中，怎樣選擇最優(yōu)的路由路徑，這也是最短路徑問題；在交通旅游、城市規(guī)劃以及電網(wǎng)架設(shè)中怎樣使其耗費(fèi)的資金最少，這還是最短路徑問題．由此可見對(duì)最短路徑問題的研究是非常有意義的．</p><p>　　第2章 Dijkstra經(jīng)典算法<

25、/p><p><b>　　2.1 引言</b></p><p>　　Dijkstra算法是典型最短路算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑．主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止．Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)很多，所以效率低．如何改進(jìn)這一經(jīng)典算法，成為了實(shí)現(xiàn)圖論中賦權(quán)圖中解決實(shí)際問題的重要課題．</p

26、><p>　　2.2 原理及應(yīng)用</p><p>　　Dijkstra(迪杰斯特拉)算法是典型的單源最短路徑算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短路徑．主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止．Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本內(nèi)容有詳細(xì)的介紹，如數(shù)據(jù)結(jié)構(gòu)，圖論，運(yùn)籌學(xué)等等．Dijkstra一般的表述通常有兩種方式，一種用永久和臨時(shí)

27、標(biāo)號(hào)方式，一種是用OPEN, CLOSE表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式．該算法要求圖中不存在負(fù)權(quán)邊．</p><p><b>　　2.2.1 原理</b></p><p>　　Dijkstra算法是1959年由E．W．Dijkstra提出的圖論中求最短路徑的一個(gè)著名的算法，使用其可以求得圖中一點(diǎn)到其他各頂點(diǎn)的最短路徑．原始的Dijkstra算法將網(wǎng)絡(luò)結(jié)點(diǎn)分

28、成3部分：未標(biāo)記結(jié)點(diǎn)、臨時(shí)標(biāo)記結(jié)點(diǎn)和永久標(biāo)記結(jié)點(diǎn)．網(wǎng)絡(luò)中所有結(jié)點(diǎn)首先初始化為未標(biāo)記結(jié)點(diǎn)，在搜索過程中和最短路徑中的結(jié)點(diǎn)相連通的結(jié)點(diǎn)為臨時(shí)標(biāo)記結(jié)點(diǎn)，每次循環(huán)都是從臨時(shí)標(biāo)記結(jié)點(diǎn)中搜索距源點(diǎn)路徑長(zhǎng)度最短的結(jié)點(diǎn)作為永久標(biāo)記結(jié)點(diǎn)，直至找到目標(biāo)結(jié)點(diǎn)或者所有的結(jié)點(diǎn)都成為永久標(biāo)記結(jié)點(diǎn)來結(jié)束算法．</p><p>　　假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào)（,），其中是從起源點(diǎn)到點(diǎn)的最短路徑的長(zhǎng)度（從頂點(diǎn)到其本身的最短路徑是零路（沒有弧的路），其

29、長(zhǎng)度等于零）； 則是從到的最短路徑中點(diǎn)的前一點(diǎn)．求解從起源點(diǎn)到點(diǎn)的最短路徑算法的基本過程如下：</p><p>　?。?）初始化．起源點(diǎn)設(shè)置為：①,為空；②所有其他點(diǎn):,；③標(biāo)記起源點(diǎn)，記,其他所有點(diǎn)設(shè)為未標(biāo)記的．</p><p>　?。?）檢驗(yàn)從所有已標(biāo)記的點(diǎn)到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置：式中，是從點(diǎn)到的直接連接距離．</p><p>　　（3）選取下

30、一個(gè)點(diǎn)．從所有未標(biāo)記的結(jié)點(diǎn)中，選取中最小的一個(gè)：</p><p>　　，（所有未標(biāo)記的點(diǎn)），點(diǎn)就被選為最短路徑中的一點(diǎn)，并設(shè)為已標(biāo)記的．</p><p>　?。?）找到點(diǎn)的前一點(diǎn)．從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)的點(diǎn)，作為前一點(diǎn)，設(shè)置：=．</p><p>　?。?）標(biāo)記點(diǎn)．如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則，記=，轉(zhuǎn)到（2）再繼續(xù)．</p><

31、;p>　　10 </p><p><b>　　30</b></p><p>　　10 </p><p&

32、gt;　　50 60</p><p><b>　　20 </b></p><p>　　圖2-1 Dijkstra算法最短路徑應(yīng)用演示圖</p><p>　　表2-1 0節(jié)點(diǎn)到4節(jié)點(diǎn)的最短路徑</p><p><b>　　2.2.2 應(yīng)用</b><

33、;/p><p>　　給定簡(jiǎn)單定簡(jiǎn)單無向圖,指定一頂點(diǎn)為起點(diǎn),對(duì)于任意 ∈ 且≠,求到的最短路徑的長(zhǎng)度．</p><p>　　例：某單位使用一臺(tái)設(shè)備，在每年年初，企業(yè)部門領(lǐng)導(dǎo)都要決定是購(gòu)置新設(shè)備代替原來的舊設(shè)備，還是繼續(xù)使用舊設(shè)備．若購(gòu)置新設(shè)備，需要支付一定的購(gòu)置費(fèi)用；若繼續(xù)使用舊設(shè)備，需支付一定的維修費(fèi)用．設(shè)該種設(shè)備在每年年初的價(jià)格（萬元）見表2-2使用的不同時(shí)間（年）的設(shè)備所需要的維修費(fèi)用（

34、萬元）見表2-3．問如何制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使總費(fèi)用最少．</p><p><b>　　表2-2 價(jià)格表</b></p><p>　　表2-3 維修費(fèi)用表</p><p>　　圖2-2 賦權(quán)有向網(wǎng)絡(luò)圖</p><p>　　用點(diǎn)表示“第i年年初購(gòu)進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)，=1，2，…，5，用表示第五年底的狀態(tài)

35、．對(duì)于每個(gè)=1，2，…，5從到，…；各畫一條弧，?。?，）表示在第i年年初購(gòu)進(jìn)一臺(tái)設(shè)備一直使用到第年年初（即第年底）．每條弧的權(quán)可按已知的數(shù)據(jù)計(jì)算出來，例如（，）表示第一年年初購(gòu)進(jìn)一臺(tái)新設(shè)備，需支付11萬元，一直使用到第三年年底，需維修費(fèi)（5+6+8）萬元=19萬元，故其上的權(quán)為30．</p><p>　　這樣就可以得到一個(gè)賦權(quán)有向網(wǎng)絡(luò)，如圖2-3所示，所求問題等價(jià)于需找從到的最短路問題．用Dijkstra算法求解

36、，最優(yōu)解為（，，），即分別在第1、4年年初購(gòu)買一臺(tái)新設(shè)備，總費(fèi)用為53萬元．上述為Dijkstra最基本的求解路徑的方法．</p><p>　　2.3 Dijkstra算法與其他主流算法的比較</p><p>　　2.3.1 搜索速度比較</p><p>　　對(duì)5張圖分別采用Dijkstra算法、算法、遺傳算法進(jìn)行路徑規(guī)劃，他們各自花費(fèi)的時(shí)間如表2-4所示．&l

37、t;/p><p>　　表2-4 算法速度對(duì)比圖</p><p>　　由上表可以看出：當(dāng)?shù)貓D節(jié)點(diǎn)個(gè)數(shù)和弧的條數(shù)比較少時(shí)，三種算法所花費(fèi)的時(shí)間差不多，當(dāng)節(jié)點(diǎn)個(gè)數(shù)和弧的條數(shù)比較多時(shí)，A*算法最快，遺傳算法其次，Dijkstra算法最慢，而且這種差距將隨節(jié)點(diǎn)和弧數(shù)量的增加而變得更加明顯．對(duì)于實(shí)際地圖而言，由于節(jié)點(diǎn)與道路的數(shù)量一般都很的大，Dijkstra算法在搜索速度方面弱勢(shì)明顯．</p>

38、;<p>　　2.3.2 搜索成功率比較</p><p>　　對(duì)于具有個(gè)節(jié)點(diǎn)的地圖，其待規(guī)劃節(jié)點(diǎn)的個(gè)數(shù)為（除起點(diǎn)節(jié)點(diǎn)外，其他均可作為待規(guī)劃節(jié)點(diǎn)），由于每個(gè)待規(guī)劃節(jié)點(diǎn)對(duì)應(yīng)于一條最短路徑，所以對(duì)每張具有個(gè)節(jié)點(diǎn)的地圖而言，應(yīng)該規(guī)劃出條最短路徑．</p><p>　　對(duì)5張地圖分別采用三種算法進(jìn)行路徑規(guī)劃，三者各自搜索到最短路徑的情況如表2-5所示．表中括號(hào)外數(shù)據(jù)為各算法實(shí)際得到最

39、短路徑數(shù)，括號(hào)內(nèi)數(shù)據(jù)則為各算法實(shí)際得到路徑數(shù)和應(yīng)該規(guī)劃出的最短路徑數(shù)之比．</p><p>　　表2-5 三種算法在搜索質(zhì)量方面的對(duì)比</p><p>　　由表2-5可以看出：當(dāng)?shù)貓D節(jié)點(diǎn)個(gè)數(shù)和弧數(shù)量比較多時(shí)，Dijkstra算法是一種遍歷算法，每次能保證100%搜索到最短路徑，遺傳算法搜索到最短路徑的成功率比Dijkstra算法低一些，算法最低，且這種差距在節(jié)點(diǎn)數(shù)和弧數(shù)量越大時(shí)更加明顯．

40、</p><p>　　2.3.3 Dijkstra算法的優(yōu)缺點(diǎn)</p><p>　　Dijkstra算法能夠保證100%找到最優(yōu)解，但其搜索速度較慢，搜索效率非常低，時(shí)間花費(fèi)較多，一般只能用于離線的路徑規(guī)劃問題．</p><p>　　如節(jié)點(diǎn)數(shù)為的圖，用Dijkstra算法計(jì)算最短路徑總共需要迭代次，每次迭代都新加一個(gè)節(jié)點(diǎn)到臨時(shí)節(jié)點(diǎn)集合中，由于第i次迭代時(shí)不在臨時(shí)節(jié)

41、點(diǎn)集合中的節(jié)點(diǎn)數(shù)為．即第次迭代需對(duì)個(gè)節(jié)點(diǎn)進(jìn)行處理，因此其所需的處理數(shù)為：</p><p>　　對(duì)n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的時(shí)間復(fù)雜度是．在實(shí)際應(yīng)用當(dāng)中，使用Dijkstra算法查找最短路徑時(shí)耗費(fèi)大量的時(shí)間進(jìn)行數(shù)據(jù)的比較，本文對(duì)Dijkstra算法進(jìn)行分析，通過改變算法實(shí)現(xiàn)減少不必要節(jié)點(diǎn)計(jì)算的時(shí)間，提高算法的效率達(dá)到對(duì)其進(jìn)行優(yōu)化．</p><p>　　第3章 兩點(diǎn)間最短路的改進(jìn)的Dijkstra算法及

42、其MATLAB實(shí)現(xiàn)</p><p>　　3.1 Dijkstra矩陣算法I</p><p>　　Dijkstra矩陣算法I比Dijkstra算法更容易在計(jì)算機(jī)上實(shí)現(xiàn)，它能夠計(jì)算加權(quán)圖中任意兩頂點(diǎn)之間的最短距離．該算法的基本思想是將加權(quán)圖存儲(chǔ)在矩陣?yán)镌摼仃嚳啥x為</p><p>　　其中，為圖的頂點(diǎn)個(gè)數(shù)，為邊的權(quán)重．</p><p>　　將

43、Dijkstra算法的思想影響用于此矩陣的第行，可求出頂點(diǎn)到其他各項(xiàng)點(diǎn)的最短距離，將最短距離仍保存在矩陣的第行，其中=1，2，…，．當(dāng)算法結(jié)束時(shí)，矩陣的元素值就是任意兩頂點(diǎn)之間的最短距離．</p><p>　　3.2 Dijkstra矩陣算法II</p><p>　　Dijkstra矩陣算法I只是簡(jiǎn)單地將Dijkstra算法的思想應(yīng)用到矩陣的每一行，這樣做有很多的重復(fù)計(jì)算，效率不高．為了

44、提高效率，有提出了下面的Dijkstra矩陣算法II，步驟如下：</p><p>　　步驟1 輸入加權(quán)圖，存儲(chǔ)在矩陣?yán)铮?lt;/p><p>　　步驟2 對(duì)矩陣進(jìn)行操作，求任意兩頂點(diǎn)間的最短距離．算法的求解過程；</p><p>　　循環(huán)以1為步長(zhǎng)，從1到,</p><p><b>　　執(zhí)行，，</b></p>

45、;<p><b>　　，</b></p><p><b>　??；</b></p><p><b>　??；</b></p><p><b>　　；</b></p><p>　　循環(huán)．反復(fù)執(zhí)行下列語句，直到；</p><p&g

46、t;　　循環(huán)．以1為步長(zhǎng)，從1到，執(zhí)行；</p><p><b>　　若</b></p><p>　　循環(huán)．以1為步長(zhǎng)，從2到，執(zhí)行</p><p><b>　　若</b></p><p><b>　??；</b></p><p><b>　??；

47、</b></p><p>　　在數(shù)組中去掉一個(gè)元素</p><p><b>　　；</b></p><p><b>　　數(shù)組的長(zhǎng)度減少了1</b></p><p><b>　　若，執(zhí)行</b></p><p><b>　??；<

48、/b></p><p>　　循環(huán)．以1為步長(zhǎng)，從到，執(zhí)行</p><p><b>　?。?lt;/b></p><p>　　步驟3 則算法結(jié)束．</p><p>　　算法II與算法I比較，在步驟循環(huán)的次數(shù)隨著的增加而減少，循環(huán)體的執(zhí)行總次數(shù)會(huì)減少一半． </p><p>　　Dijkstra矩陣

49、算法II的MATLAB實(shí)現(xiàn)見附錄．</p><p>　　3.2.1 簡(jiǎn)單實(shí)例</p><p>　　我們舉下面圖3-1中頂點(diǎn)到其他頂點(diǎn)的最短距離這個(gè)例子．</p><p><b>　　圖3-1 實(shí)例圖</b></p><p>　　用MATLAB求解的主程序如下：</p><p><b>

50、;　　n=12;</b></p><p>　　a=ones(n)+inf;</p><p><b>　　for i=1:n</b></p><p><b>　　a(i,i)=0;</b></p><p><b>　　end</b></p><p&

51、gt;<b>　　a(1,2)=5;</b></p><p><b>　　a(2,3)=8;</b></p><p><b>　　a(2,6)=5;</b></p><p><b>　　a(3,4)=3;</b></p><p>　　a(3,9)=10;&

52、lt;/p><p><b>　　a(4,5)=5;</b></p><p><b>　　a(4,7)=3;</b></p><p><b>　　a(5,6)=2;</b></p><p><b>　　a(7,8)=2;</b></p><p

53、><b>　　a(8,9)=4;</b></p><p>　　a(8,11)=6;</p><p>　　a(9,10)=3;</p><p>　　a(10,11)=5;</p><p>　　a(10,12)=3;</p><p>　　>> dij2_m(a)</p>

54、<p><b>　　計(jì)算結(jié)果如下：</b></p><p>　　圖3-2 運(yùn)行結(jié)果</p><p>　　第4章 基于Dijkstra算法的優(yōu)化算法的研究</p><p>　　4.1 幾種優(yōu)化算法</p><p>　　4.1.1 減小算法中成功搜索的搜索范圍</p><p>　　

55、減小算法中成功搜索的搜索范圍以盡快到達(dá)目標(biāo)節(jié)點(diǎn)．在對(duì)現(xiàn)實(shí)問題中的交通圖初始化為網(wǎng)絡(luò)拓?fù)鋱D時(shí)，雖然終點(diǎn)已知，而源點(diǎn)尚未確定，但依據(jù)常識(shí)離案發(fā)地段最近的派出所應(yīng)為案發(fā)地段所在轄區(qū)派出所，或其周邊派出所，也就是源點(diǎn)的選取范圍可以確定．利用MapObjects2組件提供的MapLayer.SearchExpression （expression）記錄集篩選方法，根據(jù)案發(fā)地段（終點(diǎn)）的不同，動(dòng)態(tài)選取案發(fā)地段所在轄區(qū)及相鄰轄區(qū)的道路圖層及派出所圖層

56、數(shù)據(jù)進(jìn)行最短路徑查詢，從而有效地減少了拓?fù)鋱D中節(jié)點(diǎn)總數(shù)的值．</p><p>　　4.1.2 改進(jìn)算法的存儲(chǔ)結(jié)構(gòu)</p><p>　　在實(shí)際工作中，還要建立起空間數(shù)據(jù)結(jié)構(gòu)．網(wǎng)絡(luò)數(shù)據(jù)結(jié)構(gòu)使用的是“邊和節(jié)點(diǎn)”的數(shù)據(jù)結(jié)構(gòu)，該數(shù)據(jù)結(jié)構(gòu)是建立在圖論的基礎(chǔ)上，節(jié)點(diǎn)可用來定義邊的連接關(guān)系．對(duì)于網(wǎng)絡(luò)數(shù)據(jù)的存儲(chǔ)，傳統(tǒng)的是采用圖論中的鄰接矩陣方法，其存儲(chǔ)量為(為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù))．通常的地理網(wǎng)絡(luò)，盡管節(jié)點(diǎn)很多，

57、但與節(jié)點(diǎn)相關(guān)聯(lián)的節(jié)點(diǎn)數(shù)目并不多，一般都為稀疏圖，將會(huì)浪費(fèi)大量的空間．若采用鄰接表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，其存儲(chǔ)量為(為節(jié)點(diǎn)列表中，同節(jié)點(diǎn)關(guān)聯(lián)的所有邊的數(shù)目)，可節(jié)省大量的存儲(chǔ)空間，尤其是在表示與節(jié)點(diǎn)和邊相關(guān)信息較多的地理網(wǎng)絡(luò)時(shí)，更為有效．但鄰接表卻難以判斷兩節(jié)點(diǎn)之間的關(guān)系，因此本文提出利用．NET框架提供的特殊類Hashtable．NET框架包含特殊類，比如通常所說的集合類用于存儲(chǔ)對(duì)象．與數(shù)組類似，集合類可以把對(duì)象放入容器中，然后再取出．但集合

58、的使用方法與數(shù)組不同，擁有用于插入和刪除項(xiàng)的專用方法．使用Hashtable最大的優(yōu)點(diǎn)就是大大降低數(shù)據(jù)存儲(chǔ)和查找的時(shí)間花費(fèi)．</p><p>　　4.2 本文對(duì)Dijlstra優(yōu)化算法研究</p><p>　　4.2.1 優(yōu)化目標(biāo)</p><p>　　Dijkstra算法用來求解圖上從任一節(jié)點(diǎn)(源點(diǎn))到其余各節(jié)點(diǎn)的最短路徑．其時(shí)間復(fù)雜度為；采用鄰接矩陣存儲(chǔ)網(wǎng)絡(luò)拓

59、撲結(jié)構(gòu)，需要的存儲(chǔ)空間，隨著節(jié)點(diǎn)數(shù)的增大，其計(jì)算效率和存儲(chǔ)效率越低．針對(duì)此問題，提出了Dijkstra算法的改進(jìn)，本文在對(duì)傳統(tǒng)Dijkstra算法分析的基礎(chǔ)上，對(duì)其進(jìn)行了優(yōu)化，優(yōu)化算法只對(duì)最短路徑上節(jié)點(diǎn)的鄰居做處理，而不涉及到其他節(jié)點(diǎn)．</p><p>　　4.2.2 優(yōu)化思路</p><p>　　Dijkstra算法基本方法：設(shè)是從源點(diǎn)s到節(jié)點(diǎn)j的最短路徑長(zhǎng)度；是從到的最短路徑中點(diǎn)的前

60、一節(jié)點(diǎn)．是標(biāo)識(shí)集合；是未標(biāo)識(shí)集合；是節(jié)點(diǎn)集合．是節(jié)點(diǎn)到節(jié)點(diǎn)的距離（與直接相連，否則）．算法步驟如下：</p><p>　　Step0：；；（，與直接相連）或(，與不直接相連)．</p><p>　　Step1：在中找到節(jié)點(diǎn)，使到的距離最小，并將劃歸到（可從與直接相連的中考慮）</p><p>　　若= min ，與直接相連，則將劃歸到中，即，</p>

61、<p><b>　??；；．</b></p><p>　　Step2：修改中節(jié)點(diǎn)的值：；若值改變，則．；.</p><p>　　Step3：選定所有的最小值，并將其劃歸到中：</p><p>　?。?；；若,所有節(jié)點(diǎn)已標(biāo)識(shí)，</p><p>　　則算法終止，否則，轉(zhuǎn)入Step2．</p><p

62、>　　通過分析傳統(tǒng)Dijkstra算法的基本思路，傳統(tǒng)Dijkstra算法存在如下兩點(diǎn)不足：</p><p>　?。?）當(dāng)從未標(biāo)記節(jié)點(diǎn)集合T中選定一個(gè)節(jié)點(diǎn)作為轉(zhuǎn)接點(diǎn)后時(shí)，需掃描未標(biāo)記節(jié)點(diǎn)集合中的節(jié)點(diǎn)并更新其值，而未標(biāo)記節(jié)點(diǎn)集合中往往包含大量與轉(zhuǎn)接節(jié)點(diǎn)不直接相連的節(jié)點(diǎn)（即）；</p><p>　?。?）在未標(biāo)記節(jié)點(diǎn)集合中選擇一個(gè)值最小的節(jié)點(diǎn)作為下一個(gè)轉(zhuǎn)接節(jié)點(diǎn)，然而下一個(gè)轉(zhuǎn)接節(jié)點(diǎn)往往是與

63、標(biāo)記節(jié)點(diǎn)集合中的節(jié)點(diǎn)直接相連的．</p><p>　　4.2.3 問題描述</p><p>　　基于上述兩點(diǎn)不足，對(duì)傳統(tǒng)Dijkstra算法進(jìn)行優(yōu)化，算法優(yōu)化思路為：首先從源點(diǎn)s的鄰居集合集合（與直接相連的節(jié)點(diǎn)集合）中選擇距離最小的鄰居節(jié)點(diǎn)作為轉(zhuǎn)接點(diǎn)，同時(shí)將劃歸到標(biāo)識(shí)集合（初始時(shí)，為{}）．然后對(duì)鄰居集合與標(biāo)識(shí)集合的差集中節(jié)點(diǎn)的值進(jìn)行更新，從標(biāo)識(shí)集合中所有節(jié)點(diǎn)的鄰居集合的并集與標(biāo)識(shí)集合的

64、差集（，）中選擇一個(gè)值最小的節(jié)點(diǎn)作為下一個(gè)轉(zhuǎn)接點(diǎn)，并劃歸到標(biāo)識(shí)集合中．重復(fù)上述過程，直到所有的節(jié)點(diǎn)都被標(biāo)識(shí)過，即，算法結(jié)束．</p><p>　　設(shè)為節(jié)點(diǎn)的鄰居集合；為標(biāo)識(shí)集合；是從源點(diǎn)到節(jié)點(diǎn)的最短路徑長(zhǎng)度；是從到的最短路徑中點(diǎn)的前一節(jié)點(diǎn)；是節(jié)點(diǎn)到節(jié)點(diǎn)的距離．算法步驟如下：</p><p>　　Step0：初始化；；否則；．</p><p>　　Step1：若，則．

65、．</p><p>　　Step2：修改中的值：；若值改變，則，．</p><p>　　Step3：選定中的最小值，并將其劃歸到中：；；若；節(jié)點(diǎn)已標(biāo)識(shí)，則算法終止，否則，轉(zhuǎn)到Step2．</p><p>　　圖4-1為帶權(quán)值的無向圖，對(duì)分別用Dijkstra算法和優(yōu)化了的Dijkstra算法進(jìn)行求解，則可得從到其余各節(jié)點(diǎn)的最短路徑．</p><p

66、>　　圖4-1 帶權(quán)值的無向圖</p><p>　　經(jīng)典Dijkstra算法求解過程：</p><p>　　Step0：初始化，，；</p><p>　　Step1：，，，；</p><p><b>　　Step2：</b></p><p><b>　　，</b>&l

67、t;/p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　?。?-1）</b></p><p><b>　　（4-2）</b></p><p><b>　　，</b>

68、;</p><p><b>　　,；</b></p><p><b>　　Step3：</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　?。?-3）<

69、/b></p><p><b>　?。?-4）</b></p><p><b>　　，</b></p><p><b>　　，；</b></p><p><b>　　Step4：</b></p><p><b>　　

70、，</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　若為</b></p><p><b>　　，</b></p><p><b>　　，；&l

71、t;/b></p><p><b>　　Step5：</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　min== 4，</b></p><p><b&g

72、t;　　，；</b></p><p><b>　　Step6：</b></p><p><b>　?。?lt;/b></p><p>　　至此，算法終止．結(jié)果為，，，，，．</p><p>　　優(yōu)化Dijkstra算法求解過程：</p><p>　　表4-1 優(yōu)化的D

73、ijkstra算法求解v1到其他各節(jié)點(diǎn)最短路徑的過程</p><p>　　Step0：初始化，與直接相連點(diǎn)有,,,，；</p><p><b>　　Step1：2,，</b></p><p><b>　　，，；</b></p><p><b>　　Step2：</b></

74、p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　min，</b></p><p><b>　　，，，</b></

75、p><p><b>　　Step3：</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　min，</b></p><p><b>　　，，；</b>

76、</p><p><b>　　Step4：</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　，</b></p><p><b>　　若為</b>

77、;</p><p><b>　　4，</b></p><p><b>　　，，，</b></p><p><b>　??；</b></p><p><b>　　Step5：</b></p><p><b>　　4;54，&l

78、t;/b></p><p><b>　　4，</b></p><p><b>　　，，， </b></p><p><b>　??；</b></p><p><b>　　Step6：)</b></p><p><b>

79、　?。?lt;/b></p><p>　　至此，所有節(jié)點(diǎn)已標(biāo)識(shí)，則算法終止．最終結(jié)果為，，，，，．</p><p>　　4.2.4 算法特點(diǎn)</p><p>　　傳統(tǒng)Dijkstra算法基于廣度優(yōu)先的搜索策略，從指定節(jié)點(diǎn)出發(fā)，通過權(quán)值迭代遍歷所有其他節(jié)點(diǎn)后，最后得到從指定節(jié)點(diǎn)到其他各節(jié)點(diǎn)的最短路徑樹．它采用線性數(shù)組結(jié)構(gòu)存儲(chǔ)其關(guān)聯(lián)矩陣，在提取最短路徑節(jié)點(diǎn)時(shí)需要

80、訪問所有的未標(biāo)記節(jié)點(diǎn)，算法的運(yùn)行時(shí)間為．</p><p>　　本文提出的優(yōu)化算法在更新最短路徑值與選擇最短路徑值最小的節(jié)點(diǎn)時(shí)，僅僅涉及到節(jié)點(diǎn)的鄰居集合及已標(biāo)識(shí)集合中所有節(jié)點(diǎn)的鄰居集合與已標(biāo)識(shí)集合的差集，其運(yùn)行時(shí)間取決于轉(zhuǎn)接點(diǎn)的鄰居集合的元素?cái)?shù)量多少（而該數(shù)量值往往小于未標(biāo)識(shí)集合中的元素個(gè)數(shù)）．優(yōu)化算法空間復(fù)雜度為，其中是常量，為結(jié)點(diǎn)對(duì)象所占用的空間．另外，根據(jù)圖中頂點(diǎn)和邊的個(gè)數(shù)，可以求出頂點(diǎn)的平均出度（為邊數(shù)，為

81、頂點(diǎn)數(shù)），一般在GIS的網(wǎng)絡(luò)圖中，，由于Step2、Step3都是搜索與（=l，2，3,…，）相鄰的結(jié)點(diǎn)操作，時(shí)間復(fù)雜度均為；Step3的時(shí)間復(fù)雜度為，即；Step5的時(shí)間復(fù)雜度為．因此，算法的時(shí)間復(fù)雜度為．</p><p>　　4.3 優(yōu)化和改進(jìn)的結(jié)論</p><p>　　由圖4-1對(duì)帶權(quán)值的無向圖的求解可以看出，優(yōu)化了的Dijkstra算法在Step2和Step3中較經(jīng)典的Dijks

82、tra算法減少了步驟（4-1）（4-2）（4-3）（4-4），減少了計(jì)算次數(shù)，提高了搜索速度．當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖具有的節(jié)點(diǎn)數(shù)，較大且其關(guān)聯(lián)矩陣為一個(gè)稀疏矩陣時(shí)，相對(duì)傳統(tǒng)Dijkstra算法，優(yōu)化算法大大減少了計(jì)算次數(shù)與比較次數(shù)，在一定程度上提高了運(yùn)算速度．在分析傳統(tǒng)Dijkstra算法的基礎(chǔ)上，針對(duì)傳統(tǒng)Dijkstra算法存在的兩點(diǎn)不足之處，對(duì)其進(jìn)行了優(yōu)化處理．當(dāng)網(wǎng)絡(luò)的規(guī)模較大及其關(guān)聯(lián)矩陣為一個(gè)稀疏矩陣時(shí)，本文提出的優(yōu)化算法，與傳統(tǒng)Dij

83、kstra算法相比，能大大減少了計(jì)算次數(shù)及比較次數(shù)，提高了運(yùn)算效率．</p><p>　　第5章 Dijkstra算法在物流上的應(yīng)用</p><p>　　物流成為一項(xiàng)產(chǎn)業(yè)的歷史并不久遠(yuǎn)，最早是起源于二戰(zhàn)中美軍建立的后勤理論原型，當(dāng)時(shí)的后勤是指將戰(zhàn)時(shí)物資生產(chǎn)、采購(gòu)、運(yùn)輸和配給等活動(dòng)作為整體進(jìn)行統(tǒng)籌安排，以達(dá)到使戰(zhàn)略物資補(bǔ)給費(fèi)用最低，速度最快，效率更高的目的，后來后勤體系逐漸被經(jīng)濟(jì)領(lǐng)域采用，

84、形成現(xiàn)代物流系統(tǒng)．尤其在科學(xué)技術(shù)突飛猛進(jìn)，經(jīng)濟(jì)全球化迅速發(fā)展的今天，物流產(chǎn)業(yè)已經(jīng)形成了龐大的規(guī)模和網(wǎng)絡(luò)，并成為社會(huì)發(fā)展的基礎(chǔ)產(chǎn)業(yè)和經(jīng)濟(jì)推動(dòng)力．</p><p>　　物流服務(wù)已經(jīng)融入到社會(huì)經(jīng)濟(jì)生活的各個(gè)角落，一方面，企業(yè)與企業(yè)之間的不可能孤立存在，多數(shù)情況是相互依存相互合作并形成一條完整的產(chǎn)業(yè)鏈條，企業(yè)與企業(yè)的合作就會(huì)產(chǎn)生大量的物資運(yùn)輸和交換需求，這就需要高效有力的物流紐帶將之連接起來．另一方面，隨著電子商務(wù)產(chǎn)業(yè)的

85、發(fā)展，面對(duì)小宗單一客戶的服務(wù)需求呈爆炸式增長(zhǎng)，物流領(lǐng)域的效率直接影響到電子商務(wù)產(chǎn)業(yè)的效益．</p><p>　　然而物流產(chǎn)業(yè)的發(fā)展也面臨著很嚴(yán)重的供求矛盾和產(chǎn)業(yè)發(fā)展瓶頸以及競(jìng)爭(zhēng)壓力．面對(duì)飛速增長(zhǎng)的服務(wù)需求，物流產(chǎn)業(yè)的基礎(chǔ)設(shè)施和物流能力難以消化，服務(wù)訂單的堆積也導(dǎo)致了物流效率的低下．這就要求物流企業(yè)從自身上進(jìn)行硬件設(shè)施升級(jí)和管理方法上的創(chuàng)新．由于硬件升級(jí)上的成本投入巨大，以及回報(bào)周期的長(zhǎng)效性，很難再短期內(nèi)提高企業(yè)的

86、競(jìng)爭(zhēng)力，越來越多的物流企業(yè)將目光投在了優(yōu)化配送網(wǎng)絡(luò)，提升管理水平方面．同等基礎(chǔ)條件下，一個(gè)企業(yè)的配送網(wǎng)絡(luò)是否達(dá)到最優(yōu)，資源使用是否達(dá)到了最大效率，直接關(guān)系到物流服務(wù)效率的高低以及企業(yè)競(jìng)爭(zhēng)力的大?。畬?duì)于物流企業(yè)來說，物流網(wǎng)絡(luò)的范圍和質(zhì)量直接關(guān)系到其配送能力的高低和自身服務(wù)質(zhì)量的好壞，進(jìn)而直接影響到企業(yè)核心競(jìng)爭(zhēng)力的大?。蚨瑸榱颂嵘锪髌髽I(yè)的核心競(jìng)爭(zhēng)力，我們需要研究出更為有效的管理和分配方法，充分有效利用現(xiàn)有的人力物力時(shí)間等資源，達(dá)到最優(yōu)

87、化配送．為了科學(xué)有效的實(shí)現(xiàn)這些目的，就需要引入新的技術(shù)來解決問題．計(jì)算機(jī)技術(shù)的發(fā)展為各行各業(yè)都帶來了顯著的效益，在信息化生產(chǎn)的今天，物流行業(yè)也急需一種能夠全局統(tǒng)籌監(jiān)控，自動(dòng)進(jìn)行資源調(diào)配的計(jì)算機(jī)系統(tǒng)來對(duì)運(yùn)營(yíng)網(wǎng)絡(luò)進(jìn)行分析控制，以實(shí)現(xiàn)良性運(yùn)營(yíng)．首先闡述了物流行業(yè)</p><p>　　5.1 最優(yōu)配送路線選擇問題</p><p>　　在物流配送領(lǐng)域中，最重要的任務(wù)就是如何將貨物用最高效，快捷的方

88、式送達(dá)目的地．不同的目的地之間由于客觀條件的不同，運(yùn)送成本也會(huì)不同．將不同節(jié)點(diǎn)之間的各項(xiàng)信息進(jìn)行匯總可以得到一個(gè)有權(quán)無向圖，該圖可以全面的反映出整個(gè)物流網(wǎng)絡(luò)中各個(gè)節(jié)點(diǎn)間的詳細(xì)情況．通過對(duì)整個(gè)物流網(wǎng)絡(luò)進(jìn)行分析，我們就可以權(quán)衡確定選擇何種配送方式，何種配送路線等．本文中我們采用計(jì)算機(jī)領(lǐng)域中對(duì)圖最短路徑分析的方法——Dijkstra算法對(duì)最優(yōu)配送路線選擇問題進(jìn)行分析．</p><p>　　我們知道，在物流配送環(huán)節(jié)中首先

89、要形成一條既有的物流網(wǎng)絡(luò)，能夠?qū)⑷我馀渌凸?jié)點(diǎn)發(fā)出的貨物高效的送達(dá)網(wǎng)絡(luò)中其他節(jié)點(diǎn)．其中節(jié)點(diǎn)間的交通長(zhǎng)度是客觀成本，會(huì)直接影響到相應(yīng)的人力成本和油耗成本以及損耗成本．我們?cè)O(shè)兩個(gè)物流節(jié)點(diǎn)之間的交通長(zhǎng)度為，也就是基礎(chǔ)成本．在此基礎(chǔ)上會(huì)產(chǎn)生附加成本．</p><p>　　進(jìn)一步，我們會(huì)討論附加成本與基礎(chǔ)成本之間的關(guān)系問題．進(jìn)而確定每?jī)蓚€(gè)節(jié)點(diǎn)間最終的權(quán)值．我們知道，由于不同城市的經(jīng)濟(jì)發(fā)展水平和地理因素等會(huì)導(dǎo)致他們之間的人力成

90、本和油耗成本等因素的不同，有些城市經(jīng)濟(jì)水平比較發(fā)達(dá)，相應(yīng)的其人力成本和油耗成本等就會(huì)增加，而有些城市之間的交通路況不好，就會(huì)響應(yīng)的增加油耗成本和損耗成本．故而我們需要對(duì)不同城市之間的具體情況進(jìn)行深入調(diào)查才，采用綜合考慮的方法來確定其最終費(fèi)用．</p><p>　　此外我們發(fā)現(xiàn)，在物流運(yùn)輸過程中，由于兩地之間的人力成本不同會(huì)導(dǎo)致雙向運(yùn)輸中的成本統(tǒng)計(jì)出現(xiàn)不同，因此，在本文中，我們僅取折中的辦法，統(tǒng)計(jì)兩地之間雙向運(yùn)輸?shù)?/p>

91、平均成本．我們?cè)O(shè)兩地的人力成本分別為 、，我們根據(jù)經(jīng)驗(yàn)公式可以得出一般運(yùn)輸領(lǐng)域中平均人力成本計(jì)算公式：</p><p>　　假設(shè)針對(duì)附加成本方面，我們只考慮運(yùn)輸距離，油耗，和人力成本三個(gè)基本因素．我們?cè)O(shè)運(yùn)輸距離為 ，兩個(gè)配送節(jié)點(diǎn)的油耗成本分別為 、,兩個(gè)配送節(jié)點(diǎn)的人力成本分別為、，表示貨物損耗成本，表示實(shí)時(shí)油價(jià)，，，表示基礎(chǔ)成本影響因子，他們分別表示各項(xiàng)附加成本受到基本成本的影響程度．我們可以得到最終成本的計(jì)算公

92、式為：</p><p><b>　　，，</b></p><p>　　根據(jù)不同影響因素及其影響因子我們可以得到兩個(gè)配送節(jié)點(diǎn)之間相應(yīng)的油耗成本，人力成本以及可能的損耗成本，進(jìn)而得到最終的綜合成本，也就是兩個(gè)配送節(jié)點(diǎn)之間的綜合權(quán)值．我們改進(jìn)的 Dijkstra 算法的流程圖如圖 5-1 所示：</p><p>　　圖5-1 改進(jìn)的Dijkstra

93、算法流程圖</p><p>　　5.2 改進(jìn)的Dijkstra算法在最優(yōu)配送路線確定中的實(shí)例</p><p>　　為了更好的說明問題，我們選取一個(gè)如圖5-2 所示的簡(jiǎn)單聯(lián)通區(qū)域?yàn)槔M(jìn)行分析和說明具體的方案設(shè)計(jì)．我們可以看到途中一共有七個(gè)配送節(jié)點(diǎn)，節(jié)點(diǎn)之間的路線權(quán)值表明的是兩個(gè)節(jié)點(diǎn)的運(yùn)輸距離．</p><p>　　圖5-2 路線無向有權(quán)示意圖</p>

94、<p>　　人力成本和油耗成本列表如表5-1所示，單位為千元/公里·噸</p><p>　　表5-1 人力成本表</p><p>　　各個(gè)節(jié)點(diǎn)間的聯(lián)通情況以及運(yùn)輸距離情況也可以列出表格如表 5-2 所示．</p><p>　　表5-2 運(yùn)輸距離表</p><p>　　我們根據(jù)以上公式對(duì)本例中的配送節(jié)點(diǎn)間綜合代價(jià)進(jìn)行

95、計(jì)算得到了各個(gè)配送節(jié)點(diǎn)間的綜合權(quán)值如圖5-3 所示：</p><p>　　圖5-3 節(jié)點(diǎn)間的綜合權(quán)值 </p><p>　　5.2.1 路徑優(yōu)化結(jié)果</p><p>　　繼而我們根據(jù)上述數(shù)據(jù)，應(yīng)用 Dijkstra 算法對(duì)其進(jìn)行最優(yōu)配送路徑確定，我們確定選定的最終結(jié)果如表5-3 所示：</p><p>　　表5-3 路徑選擇圖<

96、/p><p>　　這樣，我們就確定了從任意一個(gè)節(jié)點(diǎn)出發(fā)，配送到區(qū)域內(nèi)其他節(jié)點(diǎn)應(yīng)選擇的路線，以及相應(yīng)的成本分析，從而可以根據(jù)這些信息調(diào)配相應(yīng)的人力和車輛等資源，進(jìn)行配送安排．</p><p><b>　　結(jié) 論</b></p><p>　　本文基于Dijkstra算法，針對(duì)Dijkstra算法在實(shí)際應(yīng)用中搜索速度慢，搜索效率低，時(shí)間花費(fèi)多的的缺

97、陷，對(duì)其進(jìn)行了優(yōu)化．優(yōu)化算法只對(duì)最短路徑上節(jié)點(diǎn)的鄰居做處理，而不涉及到其他節(jié)點(diǎn)，每個(gè)搜索過程不必全部遍歷或者較少地遍歷臨時(shí)標(biāo)記點(diǎn)，既縮小了搜索范圍，又保證了遍歷搜索的搜索成功率，從而提高了搜索效率，節(jié)省了時(shí)間，適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓阅芊€(wěn)定．但針對(duì)實(shí)際問題，例如物流問題，路徑最短并不一定是是花銷最小，相對(duì)于這一Dijkstra算法或改進(jìn)算法，并不是特別理想，只能在一定程度或者范圍內(nèi)起到優(yōu)化和改進(jìn)的目的．即使如此，Dijkstra算法還是在

98、路徑問題上做出了應(yīng)有的指引作用，為以后的進(jìn)一步研究提供了知識(shí)基礎(chǔ)．</p><p><b>　　參考文獻(xiàn)</b></p><p>　　[1] 王峰．Dijkstra及基于Dijkstra的前N條最短路徑算法在智能交通系統(tǒng)中的應(yīng)</p><p>　　用[J]．計(jì)算機(jī)應(yīng)用研究，2006，2（2）：17-25．</p><p>

99、;　　[2] 李秉智，李智．一種新的基于Dijkstra算法的QoS組播樹啟發(fā)式算法[J]．重</p><p>　　慶郵電學(xué)院學(xué)報(bào)(自然科學(xué)版)，2006，3（4）：10-13．</p><p>　　[3] 紀(jì)江濤．基于傳感器網(wǎng)絡(luò)的智能交通系統(tǒng)模型應(yīng)用研究[M]．山東科技大學(xué)</p><p>　　出版社，2010，1（4）：6-9．</p><p

100、>　　[4] 徐寅峰,劉明,蘇兵．不完全信息下交通網(wǎng)絡(luò)最短路徑的求解方法[J]．西安交</p><p>　　通大學(xué)學(xué)報(bào)，2005，1（1）：3-9．</p><p>　　[5] 張杰，周碩．運(yùn)籌學(xué)模型[M]．東北大學(xué)出版社，2005．</p><p>　　[6] 李擎，宋頂立，張雙江，李哲，劉建光，王志良．兩種改進(jìn)的最優(yōu)路徑規(guī)算</p><

101、p>　　法[J]．北京科技大學(xué)學(xué)報(bào)，2005，30（2）：2-4．</p><p>　　[7] Salehfar H，Zhao R．A neural network pre - estimation filter for bad data detection and identification in power system state estimation [J]．Electric system pow

102、er reserch，1995，10（34）：15-34．</p><p>　　[8] 羅理，王鋒.基于Dijkstra的最短路徑改進(jìn)算法[J]．湖北汽車工業(yè)學(xué)報(bào)，2007，</p><p>　　14（7）：12-19．</p><p>　　[9] 程理民等．運(yùn)籌學(xué)模型與方法教程[M]．北京：清華大學(xué)出版社，2002．</p><p>　　[

103、10] 胡運(yùn)權(quán)譯．目標(biāo)規(guī)劃及其應(yīng)用[M]．哈爾濱：哈爾濱工業(yè)大學(xué)出版社，1988．</p><p>　　[11] 許英．關(guān)于圖譜的若干研究[M]．新疆大學(xué)出版社，2010．</p><p>　　[12] 左為平，劉云芳．有向圖中路徑矩陣的實(shí)現(xiàn)及其算法研究[J]．洛陽(yáng)師范學(xué)</p><p>　　院學(xué)報(bào)，2004，5（2）：2-3．</p><p&g

104、t;<b>　　致 謝</b></p><p>　　本文工作是在徐X老師的耐心指導(dǎo)下完成的．在近幾個(gè)月來的努力工作下這次畢業(yè)論文即將結(jié)束，在次論文完成之際，向尊敬的論文導(dǎo)師表達(dá)衷心的感謝！</p><p>　　再次，我還要對(duì)再次期間給我?guī)椭睦蠋熀屯瑢W(xué)們說一聲謝謝，感謝他們?cè)谖疑硖幚щy時(shí)給我?guī)椭完P(guān)懷，讓我能在這一期間一直保持樂觀的態(tài)度，使我最后幾個(gè)月的大學(xué)充滿

105、了樂趣．同時(shí)也感謝在大學(xué)期間一直幫助和關(guān)心我的朋友，老師和同學(xué)，他們的理解和支持是我走到今天的動(dòng)力，而我也將用我的努力報(bào)答你們對(duì)我的鼓勵(lì)．</p><p>　　最后要感謝的是我的父母，他們?yōu)槲夷軌蝽樌耐瓿僧厴I(yè)論文提供了巨大的支持和鼓勵(lì)．在未來的日子里，我會(huì)更加努力的學(xué)習(xí)和工作，不辜負(fù)父母對(duì)我的期望！力所能及地回報(bào)他們，讓明天的陽(yáng)光更加燦爛．</p><p><b>　　2013

106、年6月</b></p><p><b>　　附 錄</b></p><p>　　改進(jìn)Dijkstra算法II的MATLAB程序?qū)崿F(xiàn)如下：</p><p>　　function a=dij2_m(a)</p><p>　　n=length(a);</p><p><b>

107、　　for i=2:n</b></p><p>　　for j=1:(i-1)</p><p>　　a(i,j)=a(j,i);</p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　for k=1:(n-1)

108、</p><p>　　b=[1:(k-1),(k+1):n];</p><p>　　kk=length(b);</p><p><b>　　a_id=k;</b></p><p>　　b1=[(k+1):n];</p><p>　　kk1=length(b1);</p><p&

109、gt;　　while kk>0</p><p>　　for j=1:kk1</p><p>　　te=a(k,a_id)+a(a_id,b1(j));</p><p>　　if te<a(k,bi(j))</p><p>　　a(k,bi(j))=te;</p><p><b>　　end<

110、/b></p><p><b>　　end</b></p><p><b>　　miid=1;</b></p><p>　　for j=2:kk</p><p>　　if a(k,b(j))<a(k,b(miid))</p><p><b>　　miid

111、=j;</b></p><p><b>　　end</b></p><p><b>　　end</b></p><p>　　a_id=b(miid);</p><p>　　b=[b(1:(miid1-1)),b((miid1+1):kk];</p><p>　　k

112、k=length(b);</p><p><b>　　if a_id>k</b></p><p>　　miid1=find(b1==a_id);</p><p>　　b1=[b1(1:(miid1-1))b1((miid1+1):kk1)];</p><p>　　kk1=length(b1);</p>

113、<p><b>　　end</b></p><p><b>　　end</b></p><p>　　for j=(k+1):n</p><p>　　a(j,k)=a(k,j);</p><p><b>　　end</b></p><p>&l