Dijkstra最短路徑算法的優(yōu)化和改進(jìn)

1、本科畢業(yè)設(shè)計(jì)（論文）Dijkstra最短路徑算法的優(yōu)化和改進(jìn)隨著計(jì)算機(jī)和地理信息科學(xué)的發(fā)展，GIS （地理信息系統(tǒng)）的應(yīng)用領(lǐng)域越來 越廣.最短路徑分析是GIS地理網(wǎng)絡(luò)分析功能中的一個(gè)關(guān)鍵性的問題.計(jì)算最 短路徑的經(jīng)典算法之一就是Dijkstra算法，許多工程中解決最短路徑問題都是采 用這種算法.然而，傳統(tǒng)的Dijkstia算法在求解節(jié)點(diǎn)間最短路徑時(shí)，對(duì)已標(biāo)識(shí)節(jié) 點(diǎn)外的大量節(jié)點(diǎn)進(jìn)行了計(jì)算，從而影響了算法的速度.該算法的主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為 止.Dijkstra算法是很有代表性的最短路徑算法，在很多專業(yè)課程中都作為基本 內(nèi)容有詳細(xì)的介紹.本文在傳統(tǒng)Dijkstia

2、算法的基礎(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)算法大幅減少，提高了算法的速度.本文 通過實(shí)驗(yàn)和實(shí)際應(yīng)用對(duì)改進(jìn)后的算法進(jìn)行了簡(jiǎn)單的驗(yàn)證.之后將一些算法的改進(jìn) 和實(shí)際例子相結(jié)合，這樣就能使文章中算法的優(yōu)化更為理想.關(guān)鍵詞最短

3、路徑；Dijkstra；優(yōu)化算法-I-AbstractAbstractWith the development of computer and geographic infoimation science, the applications of GIS (Geographic Iiifbimation System) are becoming more and more widely. However, shortest path analysis is the key problem of network analyses, Dijkstra algontlun is a classic

4、antlunetic for the shortest path. It is the academic foundation that many engineenngs were solved in the shortest path is use. When a shortest path between nodes is searched with Dijkstra algontlun, a lot of nodes away from lagged nodes are involved, so that the efficiency of Dijkstra algontlun is l

5、ow.Main features of the algontlun is the starting point as the center outward expansion layers until it extended to the end point. DijkstiHs algoiitlun is veiy repiesentative of the shortest path algoiitlun, in many professional courses m the basic content as desciibed in detail. The proposed algoii

6、tlun updates the shortest path in the value of the minimum value of the shortest path to the node, only the set of neighbors of the node related to the identified set and a neighbor set of all nodes m the identified set with the set difference, its nuuiing time depends transfei the contact elements

7、of the set of neighbors of quantity. Successful search algontlun by reducing the search range and unpioved algontlun storage stnictuie of these two mam lesearch directions to optimize the algoritlmi. Theiefoiejlie number of processed nodes is largely reduced m the optimization algontlun, and efficie

8、ncy of the optimization algoiitlun is unproved. The improved algontlun is proved to be conect and efficient by expeimients and practical application. After some of the algontlun and the combmation of practical examples, so you can make the ailicle more ideal algontlun optimization.Keywords The short

9、est path； Dijkstra； Optimization algontlun-ii -目 錄方. .I TOC o 1-5 h z AbstractIIU. Ill HYPERLINK l bookmark2 o Current Document 第1章緒論1 HYPERLINK l bookmark4 o Current Document 國內(nèi)外最短路徑算法的發(fā)展及其概況1 HYPERLINK l bookmark6 o Current Document 傳統(tǒng)Dijkstra算法仍然存在的一些問題1 HYPERLINK l bookmark8 o Current Document 本

10、文工作2第2章Dijkstra經(jīng)典算法3 HYPERLINK l bookmark10 o Current Document 引言3 HYPERLINK l bookmark12 o Current Document 原理及應(yīng)用3原理3應(yīng)用5 HYPERLINK l bookmark14 o Current Document Dijkstia算法與其他主流算法的比較6 HYPERLINK l bookmark16 o Current Document 搜索速度比較6 HYPERLINK l bookmark18 o Current Document 搜索成功率比較7Dijkstra算法的優(yōu)缺點(diǎn)

11、8 HYPERLINK l bookmark20 o Current Document 第3章兩點(diǎn)間最短路的改進(jìn)的Dijkstra算法及其MATLAB實(shí)現(xiàn)9Dijkstia 矩陣算法 19Dijkstia 矩陣算法 II9 HYPERLINK l bookmark24 o Current Document 第4章基于Dijkstia算法的優(yōu)化算法的研究13 HYPERLINK l bookmark26 o Current Document 幾種優(yōu)化算法13 HYPERLINK l bookmark28 o Current Document 減小算法中成功搜索的搜索范圍13 HYPERLINK

12、l bookmark30 o Current Document 改進(jìn)算法的存儲(chǔ)結(jié)構(gòu)13 HYPERLINK l bookmark32 o Current Document 本文對(duì)Dijlstra優(yōu)化算法研究14 HYPERLINK l bookmark34 o Current Document 優(yōu)化目標(biāo)14 HYPERLINK l bookmark36 o Current Document 優(yōu)化思路14-in- TOC o 1-5 h z HYPERLINK l bookmark38 o Current Document 問題描述15 HYPERLINK l bookmark40 o Curr

13、ent Document 算法特點(diǎn)19 HYPERLINK l bookmark42 o Current Document 優(yōu)化和改進(jìn)的結(jié)論20 HYPERLINK l bookmark44 o Current Document 第5章Dijkstia算法在物流上的應(yīng)用21 HYPERLINK l bookmark46 o Current Document 最優(yōu)配送路線選擇問題22 HYPERLINK l bookmark48 o Current Document 改進(jìn)的Dijkstra算法在最優(yōu)配送路線確定中的實(shí)例24 HYPERLINK l bookmark50 o Current Doc

14、ument 路徑優(yōu)化結(jié)果26結(jié)論28 HYPERLINK l bookmark54 o Current Document 參考文獻(xiàn)29致謝30附錄31-IV -第1章：緒論第1章緒論最短路徑算法是計(jì)算機(jī)科學(xué)與地理信息科學(xué)等領(lǐng)域研究的熱點(diǎn)，其算法有很 多種，其中傳統(tǒng)的Dijkstia算法一般用于計(jì)算一個(gè)源節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最小 代價(jià)路徑，并且能夠適應(yīng)網(wǎng)絡(luò)拓?fù)涞淖兓阅芊€(wěn)定，因而可以在運(yùn)輸路線規(guī)劃 等領(lǐng)域都應(yīng)用廣泛.國內(nèi)外最短路徑算法的發(fā)展及其概況最短路徑在20世紀(jì)初開始受到人們的重視，關(guān)于它的求解方法，當(dāng)時(shí)有很多 科學(xué)家在研究.但給出求解的基本思想的人直到1959年才出現(xiàn)，是一位名叫 Eds

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

16、以Fiank和Muchandani為代表；研究不 同費(fèi)用函數(shù)最短路徑問題，以Loui、Muethy和Saikai為代表；研究時(shí)間獨(dú)立情況 下的路段長(zhǎng)度隨機(jī)變化的最短路徑問題，Hall、LiPmg Fu. L.R.Rilett, Elise和Hani 為代表；研究路段長(zhǎng)度為區(qū)間范圍的最短路徑問題，以Tomas和Rajeev為代表.其 中，第二方面問題的研究得出的結(jié)論是“當(dāng)目標(biāo)是期望最短路徑時(shí)問題轉(zhuǎn)化為將 邊的權(quán)重用期望值表示的最短路徑問題”.傳統(tǒng)Dijkstia算法仍然存在的一些問題原始Dijkstia算法在存儲(chǔ)圖形數(shù)據(jù)和運(yùn)算時(shí)，基于網(wǎng)絡(luò)的權(quán)矩陣，需要根據(jù) 其節(jié)點(diǎn)與距離之間的關(guān)系，形成關(guān)聯(lián)矩陣、

17、鄰接矩陣與距離矩陣，需要定義NxN東北電力大學(xué)本科畢業(yè)論文的數(shù)組來存儲(chǔ)數(shù)據(jù)，其中N為網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)，當(dāng)網(wǎng)絡(luò)的節(jié)點(diǎn)數(shù)較大時(shí)，將占用 大量的計(jì)算機(jī)內(nèi)存.原始Dijkstia算法在運(yùn)行時(shí)一般將網(wǎng)絡(luò)節(jié)點(diǎn)分為未標(biāo)記節(jié)點(diǎn)、臨時(shí)標(biāo)記節(jié)點(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í)行效率.13本文工作隨著社會(huì)的不斷

18、進(jìn)步，最短路徑算法在人們的日常生活顯得越來越重要.每 天開車去上班，應(yīng)該選擇哪條公路才能使自己到公司的費(fèi)用最低、時(shí)間最少，這 是最短路徑的問題；在網(wǎng)絡(luò)路由中，怎樣選擇最優(yōu)的路由路徑，這也是最短路徑 問題；在交通旅游、城市規(guī)劃以及電網(wǎng)架設(shè)中怎樣使其耗費(fèi)的資金最少，這還 是最短路徑問題.由此可見對(duì)最短路徑問題的研究是非常有意義的.第2堂Dijkstia經(jīng)典算法第2章Dijkstra經(jīng)典算法引言Dijkstia算法是典型最短路算法，用于計(jì)算一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的最短 路徑.主要特點(diǎn)是以起始點(diǎn)為中心向外層層擴(kuò)展，直到擴(kuò)展到終點(diǎn)為止.Dijkstra 算法能得出最短路徑的最優(yōu)解，但由于它遍歷計(jì)算的節(jié)點(diǎn)

19、很多，所以效率低，.如 何改進(jìn)這一經(jīng)典算法，成為了實(shí)現(xiàn)圖論中賦權(quán)圖中解決實(shí)際問題的重要課題.原理及應(yīng)用Dijkstia（迪杰斯特拉）算法是典型的單源最短路徑算法，用于計(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é)等等.Dijkstia 一般 的表述通常有兩種方式，一種用永久和臨時(shí)標(biāo)號(hào)方式，一種是用OPEN, CLOSE 表的方式，這里均采用永久和臨時(shí)標(biāo)號(hào)的方式.該算法要求圖中不存在負(fù)權(quán)邊.原理Dijkstia算法是1959年

20、由E. W. Dijkstia提出的圖論中求最短路徑的一個(gè)著名 的算法，使用其可以求得圖中一點(diǎn)到其他各頂點(diǎn)的最短路徑.原始的Dijkstia算 法將網(wǎng)絡(luò)結(jié)點(diǎn)分成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é)束算法.假設(shè)每個(gè)點(diǎn)都有一對(duì)標(biāo)號(hào)（嗎，pj，其中嗎是從起源點(diǎn)s到點(diǎn)，的最短路 徑的長(zhǎng)度（從頂點(diǎn)到其本身的最短路徑是零路（沒有弧的路），其長(zhǎng)度等于零）；東北電力大學(xué)本

21、科畢業(yè)論文P,則是從S到/的最短路徑中/點(diǎn)的前一點(diǎn).求解從起源點(diǎn)i到點(diǎn)J的最短路徑 算法的基本過程如下：(1 )初始化.起源點(diǎn)設(shè)置為:% = 0, p$為空;所有其他點(diǎn):VV. = 8 , Pj = ?； 標(biāo)記起源點(diǎn)S ,記女=S,其他所有點(diǎn)設(shè)為未標(biāo)記的.(2)檢驗(yàn)從所有已標(biāo)記的點(diǎn)k到其直接連接的未標(biāo)記的點(diǎn)j的距離，并設(shè)置:% =11皿帆,叫+dj式中，九是從點(diǎn)k到J的直接連接距離.(3)選取下一個(gè)點(diǎn).從所有未標(biāo)記的結(jié)點(diǎn)中，選取力中最小的一個(gè)i：h; = nuii ,(所有未標(biāo)記的點(diǎn)J ),點(diǎn)，就被選為最短路徑中的一點(diǎn)，并設(shè)為 己標(biāo)記的.(4)找到點(diǎn)i的前一點(diǎn).從已標(biāo)記的點(diǎn)中找到直接連接到點(diǎn)i

22、的點(diǎn)廣，作為 前一點(diǎn)，設(shè)置：z = j*.(5)標(biāo)記點(diǎn)i.如果所有點(diǎn)已標(biāo)記，則算法完全推出，否則，記k=i,轉(zhuǎn)到 (2)再繼續(xù).第2堂 Dijkstra經(jīng)典算法表2-1 0節(jié)點(diǎn)到4節(jié)點(diǎn)的最短路徑循環(huán)紅點(diǎn)集sK。0“3陽力。4初始化0)一01000301001(0,11010603010020,1330105030903(0X3,22010503060403,3,2,440105030602.2.2應(yīng)用給定簡(jiǎn)單定簡(jiǎn)單無向圖G,指定一頂點(diǎn)匕為起點(diǎn)，對(duì)于任意 匕&G且年人 求匕到匕的最短路徑的長(zhǎng)度.例：某單位使用一臺(tái)設(shè)備，在每年年初，企業(yè)部門領(lǐng)導(dǎo)都要決定是購置新設(shè) 備代替原來的舊設(shè)備，還是繼續(xù)使用舊

23、設(shè)備.若購置新設(shè)備，需要支付一定的購 置費(fèi)用；若繼續(xù)使用舊設(shè)備，需支付一定的維修費(fèi)用.設(shè)該種設(shè)備在每年年初的 價(jià)格（萬元）見表2-2使用的不同時(shí)間（年）的設(shè)備所需要的維修費(fèi)用（萬元） 見表2-3.問如何制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使總費(fèi)用最少.表2-2價(jià)格表第i年12345價(jià)格1112131213表2-3維修費(fèi)用表使用年數(shù)XX1lx22 cx33 x44x5維修費(fèi)用5681118東北電力大學(xué)本科畢業(yè)論文圖2-2賦權(quán)有向網(wǎng)絡(luò)圖用點(diǎn)0表示“第i年年初購進(jìn)一臺(tái)新設(shè)備”這種狀態(tài)，1=1, 2,，5,用匕 表示第五年底的狀態(tài).對(duì)于每個(gè)，=1, 2,，5從匕到匕+；匕各畫一條弧, ?。ㄘ?，V.）表示在

24、第1年年初購進(jìn)一臺(tái)設(shè)備一直使用到第/年年初（即第J 1年 底）.每條弧的權(quán)可按已知的數(shù)據(jù)計(jì)算出來，例如（乂，匕）表示第一年年初 購進(jìn)一臺(tái)新設(shè)備，需支付11萬元，一直使用到第三年年底，需維修費(fèi)（5十6十8） 萬元=19萬元，故其上的權(quán)為30.這樣就可以得到一個(gè)賦權(quán)有向網(wǎng)絡(luò)，如圖2-3所示，所求問題等價(jià)于需找從匕 到匕的最短路問題.用Dijkstta算法求解，最優(yōu)解為（匕，匕，匕），即分別在 第1、4年年初購買一臺(tái)新設(shè)備，總費(fèi)用為53萬元.上述為Dijkstia最基本的求解 路徑的方法.2.3 Dijkstia算法與其他主流算法的比較搜索速度比較對(duì)5張圖分別采用Dijkstia算法、A*算法、遺傳

25、算法進(jìn)行路徑規(guī)劃，他們各 自花費(fèi)的時(shí)間如表2-4所示.第2章 Dijkstra經(jīng)典算法表2K算法速度對(duì)比圖節(jié)點(diǎn)數(shù)搜索速度Dijkstra 算法遺傳算法A*算法1612132442437636215957825127由上表可以看出：當(dāng)?shù)貓D節(jié)點(diǎn)個(gè)數(shù)和弧的條數(shù)比較少時(shí)，三種算法所花費(fèi)的 時(shí)間差不多，當(dāng)節(jié)點(diǎn)個(gè)數(shù)和弧的條數(shù)比較多時(shí)，A*算法最快，遺傳算法其次， Dijkstta算法最慢，而且這種差距將隨節(jié)點(diǎn)和弧數(shù)量的增加而變得更加明顯.對(duì) 于實(shí)際地圖而言，由于節(jié)點(diǎn)與道路的數(shù)量一般都很的大，Dijkstia算法在搜索速 度方面弱勢(shì)明顯.搜索成功率比較對(duì)于具有個(gè)節(jié)點(diǎn)的地圖，其待規(guī)劃節(jié)點(diǎn)的個(gè)數(shù)為-1 （除起點(diǎn)

26、節(jié)點(diǎn)外，其 他均可作為待規(guī)劃節(jié)點(diǎn)），由于每個(gè)待規(guī)劃節(jié)點(diǎn)對(duì)應(yīng)于一條最短路徑，所以對(duì)每 張具有個(gè)節(jié)點(diǎn)的地圖而言，應(yīng)該規(guī)劃出-1條最短路徑.對(duì)5張地圖分別采用三種算法進(jìn)行路徑規(guī)劃，三者各自搜索到最短路徑的情 況如表2-5所示.表中括號(hào)外數(shù)據(jù)為各算法實(shí)際得到最短路徑數(shù)，括號(hào)內(nèi)數(shù)據(jù)則 為各算法實(shí)際得到路徑數(shù)和應(yīng)該規(guī)劃出的最短路徑數(shù)-1之比.表2-5三種算法在搜索質(zhì)量方面的對(duì)比節(jié)點(diǎn)數(shù)Dijkstra 算法A*算法遺傳算法1615(100%)12(80%)15(100%)3231(100%)25(81%)29 (94%)4342(100%)32 (76%)38(90%)6261(100%)40(66%)56

27、(92%)7877(100%)45(58%)71(92%)-7 -東北電力大學(xué)本科畢業(yè)論文由表2-5可以看出：當(dāng)?shù)貓D節(jié)點(diǎn)個(gè)數(shù)和弧數(shù)量比較多時(shí)，Dijkstia算法是一 種遍歷算法，每次能保證100%搜索到最短路徑，遺傳算法搜索到最短路徑的成 功率比Dijkstia算法低一些，A*算法最低，且這種差距在節(jié)點(diǎn)數(shù)和弧數(shù)量越大 時(shí)更加明顯.Dijkstra算法的優(yōu)缺點(diǎn)Dijkstia算法能夠保證100%找到最優(yōu)解，但其搜索速度較慢，搜索效率非常 低，時(shí)間花費(fèi)較多，一般只能用于離線的路徑規(guī)劃問題.如節(jié)點(diǎn)數(shù)為的圖，用Dijkstia算法計(jì)算最短路徑總共需要迭代-1次，每次 迭代都新加一個(gè)節(jié)點(diǎn)到臨時(shí)節(jié)點(diǎn)集合

28、中，由于第1次迭代時(shí)不在臨時(shí)節(jié)點(diǎn)集合中 的節(jié)點(diǎn)數(shù)為-匚即第i次迭代需對(duì)個(gè)節(jié)點(diǎn)進(jìn)行處理，因此其所需的處理數(shù) 為：(，-)=竽/=! ,對(duì)n個(gè)節(jié)點(diǎn)網(wǎng)絡(luò)的時(shí)間復(fù)雜度是0(r).在實(shí)際應(yīng)用當(dāng)中，使用Dijkstia算法 查找最短路徑時(shí)耗費(fèi)大量的時(shí)間進(jìn)行數(shù)據(jù)的比較，本文對(duì)Dijkstia算法進(jìn)行分析, 通過改變算法實(shí)現(xiàn)減少不必要節(jié)點(diǎn)計(jì)算的時(shí)間，提高算法的效率達(dá)到對(duì)其進(jìn)行優(yōu) 化.第3章 兩點(diǎn)間最短路的改進(jìn)的Dijkstra算法及其MATLAB實(shí)現(xiàn)第3章兩點(diǎn)間最短路的改進(jìn)的Dijkstra算法及其MATLAB實(shí)現(xiàn)Dijkstia矩陣算法IDijkstra矩陣算法I比Dijkstra算法更容易在計(jì)算機(jī)上實(shí)現(xiàn)，

29、它能夠計(jì)算加權(quán) 圖中任意兩頂點(diǎn)之間的最短距離.該算法的基本思想是將加權(quán)圖G(V,E)存儲(chǔ)在 矩陣A = (%，“里該矩陣可定義為0,若i = J% = , %，若iw j,頂點(diǎn)匕與Vj有連邊今若iwj,頂點(diǎn)匕與無連邊其中，為圖G的頂點(diǎn)個(gè)數(shù)，叫為邊匕匕的權(quán)重.將Dijkstra算法的思想影響用于此矩陣的第k行，可求出頂點(diǎn)收到其他各項(xiàng) 點(diǎn)的最短距離，將最短距離仍保存在矩陣A的第k行，其中k=1, 2,.當(dāng) 算法結(jié)束時(shí)，矩陣A的元素值就是任意兩頂點(diǎn)之間的最短距離.Dijkstia矩陣算法nDijkstra矩陣算法I只是簡(jiǎn)單地將Dijkstra算法的思想應(yīng)用到矩陣的每一行, 這樣做有很多的重復(fù)計(jì)算，效

30、率不高.為了提高效率，有提出了下面的Dijkstia 矩陣算法H,步驟如下：步驟1輸入加權(quán)圖，存儲(chǔ)在矩陣A = 里： U /nxrt步驟2對(duì)矩陣A進(jìn)行操作，求任意兩頂點(diǎn)間的最短距離.算法的求解過程; 循環(huán)k以1為步長(zhǎng)，從1到-1,執(zhí)行， 一1,2,，&- 1,k + 1,女 + 2,，,kk length (b),東北電力大學(xué)本科畢業(yè)論文a_id k ;bl k + l,k + 2, ,；kkl length(bl)；循環(huán).反復(fù)執(zhí)行下列語句，直到尿=0；循環(huán).J以1為步長(zhǎng)，從1到kkl,執(zhí)行；若 fe a(k,bl(j),a(k,bl( j) - temiid - 1循環(huán).J以1為步長(zhǎng)，從2到

31、&,執(zhí)行若女力(1) a(k,bmiid j.a_id b(miid)；b b(l: nuid -l),b(tniid +1: kk)；%在數(shù)組瓦中去掉一個(gè)元素kk k ,執(zhí)行miid 1 find (bl = a_id)；bl 1(1: mi id 1 -1), bl(niiid 1 +1: kkl)循環(huán).J以1為步長(zhǎng)，從攵+ 1到“，執(zhí)行步驟3則算法結(jié)束.算法H與算法I比較，在步驟循環(huán)的次數(shù)隨著我的增加而減少，循環(huán)體的執(zhí) 行總次數(shù)會(huì)減少一半.Dijkstra矩陣算法II的MATLAB實(shí)現(xiàn)見附錄.3.2.1簡(jiǎn)單實(shí)例第3章.兩點(diǎn)間最短路的改進(jìn)的Dijkstra算法及其MATLAB實(shí)現(xiàn)我們舉下面

32、圖3-1中頂點(diǎn)匕到其他頂點(diǎn)的最短距離這個(gè)例子.圖3-1實(shí)例圖用MATLAB求解的主程序如下：n=12;a=ones (n) +inf;for i=l:na (i,i) =0;enda(l,2)=5;a (2,3) =8;a (2,6) =5;a (3,4) =3;a (3,9)=10;a (4,5) =5;a (4,7) =3;a (5,6) =2;a (7,8) =2;a (8,9) =4;a (8,11)=6;-11 -東北電力大學(xué)本科畢業(yè)論文a (9,10) =3;a(10Jl)=5;a(10J2)=3; dij2_m(a)計(jì)算結(jié)果如下:匚，c 12x12 dcuble123456789

33、101112105131612101921232627292508117514161821222d31380310681013141641611305735?12111551278502810IX171620610510720101216191822719146381002598128211685101220476109231810914166Inf38，1026211312171997305311272214111618868508122924161520*12106380圖3-2運(yùn)行結(jié)果第4章 基于Dijkstra算法的優(yōu)化算法的研究第4章基于Dijkstra算法的優(yōu)化算法的研究幾種優(yōu)化算

34、法減小算法中成功搜索的搜索范圍減小算法中成功搜索的搜索范圍以盡快到達(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組件提供的MapLayei.SeaichExpiession （expression）記錄集篩選方法，根據(jù)案發(fā)地段（終點(diǎn)）的不同，動(dòng)態(tài)選取案發(fā) 地段所在轄區(qū)及相鄰轄區(qū)的道路圖層及派出所圖層數(shù)據(jù)進(jìn)行最短路徑查詢，從而 有效地減少了拓?fù)鋱D中節(jié)點(diǎn)總數(shù)的值.改進(jìn)算法的存儲(chǔ)結(jié)構(gòu)在實(shí)際工作中，還要建立起空間數(shù)據(jù)結(jié)構(gòu).網(wǎng)絡(luò)

35、數(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ǔ)量為 NxN（N為網(wǎng)絡(luò)中節(jié)點(diǎn)數(shù)）.通常的地理網(wǎng)絡(luò)，盡管節(jié)點(diǎn)很多，但與節(jié)點(diǎn)相關(guān)聯(lián) 的節(jié)點(diǎn)數(shù)目并不多，一般都為稀疏圖，將會(huì)浪費(fèi)大量的空間.若采用鄰接表的鏈 式存儲(chǔ)結(jié)構(gòu)，其存儲(chǔ)量為E（E為節(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框架包含特殊類，比如通常

36、所說的集合類用于存儲(chǔ) 對(duì)象.與數(shù)組類似，集合類可以把對(duì)象放入容器中，然后再取出.但集合的使用 方法與數(shù)組不同，擁有用于插入和刪除項(xiàng)的專用方法.使用Hashtable最大的優(yōu)點(diǎn) 就是大大降低數(shù)據(jù)存儲(chǔ)和查找的時(shí)間花費(fèi).-13-東北電力大學(xué)本科畢業(yè)論文本文對(duì)Dijlstia優(yōu)化算法研究?jī)?yōu)化目標(biāo)Dijkstra算法用來求解圖上從任一節(jié)點(diǎn)（源點(diǎn)）到其余各節(jié)點(diǎn)的最短路徑.其 時(shí)間復(fù)雜度為0（r）;采用鄰接矩陣存儲(chǔ)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，需要（NxN）的存儲(chǔ)空 間，隨著節(jié)點(diǎn)數(shù)N的增大，其計(jì)算效率和存儲(chǔ)效率越低.針對(duì)此問題，提出了 Dijkstra算法的改進(jìn)，本文在對(duì)傳統(tǒng)Dijkstra算法分析的基礎(chǔ)上，對(duì)其進(jìn)行了優(yōu)

37、化，優(yōu)化算法只對(duì)最短路徑上節(jié)點(diǎn)的鄰居做處理，而不涉及到其他節(jié)點(diǎn).優(yōu)化思路Dijkstia算法基本方法：設(shè)必是從源點(diǎn)s到節(jié)點(diǎn)j的最短路徑長(zhǎng)度；p ,是從s到 /的最短路徑中/點(diǎn)的前一節(jié)點(diǎn),S是標(biāo)識(shí)集合；T是未標(biāo)識(shí)集合；M是節(jié)點(diǎn)集 合.乙是節(jié)點(diǎn)i到節(jié)點(diǎn)）的距離（i與/直接相連，否則匕=8）,算法步驟如 下：StepO： S = s; T = M-S； VV. =（ jgT, s 與j直接相連）或% = 8 （） 7，s與）不直接相連）.Stepl：在T中找到節(jié)點(diǎn)i,使s到i的距離最小，并將，劃歸到S （可從與s直 接相連的）中考慮）若djmm內(nèi)，）與s直接相連，則將i劃歸到S中，即5 = 甲, T

38、 = T-i； jeT； Pj = S .Step2：修改T中/節(jié)點(diǎn)的匕值：Wj = imi（叱,+1匕+%）；若VV.值改變，則p =/. jwT ； ieS .Step3：選定所有的%最小值，并將其劃歸到S中：W； = minW,； S=5u/； T=T-i；若卜| 二 “,所有節(jié)點(diǎn)已標(biāo)識(shí)，-14-第4章 基于Dijkstra算法的優(yōu)化算法的研究則算法終止，否則，轉(zhuǎn)入Step2.通過分析傳統(tǒng)Dijkstia算法的基本思路，傳統(tǒng)Dijkstia算法存在如下兩點(diǎn)不足: (1)當(dāng)從未標(biāo)記節(jié)點(diǎn)集合TT中選定一個(gè)節(jié)點(diǎn)k作為轉(zhuǎn)接點(diǎn)后時(shí)，需掃描未 標(biāo)記節(jié)點(diǎn)集合T中的節(jié)點(diǎn),并更新其W,值，而未標(biāo)記節(jié)點(diǎn)集合

39、T中往往包含大量 與轉(zhuǎn)接節(jié)點(diǎn)k不直接相連的節(jié)點(diǎn)i (即4, = 8);(2)在未標(biāo)記節(jié)點(diǎn)集合T中選擇一個(gè)堆值最小的節(jié)點(diǎn)作為下一個(gè)轉(zhuǎn)接節(jié)點(diǎn), 然而下一個(gè)轉(zhuǎn)接節(jié)點(diǎn)往往是與標(biāo)記節(jié)點(diǎn)集合S中的節(jié)點(diǎn)直接相連的.問題描述基于上述兩點(diǎn)不足，對(duì)傳統(tǒng)Dijkstia算法進(jìn)行優(yōu)化，算法優(yōu)化思路為：首先 從源點(diǎn)s的鄰居集合集合N紇(與s直接相連的節(jié)點(diǎn)集合)中選擇距離最小的鄰居 節(jié)點(diǎn)k作為轉(zhuǎn)接點(diǎn)，同時(shí)將劃歸到標(biāo)識(shí)集合S (初始時(shí)，S為s).然后對(duì)k鄰 居集合與標(biāo)識(shí)集合的差集中節(jié)點(diǎn)的值進(jìn)行更新，從標(biāo)識(shí)集合s中所有節(jié)點(diǎn)的鄰居 集合的并集與標(biāo)識(shí)集合的差集(uNaS , ieS)中選擇一個(gè)M值最小的節(jié)點(diǎn)作 為下一個(gè)轉(zhuǎn)接點(diǎn)，并

40、劃歸到標(biāo)識(shí)集合s中.重復(fù)上述過程，直到所有的節(jié)點(diǎn)都被 標(biāo)識(shí)過，即卜|二，算法結(jié)束.設(shè)Ng為節(jié)點(diǎn)，的鄰居集合；S為標(biāo)識(shí)集合；明是從源點(diǎn)s到節(jié)點(diǎn))的最短 路徑長(zhǎng)度；號(hào)是從s到1的最短路徑中，點(diǎn)的前一節(jié)點(diǎn)：4是節(jié)點(diǎn)i到節(jié)點(diǎn)j的 距離.算法步驟如下：StepO：初始化 S = s； vv. = dxi (/ e NBs)；否則嗎=8(i 為 Pt= s .Stepl：若九二min%, S = S 2 = w2,w5 = niii vv5,vv4 + d45= niii 松,3 = 3 2 = 匕， 卬6 = nun限,%+九 = svv7 = nmi 卬7，卬4 + J47) = oonmi w. =

41、 h = 2 ,J -S = （l”匕，匕，匕），7 = 63，匕，16,匕）;16第4章 基于Dijkstra算法的優(yōu)化算法的研究Step3： T =（匕,v5，v7）vv3 = niii 卬3,w2 +d2Z= niii 5,5 = 5 , TOC o 1-5 h z w5 = niii vv5，卬2 + ? = nmi 3,8 = 3 4 =%=w6,若為明nmi Wj = vv3 = w6 = 4 ,二 S =（匕，匕，匕，匕，%），T = （v6,v7）；Step5： T = （v6,v7）w6 = niii vv6,嗎 + 右 = nin 4,8 = 4 ,w7 = niii 卬7

42、, vv3 + J37）= niii 5,8 = 5 4 = w6,v 111111 = = 4,S =（匕.匕,%，%,%，%），丁 =（匕）；Step6 ： T = （v7）vv7 = niii卬7,w6 +d67= niii5,6 = 5 至此，算法終止.結(jié)果為卬2 = 2, % = 4,*=2,叼=3 ,叫=4, % = 5 .東北電力大學(xué)本科畢業(yè)論文優(yōu)化Dijkstia算法求解過程：表4-1優(yōu)化的Dijkstra算法求解巧到其他各節(jié)點(diǎn)最短路徑的過程迭代選代數(shù)匕 匕匕匕匕 乙 匕定 ”叫點(diǎn)01252- 匕 卬=0（匕，匕，叱）1-25- 匕 % =2（匕，vz，匕，v5）2- 4-3-

43、 匕 w2 =2（匕，匕，匕）3- -4- 匕 叼=3（匕，匕，v6, v7）4- -45 匕 *=4 （匕，匕，匕，心，口6）5- -5 v6 vv6 =4（v3, v5, v7）6- - V7 vv7 =5（V5, v6）StepO：初始化s =（匕），與匕直接相連點(diǎn)有匕，%,辦，NS】=（匕，匕,也），叼=0；Step 1：卬4 = d4 = nun4, =2,5 = （, v4）, j e NB1=（匕，匕，0,%）, B4-5 = （v2,v3,v5）, uN54-5 = （v2,v3,v5）；Step2： jg N54-5 = （v2,v3,v5）w2 = nm vv2,卬4 +

44、J42 = niii 2,4 = 2 ,vv3 = niii 卬3，卬4 + J43 = niii 5,5 = 5 2 = w2,w5 = niii 卬5, vv4 + 45= nin 松,3 = 3 2 = w2,minnmi w：=m=2 ,J-，S =（匕，匕，匕），人/2 =（匕,匕,巳），NB2-S = （v3）, dN6?S =（匕,）Step3 ： j e l）NB? - S =（匕,v5）18第4章 基于Dijkstra算法的優(yōu)化算法的研究卬3 = nin 卬3 /匕 +/23= niii 5,5 = 5 ,明=3 4 = vv3,若為明, nun嗎=*=卬6 =%，S=（匕匕

45、，匕，匕，%）,仍3 =（匕.匕#4，%，也），NBb-S = M）,uA3-S = （v6,v7）；Step5： j2NBS = （v6,v7）卬6 =4；* =54=卬，, nunWj = vv6 =4, S =（匕2,匕 #4#5#6），凡線=（匕匕），NB6-S = （v7 ）,UN叫-S =（匕）；Step6： jwNBe-S = W）w7 = nrni %,M% + 7 = 6,6 = 5 .至此，所有節(jié)點(diǎn)已標(biāo)識(shí)，則算法終止.最終結(jié)果為叭=2, % = 4,%=2, w5 = 3 , w6 = 4,卬7 = 5 -19-東北電力大學(xué)本科畢業(yè)論文4.2.4算法特點(diǎn)傳統(tǒng)Dijkstia

46、算法基于廣度優(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í)需要訪問所有的未標(biāo)記 節(jié)點(diǎn)，算法的運(yùn)行時(shí)間為。(/).本文提出的優(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ù)雜度為O(xp),其中是常量, 為結(jié)點(diǎn)對(duì)象所占用的空間.另外，根據(jù)圖中頂點(diǎn)和邊的個(gè)數(shù)，可以求出頂點(diǎn)的平 均出度e =

47、 (根為邊數(shù)，為頂點(diǎn)數(shù))，一般在GIS的網(wǎng)絡(luò)圖中，e g 2,5,n由于Step2、Step3都是搜索與匕(/=1, 2, 3,，)相鄰的結(jié)點(diǎn)操作,時(shí)間復(fù) 雜度均為。);Step3的時(shí)間復(fù)雜度為0(,即0(xe)； Step5的時(shí)間復(fù)雜 度為0(xe).因此，算法的時(shí)間復(fù)雜度為0(xe).4.3優(yōu)化和改進(jìn)的結(jié)論由圖4-1對(duì)帶權(quán)值的無向圖G7的求解可以看出，優(yōu)化了的Dijkstta算法在 Step2和Step3中較經(jīng)典的Dijkstia算法減少了步驟(4-1) (4-2) (4-3) (4-4), 減少了計(jì)算次數(shù)，提高了搜索速度.當(dāng)網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)圖具有的節(jié)點(diǎn)數(shù)，I，較大且 其關(guān)聯(lián)矩陣為一個(gè)稀疏矩陣

48、時(shí)，相對(duì)傳統(tǒng)Dijkstia算法，優(yōu)化算法大大減少了計(jì) 算次數(shù)與比較次數(shù)，在一定程度上提高了運(yùn)算速度.在分析傳統(tǒng)Dijkstia算法的 基礎(chǔ)上，針對(duì)傳統(tǒng)Dijkstia算法存在的兩點(diǎn)不足之處，對(duì)其進(jìn)行了優(yōu)化處理.當(dāng) 網(wǎng)絡(luò)的規(guī)模較大及其關(guān)聯(lián)矩陣為一個(gè)稀疏矩陣時(shí)，本文提出的優(yōu)化算法，與傳統(tǒng) Dijkstia算法相比，能大大減少了計(jì)算次數(shù)及比較次數(shù)，提高了運(yùn)算效率.-20-第5章Dijkstra算法在物流上的應(yīng)用第5章Dijkstra算法在物流上的應(yīng)用物流成為一項(xiàng)產(chǎn)業(yè)的歷史并不久遠(yuǎn)，最早是起源于二戰(zhàn)中美軍建立的后勤理 論原型，當(dāng)時(shí)的后勤是指將戰(zhàn)時(shí)物資生產(chǎn)、采購、運(yùn)輸和配給等活動(dòng)作為整體進(jìn) 行統(tǒng)籌安排

49、，以達(dá)到使戰(zhàn)略物資補(bǔ)給費(fèi)用最低，速度最快，效率更高的目的，后 來后勤體系逐漸被經(jīng)濟(jì)領(lǐng)域采用，形成現(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)力.物流服務(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è)的發(fā)展，面對(duì)小宗單一客戶的 服務(wù)需求呈爆炸式增長(zhǎng)，物流領(lǐng)域的效率直接影響到電子商務(wù)產(chǎn)業(yè)的效益.然而物流產(chǎn)業(yè)

50、的發(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è)的競(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)而直接影

51、響到企業(yè)核心競(jìng)爭(zhēng)力的大小.因 而，為了提升物流企業(yè)的核心競(jìng)爭(zhēng)力，我們需要研究出更為有效的管理和分配方 法，充分有效利用現(xiàn)有的人力物力時(shí)間等資源，達(dá)到最優(yōu)化配送.為了科學(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)營網(wǎng)絡(luò)進(jìn)行分析控制，以實(shí)現(xiàn)良 性運(yùn)營.首先闡述了物流行業(yè)的產(chǎn)生背景和發(fā)展，以及其存在的一些問題，并主-21 -東北電力大學(xué)本科畢業(yè)論文要針對(duì)物流企業(yè)中存在的一些資源優(yōu)化調(diào)度，區(qū)域規(guī)劃管理等方面存在的問題進(jìn) 行分析，結(jié)合數(shù)學(xué)建模以及數(shù)據(jù)挖掘相

52、關(guān)技術(shù)提出了一種基于改進(jìn)Dijkstia算 法.最優(yōu)配送路線選擇問題在物流配送領(lǐng)域中，最重要的任務(wù)就是如何將貨物用最高效，快捷的方式送 達(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ì)圖最短路徑分析的方法一一Dijkstia算法對(duì)最優(yōu)配送路線選擇問題進(jìn)行分 析.我們知道，在物流配送環(huán)節(jié)中首先要形成一條既有的物流網(wǎng)絡(luò)，能夠?qū)⑷我?配送節(jié)點(diǎn)發(fā)出的貨物高效的送

53、達(dá)網(wǎng)絡(luò)中其他節(jié)點(diǎn).其中節(jié)點(diǎn)間的交通長(zhǎng)度是客觀 成本，會(huì)直接影響到相應(yīng)的人力成本和油耗成本以及損耗成本.我們?cè)O(shè)兩個(gè)物流 節(jié)點(diǎn)之間的交通長(zhǎng)度為W,也就是基礎(chǔ)成本.在此基礎(chǔ)上會(huì)產(chǎn)生附加成本.進(jìn)一步，我們會(huì)討論附加成本與基礎(chǔ)成本之間的關(guān)系問題.進(jìn)而確定每?jī)蓚€(gè) 節(jié)點(diǎn)間最終的權(quán)值.我們知道，由于不同城市的經(jīng)濟(jì)發(fā)展水平和地理因素等會(huì)導(dǎo) 致他們之間的人力成本和油耗成本等因素的不同，有些城市經(jīng)濟(jì)水平比較發(fā)達(dá)， 相應(yīng)的其人力成本和油耗成本等就會(huì)增加，而有些城市之間的交通路況不好，就 會(huì)響應(yīng)的增加油耗成本和損耗成本.故而我們需要對(duì)不同城市之間的具體情況進(jìn) 行深入調(diào)查才，采用綜合考慮的方法來確定其最終費(fèi)用阿.此外我們

54、發(fā)現(xiàn)，在物流運(yùn)輸過程中，由于兩地之間的人力成本不同會(huì)導(dǎo)致雙 向運(yùn)輸中的成本統(tǒng)計(jì)出現(xiàn)不同，因此，在本文中，我們僅取折中的辦法，統(tǒng)計(jì)兩 地之間雙向運(yùn)輸?shù)钠骄杀?我們?cè)O(shè)兩地的人力成本分別為 、只，我們根據(jù) 經(jīng)驗(yàn)公式可以得出一般運(yùn)輸領(lǐng)域中平均人力成本計(jì)算公式：p Pp=p5p”py+pj-22 -第5章.Dijkstra算法在物流上的應(yīng)用假設(shè)針對(duì)附加成本方面，我們只考慮運(yùn)輸距離，油耗，和人力成本三個(gè)基本 因素.我們?cè)O(shè)運(yùn)輸距離為W,兩個(gè)配送節(jié)點(diǎn)的油耗成本分別為。,兩個(gè)配 送節(jié)點(diǎn)的人力成本分別為巴、P, L表示貨物損耗成本，/表示實(shí)時(shí)油價(jià)，人， 我、，表示基礎(chǔ)成本影響人因子，他們分別表示各項(xiàng)附加成本受到

55、基本成本的影 響程度.我們可以得到最終成本R的計(jì)算公式為：pP.P = k2w9 L =R = ”(。1片(二+ 片)+。2 P?(=+R) + Lp2P根據(jù)不同影響因素及其影響因子我們可以得到兩個(gè)配送節(jié)點(diǎn)之間相應(yīng)的油 耗成本，人力成本以及可能的損耗成本，進(jìn)而得到最終的綜合成本，也就是兩個(gè) 配送節(jié)點(diǎn)之間的綜合權(quán)值.我們改進(jìn)的Dijkstra算法的流程圖如圖5-1所示：圖5-1改進(jìn)的Dijkstia算法流程圖-23 -東北電力大學(xué)本科畢業(yè)論文改進(jìn)的Dijkstia算法在最優(yōu)配送路線確定中的實(shí)例為了更好的說明問題，我們選取一個(gè)如圖5-2所示的簡(jiǎn)單聯(lián)通區(qū)域?yàn)槔M(jìn) 行分析和說明具體的方案設(shè)計(jì).我們可

56、以看到途中一共有七個(gè)配送節(jié)點(diǎn)，節(jié)點(diǎn)之 間的路線權(quán)值表明的是兩個(gè)節(jié)點(diǎn)的運(yùn)輸距離.圖5-2路線無向有權(quán)示意圖人力成本和油耗成本列表如表5-1所示，單位為千元/公里噸-24 -第5章Dijkstn算法在物流上的應(yīng)用表5-1人力成本表人力成本油耗成本A0.350.34B0.370.17C0.420.31D0.380.33E0.790.26F0.510.39G0.350.39各個(gè)節(jié)點(diǎn)間的聯(lián)通情況以及運(yùn)輸距離情況也可以列出表格如表5-2所示.表5-2運(yùn)輸距離表ABCDEFGAoB80C60D1530E131100F760G890我們根據(jù)以上公式對(duì)本例中的配送節(jié)點(diǎn)間綜合代價(jià)進(jìn)行計(jì)算得到了各個(gè)配 送節(jié)點(diǎn)間的綜

57、合權(quán)值如圖5-3所示：-25 -東北電力大學(xué)本科畢業(yè)論文路徑優(yōu)化結(jié)果繼而我們根據(jù)上述數(shù)據(jù)，應(yīng)用Dijkstra算法對(duì)其進(jìn)行最優(yōu)配送路徑確定，我們 確定選定的最終結(jié)果如表5-3所示：-26 -第5章Dijkstra算法在物流上的應(yīng)用表5-3路徑選擇圖路徑選擇花費(fèi)代價(jià)A f 6A f 60.72A f C0.66A .。4 .C .。1.04NtC tE0.84A f尸AfCfE一尸2.02A f GA C f E G2.20B fC6 f A f C1.38B f D6 A f C 。1.76B EB A C E1.56B F5 f AfC 一石一尸2.74B G5 f AfC 一石G2.92C tDC tD0.38C tEC E0.18C t FC f E f F1.36C f GC f E fG1.54D E。fC f E0.56D f FD f F1.11D GD C E G1.92E tFE tF1.18E fGE tG1.36F GF tG1.48這樣，我們就確定了從任意一個(gè)節(jié)點(diǎn)出發(fā)，配送到區(qū)域內(nèi)其他節(jié)點(diǎn)應(yīng)選擇的