1、遼 寧 工 業(yè) 大 學(xué) 物流運(yùn)輸與配送 課程設(shè)計(jì)（論文）題目：MATLAB下Dijkstra算法的實(shí)現(xiàn)院（系）： 汽車與交通工程學(xué)院 專業(yè)班級： 物流工程092 學(xué) 號： 091204046 學(xué)生姓名： 牟東旭 指導(dǎo)教師： 宛劍業(yè) 職 稱： 教授 起止時間： 2012.12.172012.12.28 課程設(shè)計(jì)（論文）任務(wù)及評語院（系）：汽車與交通工程學(xué)院 教研室：物流工程教研室學(xué) 號091204046學(xué)生姓名 牟東旭專業(yè)班級物流工程092課程設(shè)計(jì)（論 文）題 目MATLAB下Dijkstra算法的實(shí)現(xiàn)課程設(shè)計(jì)（論文）任務(wù)在掌握Dijkstra算法的基礎(chǔ)上，綜合運(yùn)用物流運(yùn)輸與配送、運(yùn)籌學(xué)、物流學(xué)

2、等課程理論知識，學(xué)會利用MATLAB軟件編制設(shè)計(jì)程序，提高理論與實(shí)際相結(jié)合的應(yīng)用能力。 要求運(yùn)用節(jié)約法進(jìn)行配送線路設(shè)計(jì)，解決課程設(shè)計(jì)指導(dǎo)書上案例3，計(jì)算應(yīng)用MATLAB軟件。編寫設(shè)計(jì)程序，并調(diào)試運(yùn)行，完成以下任務(wù)：（1）同組同學(xué)每人以一個不同的節(jié)點(diǎn)作為出發(fā)點(diǎn)手動進(jìn)行最短路的計(jì)算； （2）利用MATLAB軟件編寫程序，以案例3的數(shù)據(jù)作為默認(rèn)數(shù)據(jù)對Dijkstra算法程序進(jìn)行測試；（3）實(shí)現(xiàn)輸入數(shù)據(jù)的界面操作；（4）輸入起始點(diǎn)和終點(diǎn)能夠自動計(jì)算最短路徑里程及最短路徑。完成課程設(shè)計(jì)說明書。主要內(nèi)容包括：Dijkstra算法的原理、程序框圖、部分主要程序及說明、最終結(jié)果、結(jié)果分析極任務(wù)書上要求完成的內(nèi)

3、容等。指導(dǎo)教師評語及成績成績： 指導(dǎo)教師簽字： 年 月 日遼 寧 工 學(xué) 院 課 程 設(shè) 計(jì) 說 明 書（論 文）目錄一設(shè)計(jì)目的1二Dijkstra算法的原理12.1Dijkstra算法原理1適用條件與限制1算法流程12.2 Dijkstra算法22.3 Dijkstra算法思想22.4 Dijkstra算法具體步驟2三. 程序框圖2四主要程序說明34.1菜單menu程序44.2原始數(shù)據(jù)default_dat程序54.3輸入數(shù)據(jù)input_dat程序54.4迪杰斯特拉算法main程序5五 任務(wù)75.1手動計(jì)算75.2測試85.2.1測試185.2.2測試295.2.2測試395.3數(shù)據(jù)輸入10

4、5.4計(jì)算最短路徑11參考文獻(xiàn)1111MATLAB下Dijkstra算法的實(shí)現(xiàn)一設(shè)計(jì)目的物流運(yùn)輸與配送課程設(shè)計(jì)是在學(xué)生完成物流運(yùn)輸與配送課程學(xué)習(xí)后必修的教學(xué)環(huán)節(jié)。它一方面要求學(xué)生在設(shè)計(jì)中能初步學(xué)會綜合運(yùn)用過去所學(xué)的全部知識，另外也為以后畢業(yè)設(shè)計(jì)工作做一次綜合訓(xùn)練，學(xué)生應(yīng)當(dāng)通過物流運(yùn)輸與配送課程設(shè)計(jì)達(dá)到以下幾個目的：1.培養(yǎng)學(xué)生綜合運(yùn)用物流學(xué)、物流運(yùn)輸與配送、運(yùn)籌學(xué)等課程理論知識的能力。2.培養(yǎng)學(xué)生初步掌握配送中心選址、配送線路優(yōu)化的基本方法和基本理論，學(xué)會利用MATLAB軟件進(jìn)行程序設(shè)計(jì)，提高理論與實(shí)際相結(jié)合的應(yīng)用能力。3.能夠進(jìn)一步強(qiáng)化學(xué)生收集整理資料的能力，提高對文獻(xiàn)資料的歸納、寫作、綜合

5、運(yùn)用能力。同組組員：盧駿鵬，佟連慶，苗靈卉，胡冰。二Dijkstra算法的原理2.1Dijkstra算法原理Dijkstra算法是一種求單源最短路的算法，即從一個點(diǎn)開始到所有其他點(diǎn)的最短路。其基本原理是：每次新擴(kuò)展一個距離最短的點(diǎn)，更新與其相鄰的點(diǎn)的距離。當(dāng)所有邊權(quán)都為正時，由于不會存在一個距離更短的沒擴(kuò)展過的點(diǎn)，所以這個點(diǎn)的距離永遠(yuǎn)不會再被改變，因而保證了算法的正確性。不過根據(jù)這個原理，用Dijkstra求最短路的圖不能有負(fù)權(quán)邊，因?yàn)閿U(kuò)展到負(fù)權(quán)邊的時候會產(chǎn)生更短的距離，有可能就破壞了已經(jīng)更新的點(diǎn)距離不會改變的性質(zhì)。 如果用本算法求一個圖中全部的最短路，則要以每個點(diǎn)為源調(diào)用一次Dijkstra

6、算法。 適用條件與限制 有向圖和無向圖都可以使用本算法，無向圖中的每條邊可以看成相反的兩條邊。 用來求最短路的圖中不能存在負(fù)權(quán)邊。(可以利用拓?fù)渑判驒z測) 算法流程在以下說明中，s為源，wu,v為點(diǎn)u和v之間的邊的長度，結(jié)果保存在dist 初始化：源的距離dists設(shè)為0，其他的點(diǎn)距離設(shè)為無窮大，同時把所有的點(diǎn)的狀態(tài)設(shè)為沒有擴(kuò)展過。 循環(huán)n-1次： 在沒有擴(kuò)展過的點(diǎn)中取一距離最小的點(diǎn)u，并將其狀態(tài)設(shè)為已擴(kuò)展。 對于每個與u相鄰的點(diǎn)v，執(zhí)行Relax(u,v)，也就是說，如果distu+wu,v,path(i);endfprintf(%dn,path(k);endend該段程序完成的是從菜單界面

7、進(jìn)入程序并選擇完成的任務(wù)。當(dāng)輸入值為1時，程序默認(rèn)使用原始數(shù)據(jù)程序即default_dat，并在界面上輸出默認(rèn)數(shù)據(jù)已被啟用。當(dāng)輸入值為2時，程序調(diào)用輸入程序即input_dat。當(dāng)輸入值為3時，程序輸出數(shù)據(jù)，并在界面上顯示。當(dāng)輸入值為4時，程序調(diào)用迪杰斯特拉算法程序即main，并在界面上輸入起始點(diǎn)和目的點(diǎn)，通過main的計(jì)算，能輸出最短路徑和經(jīng)過的路徑。當(dāng)輸入值為5時，退出程序。4.2原始數(shù)據(jù)default_dat程序function adj_mat=default_dat() %定義原始數(shù)據(jù)函數(shù)length=10; %定義結(jié)點(diǎn)個數(shù)adj_mat=zeros(length); %鄰接矩陣adj

8、_mat(1,1)=0;adj_mat(1,2)=8;adj_mat(1,3)=5;adj_mat(1,4)=9;adj_mat(1,5)=12;adj_mat(1,6)=14;adj_mat(1,7)=12;adj_mat(1,8)=16;adj_mat(1,9)=17;adj_mat(1,10)=22; %原始數(shù)據(jù)該段程序通過定義結(jié)點(diǎn)個數(shù)來確定鄰接矩陣的寬度，并能輸入案例上的的數(shù)據(jù)，用其來進(jìn)行測試。4.3輸入數(shù)據(jù)input_dat程序function adj_mat =input_dat() %定義輸入數(shù)據(jù)函數(shù)length = input(請輸入節(jié)點(diǎn)的數(shù)量 ); %定義結(jié)點(diǎn)個數(shù)adj_ma

9、t=zeros(length); %定義一個鄰接矩陣for i =1:1:length for j =i:1:lengthif i = jfprintf(請輸入結(jié)點(diǎn)%d到結(jié)點(diǎn)%d的長度(沒有則輸入0),i,j)adj_mat(i,j) = input(:); %輸入結(jié)點(diǎn)間的距離if adj_mat(i,j) = 0adj_mat(i,j) = inf;endadj_mat(j,i) = adj_mat(i,j); %對稱成為一個完整的對稱矩陣endendend 該段程序完成的是輸入數(shù)據(jù)的過程，通過在界面上輸入的結(jié)點(diǎn)數(shù)，以及從各結(jié)點(diǎn)到其后面的結(jié)點(diǎn)之間的距離，在對輸入的數(shù)據(jù)進(jìn)行對稱，使其成為一個完

10、整的矩陣，為以后的計(jì)算做鋪墊。4.4迪杰斯特拉算法main程序m=length(adj_mat); %定義m的長度lengs =linspace(0,0,m); %產(chǎn)生行矢量for i = 1:1:m if i = sta lengs(i) = adj_mat(sta,i); if lengs(i) = inf paths(i) = sta; end end end %for循環(huán)求起始點(diǎn)到各鄰點(diǎn)的距離index = 1; %標(biāo)號for i = 1:1:m if i = sta min = inf; %讓最小值min為for j = 1:1:m if lengs(j) = mink = j; m

11、in = lengs(j); end end %for循環(huán)求最小值，并將lengs(j)的值賦給min，最后確定距起始點(diǎn)最近的點(diǎn)know(index) = k; index=index+1;for j = 1:1:m if (lengs(i) + adj_mat(i,j) 1。通過MATLAB計(jì)算得到結(jié)果如下圖2 測試結(jié)果1 所示。圖 2 測試結(jié)果15.2.2測試2現(xiàn)取5點(diǎn)為起始點(diǎn)，以2點(diǎn)為終點(diǎn)。其手動計(jì)算結(jié)果為最短路徑長度為16，其路徑是5 -6 -2。通過MATLAB計(jì)算得到結(jié)果如下圖3 測試結(jié)果 2 所示。圖3 測試結(jié)果25.2.2測試3現(xiàn)取5點(diǎn)為起始點(diǎn)，以8點(diǎn)為終點(diǎn)。其手動計(jì)算結(jié)果為最

12、短路徑長度為6，其路徑是5 -8。通過MATLAB計(jì)算得到結(jié)果如下圖4 測試結(jié)果 3 所示。圖 4 測試35.3數(shù)據(jù)輸入進(jìn)行菜單選擇的界面操作如圖 5菜單選擇界面所示。在該界面可以完成使用默認(rèn)數(shù)據(jù)，輸入數(shù)據(jù)，查看數(shù)據(jù)，求取路徑和退出程序等功能。而且使用該界面能更直觀的讓使用者使用。圖 5 菜單選擇界面以下是實(shí)現(xiàn)輸入數(shù)據(jù)與查看數(shù)據(jù)的任務(wù)，在該過程中，可以輸入結(jié)點(diǎn)的數(shù)量，并能輸入各結(jié)點(diǎn)之間的距離，顯示一個對稱的矩陣，為以后的求解做準(zhǔn)備。其具體的操作步驟如圖6 輸入數(shù)據(jù) 所示。圖6輸入數(shù)據(jù)5.4計(jì)算最短路徑該程序可以完成輸入起始點(diǎn)和終點(diǎn)能夠自動計(jì)算最短路徑里程及最短路徑?，F(xiàn)輸入4個結(jié)點(diǎn)，且結(jié)點(diǎn)1到結(jié)點(diǎn)2的距離為44，結(jié)點(diǎn)1到結(jié)點(diǎn)3的距離為16，結(jié)點(diǎn)1到結(jié)點(diǎn)4的距離為23，結(jié)點(diǎn)2到結(jié)點(diǎn)3的距離為5，結(jié)點(diǎn)2到結(jié)點(diǎn)4的距離為9，結(jié)點(diǎn)3到結(jié)點(diǎn)4的距離為3?，F(xiàn)計(jì)算結(jié)點(diǎn)1到結(jié)點(diǎn)4的距離，其最短路徑為5，路徑是1 -3-4。使用MATLA