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

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

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

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

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

5、法的速度．本文通過實驗和實際應(yīng)用對改進(jìn)后的算法進(jìn)行了簡單的驗證．之后將一些算法的改進(jìn)和實際例子相結(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 國內(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)缺點8</p><p>　　第3章 兩點間最短路的改進(jìn)的Dijkstra算法及其MATLAB實現(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)算法的存儲結(jié)構(gòu)13</p><p>　　4.2 本文對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 算法特點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)配送路線確定中的實例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>　　最短路徑算法是計算機科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點，其算法有很多種，其中傳統(tǒng)的Dijks

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

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

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

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

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

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

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

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

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

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

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

30、一個點．從所有未標(biāo)記的結(jié)點中，選取中最小的一個：</p><p>　　，（所有未標(biāo)記的點），點就被選為最短路徑中的一點，并設(shè)為已標(biāo)記的．</p><p>　　（4）找到點的前一點．從已標(biāo)記的點中找到直接連接到點的點，作為前一點，設(shè)置：=．</p><p>　?。?）標(biāo)記點．如果所有點已標(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é)點到4節(jié)點的最短路徑</p><p><b>　　2.2.2 應(yīng)用</b><

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

49、算法II的MATLAB實現(xiàn)見附錄．</p><p>　　3.2.1 簡單實例</p><p>　　我們舉下面圖3-1中頂點到其他頂點的最短距離這個例子．</p><p><b>　　圖3-1 實例圖</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>　　計算結(jié)果如下：</b></p><p>　　圖3-2 運行結(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é)點．在對現(xiàn)實問題中的交通圖初始化為網(wǎng)絡(luò)拓?fù)鋱D時，雖然終點已知，而源點尚未確定，但依據(jù)常識離案發(fā)地段最近的派出所應(yīng)為案發(fā)地段所在轄區(qū)派出所，或其周邊派出所，也就是源點的選取范圍可以確定．利用MapObjects2組件提供的MapLayer.SearchExpression （expression）記錄集篩選方法，根據(jù)案發(fā)地段（終點）的不同，動態(tài)選取案發(fā)地段所在轄區(qū)及相鄰轄區(qū)的道路圖層及派出所圖層

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

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

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

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

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

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

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

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

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

65、．</p><p>　　Step2：修改中的值：；若值改變，則，．</p><p>　　Step3：選定中的最小值，并將其劃歸到中：；；若；節(jié)點已標(biāo)識，則算法終止，否則，轉(zhuǎn)到Step2．</p><p>　　圖4-1為帶權(quán)值的無向圖，對分別用Dijkstra算法和優(yōu)化了的Dijkstra算法進(jìn)行求解，則可得從到其余各節(jié)點的最短路徑．</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>　?。?-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>　　（4-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é)點最短路徑的過程</p><p>　　Step0：初始化，與直接相連點有,,,，；</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>　?。?lt;/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é)點已標(biāo)識，則算法終止．最終結(jié)果為，，，，，．</p><p>　　4.2.4 算法特點</p><p>　　傳統(tǒng)Dijkstra算法基于廣度優(yōu)先的搜索策略，從指定節(jié)點出發(fā)，通過權(quán)值迭代遍歷所有其他節(jié)點后，最后得到從指定節(jié)點到其他各節(jié)點的最短路徑樹．它采用線性數(shù)組結(jié)構(gòu)存儲其關(guān)聯(lián)矩陣，在提取最短路徑節(jié)點時需要

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

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

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

83、kstra算法相比，能大大減少了計算次數(shù)及比較次數(shù)，提高了運算效率．</p><p>　　第5章 Dijkstra算法在物流上的應(yīng)用</p><p>　　物流成為一項產(chǎn)業(yè)的歷史并不久遠(yuǎn)，最早是起源于二戰(zhàn)中美軍建立的后勤理論原型，當(dāng)時的后勤是指將戰(zhàn)時物資生產(chǎn)、采購、運輸和配給等活動作為整體進(jìn)行統(tǒng)籌安排，以達(dá)到使戰(zhàn)略物資補給費用最低，速度最快，效率更高的目的，后來后勤體系逐漸被經(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ò)，并成為社會發(fā)展的基礎(chǔ)產(chǎn)業(yè)和經(jīng)濟(jì)推動力．</p><p>　　物流服務(wù)已經(jīng)融入到社會經(jīng)濟(jì)生活的各個角落，一方面，企業(yè)與企業(yè)之間的不可能孤立存在，多數(shù)情況是相互依存相互合作并形成一條完整的產(chǎn)業(yè)鏈條，企業(yè)與企業(yè)的合作就會產(chǎn)生大量的物資運輸和交換需求，這就需要高效有力的物流紐帶將之連接起來．另一方面，隨著電子商務(wù)產(chǎn)業(yè)的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

99、;　　[2] 李秉智，李智．一種新的基于Dijkstra算法的QoS組播樹啟發(fā)式算法[J]．重</p><p>　　慶郵電學(xué)院學(xué)報(自然科學(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é)報，2005，1（1）：3-9．</p><p>　　[5] 張杰，周碩．運籌學(xué)模型[M]．東北大學(xué)出版社，2005．</p><p>　　[6] 李擎，宋頂立，張雙江，李哲，劉建光，王志良．兩種改進(jìn)的最優(yōu)路徑規(guī)算</p><

101、p>　　法[J]．北京科技大學(xué)學(xué)報，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é)報，2007，</p><p>　　14（7）：12-19．</p><p>　　[9] 程理民等．運籌學(xué)模型與方法教程[M]．北京：清華大學(xué)出版社，2002．</p><p>　　[

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

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

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