物流運(yùn)輸與配送課程設(shè)計(jì) 遼寧工業(yè)大學(xué)

PAGE遼寧工業(yè)大學(xué)課程設(shè)計(jì)說明書（論文）遼寧工業(yè)大學(xué)物流運(yùn)輸與配送課程設(shè)計(jì)（論文）題目：MATLAB下Dijkstra算法的實(shí)現(xiàn)院（系）：汽車與交通工程學(xué)院專業(yè)班級(jí)：學(xué)號(hào)：學(xué)生姓名：ZP.Lou指導(dǎo)教師：職稱：起止時(shí)間：2012.12.17——2012.12.28課程設(shè)計(jì)（論文）任務(wù)及評(píng)語(yǔ)院（系）：汽車與交通工程學(xué)院教研室：物流工程教研室學(xué)號(hào)學(xué)生姓名專業(yè)班級(jí)課程設(shè)計(jì)（論文）題目MATLAB下Dijkstra算法的實(shí)現(xiàn)課程設(shè)計(jì)（論文）任務(wù)在掌握Dijkstra算法的基礎(chǔ)上，綜合運(yùn)用《物流運(yùn)輸與配送》、《運(yùn)籌學(xué)》、《物流學(xué)》等課程理論知識(shí)，學(xué)會(huì)利用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é)每人以一個(gè)不同的節(jié)點(diǎn)作為出發(fā)點(diǎn)手動(dòng)進(jìn)行最短路的計(jì)算；（2）利用MATLAB軟件編寫程序，以案例3的數(shù)據(jù)作為默認(rèn)數(shù)據(jù)對(duì)Dijkstra算法程序進(jìn)行測(cè)試；（3）實(shí)現(xiàn)輸入數(shù)據(jù)的界面操作；（4）輸入起始點(diǎn)和終點(diǎn)能夠自動(dòng)計(jì)算最短路徑里程及最短路徑。完成課程設(shè)計(jì)說明書。主要內(nèi)容包括：Dijkstra算法的原理、程序框圖、部分主要程序及說明、最終結(jié)果、結(jié)果分析及任務(wù)書上要求完成的內(nèi)容等。指導(dǎo)教師評(píng)語(yǔ)及成績(jī)成績(jī)：指導(dǎo)教師簽字：年月日遼寧工學(xué)院課程設(shè)計(jì)說明書（論文）PAGE13目錄一．設(shè)計(jì)目的 1二．Dijkstra算法的原理 12.1兩個(gè)指定頂點(diǎn)之間的最短路徑 12.2Dijkstra算法原理 2三．Dijkstra算法的操作步驟 2四．Dijkstra算法的程序框圖 34.1菜單程序框圖 34.2輸入程序框圖 44.3main框圖 5五．部分主要程序及其說明 65.1菜單menu程序 65.2原始數(shù)據(jù)default_dat程序 65.3輸入數(shù)據(jù)input_dat程序 75.4迪杰斯特拉算法main程序 7六．主要任務(wù) 96.1最短路的計(jì)算 96.2測(cè)試 106.2.1測(cè)試1 106.2.2測(cè)試2 116.3實(shí)現(xiàn)輸入數(shù)據(jù)界面 116.4最短路徑求取 12參考文獻(xiàn) 13MATLAB下Dijkstra算法的實(shí)現(xiàn)一．設(shè)計(jì)目的物流運(yùn)輸與配送課程設(shè)計(jì)是在學(xué)生完成物流運(yùn)輸與配送課程學(xué)習(xí)后必修的教學(xué)環(huán)節(jié)。它一方面要求學(xué)生在設(shè)計(jì)中能初步學(xué)會(huì)綜合運(yùn)用過去所學(xué)的全部知識(shí)，另外也為以后畢業(yè)設(shè)計(jì)工作做一次綜合訓(xùn)練，學(xué)生應(yīng)當(dāng)通過物流運(yùn)輸與配送課程設(shè)計(jì)達(dá)到以下幾個(gè)目的：1.培養(yǎng)學(xué)生綜合運(yùn)用《物流學(xué)》、《物流運(yùn)輸與配送》、《運(yùn)籌學(xué)》等課程理論知識(shí)的能力。2.培養(yǎng)學(xué)生初步掌握配送中心選址、配送線路優(yōu)化的基本方法和基本理論，學(xué)會(huì)利用MATLAB軟件進(jìn)行程序設(shè)計(jì)，提高理論與實(shí)際相結(jié)合的應(yīng)用能力。3.能夠進(jìn)一步強(qiáng)化學(xué)生收集整理資料的能力，提高對(duì)文獻(xiàn)資料的歸納、寫作、綜合運(yùn)用能力。二．Dijkstra算法的原理2.1兩個(gè)指定頂點(diǎn)之間的最短路徑問題如下：給出了一個(gè)連接若干個(gè)客戶的道路網(wǎng)絡(luò)，在這個(gè)網(wǎng)絡(luò)的兩個(gè)指定客戶間，找一條最短的路線。以各客戶為圖G的頂點(diǎn)，兩客戶間的直通路為圖G相應(yīng)兩頂點(diǎn)間的邊，得圖G。對(duì)G的每一邊e，賦以一個(gè)實(shí)數(shù)w(e)—直通路的長(zhǎng)度，稱為e的權(quán)，得到賦權(quán)圖G。G的子圖的權(quán)是指子圖的各邊的權(quán)和。問題就是求賦權(quán)圖G中指定的兩個(gè)頂點(diǎn)，間的具最小權(quán)的軌。這條軌叫做，間的最短路，它的權(quán)叫做，間的距離，亦記作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距從近到遠(yuǎn)為順序，依次求得到G的各頂點(diǎn)的最短路和距離，直至（或直至G的所有頂點(diǎn)），算法結(jié)束。2.2Dijkstra算法原理Dijkstra算法原理：首先，引進(jìn)一個(gè)輔助向量D，它的每個(gè)分量D表示當(dāng)前所找到的從始點(diǎn)v到每個(gè)終點(diǎn)的最短路徑的長(zhǎng)度。如D[3]=2表示從始徑相對(duì)最小長(zhǎng)度為2。這里強(qiáng)調(diào)相對(duì)就是說在算法過程中D的值是在不斷逼近最終結(jié)果但在過程中不一定就等于最短路徑長(zhǎng)度。它的初始狀態(tài)為：若從v到有弧，則D為弧上的權(quán)值；否則置D為∞。顯然，長(zhǎng)度為{∈V}的路徑就是從v出發(fā)的長(zhǎng)度最短的一條最短路徑。此路徑為。那么，下一條長(zhǎng)度次短的最短路徑是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是，則可想而知，這條路徑或者是(v,)，或者是(v,,)。它的長(zhǎng)度或者是從v到的弧上的權(quán)值，或者是和從到的弧上的權(quán)值之和。一般情況下，假設(shè)S為已求得最短路徑的終點(diǎn)的集合，則可證明：下一條最短路徑（設(shè)其終點(diǎn)為X）或者是弧(v,x)，或者是中間只經(jīng)過S中的頂點(diǎn)而最后到達(dá)頂點(diǎn)X的路徑。因此，下一條長(zhǎng)度次短的最短路徑的長(zhǎng)度必是{∈V-S}其中，D或者是弧(v,)上的權(quán)值，或者是(∈S)和弧(,)上的權(quán)值之和。迪杰斯特拉算法描述如下：（1）arcs表示弧上的權(quán)值。若不存在，則置arcs為∞。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)可能達(dá)到的最短路徑長(zhǎng)度的初值為[LocateVex(G,v),i]∈V；（2）選擇vj，使得{∈V-S}；（3）修改從v出發(fā)到集合V-S上任一頂點(diǎn)可達(dá)的最短路徑長(zhǎng)度。三．Dijkstra算法的操作步驟Dijkstra算法的操作步驟：1．初始時(shí)令回路，T={其余頂點(diǎn)}，T中頂點(diǎn)對(duì)應(yīng)的距離值若存在，為弧上的權(quán)值，若不存在，為∞；2．從T中選取一個(gè)其距離值為最小的頂點(diǎn)W且不在S中，加入到S中；3.對(duì)T中頂點(diǎn)的距離值進(jìn)行修改：若加進(jìn)W作中間頂點(diǎn)，從到的距離值比不加W的路徑要短，則修改此距離值；4.重復(fù)上述步驟2、3直到S中包含所有頂點(diǎn)，即S=T為止。四．Dijkstra算法的程序框圖4.1菜單程序框圖主菜單的程序是使界面上直接顯示所需完成的內(nèi)容，主要完成默認(rèn)數(shù)據(jù)導(dǎo)入，輸入數(shù)據(jù)，查看數(shù)據(jù)，求取路徑，退出程序的任務(wù)，其具體程序的框圖如下圖圖1菜單程序menu框圖所示。圖1菜單menu程序框圖4.2輸入程序框圖輸入程序是為了完成從外界輸入數(shù)據(jù)形成一個(gè)新的鄰接矩陣，產(chǎn)生一組新的數(shù)據(jù)進(jìn)行最短路的求解。輸入程序框圖如下圖圖2輸入input_dat程序框圖所示。圖2輸入input_dat程序框圖4.3main框圖main程序是這個(gè)系統(tǒng)的主程序，它完成的從任一結(jié)點(diǎn)開始到指定的結(jié)點(diǎn)為止的最短路程。main框圖如下圖圖3main框圖所示。圖3main框圖五．部分主要程序及其說明5.1菜單menu程序choice=input('歡迎來到dijkstra算法求取最短路徑系統(tǒng)\n請(qǐng)選擇:\n1.使用默認(rèn)數(shù)據(jù)2.輸入數(shù)據(jù)\n3.查看數(shù)據(jù)4.求取路徑\5.退出程序\n');elseifchoice==3disp(adj_mat);elseifchoice==4sta=input('請(qǐng)輸入起始結(jié)點(diǎn):');dst=input('請(qǐng)輸入目的地:');ifsta==dstfprintf('起始結(jié)點(diǎn)與目的結(jié)點(diǎn)不能相同\r\n');else[leng,path]=mainprogram(adj_mat,sta,dst);fprintf('最短路徑為%d\n',leng);k=length(path);fprintf('經(jīng)過路徑為:');fori=1:1:k-1fprintf('%d>',path(i));endfprintf('%d\n',path(k));endend該段程序完成的是從菜單界面進(jìn)入程序并選擇完成的任務(wù)。當(dāng)輸入值為1時(shí)，程序默認(rèn)使用原始數(shù)據(jù)程序即default_dat，并在界面上輸出默認(rèn)數(shù)據(jù)已被啟用。當(dāng)輸入值為2時(shí)，程序調(diào)用輸入程序即input_dat。當(dāng)輸入值為3時(shí)，程序輸出數(shù)據(jù)，并在界面上顯示。當(dāng)輸入值為4時(shí)，程序調(diào)用迪杰斯特拉算法程序即main，并在界面上輸入起始點(diǎn)和目的點(diǎn)，通過main的計(jì)算，能輸出最短路徑和經(jīng)過的路徑。當(dāng)輸入值為5時(shí)，退出程序。5.2原始數(shù)據(jù)default_dat程序functionadj_mat=default_dat()%定義原始數(shù)據(jù)函數(shù)length=10;%定義結(jié)點(diǎn)個(gè)數(shù)adj_mat=zeros(length);%鄰接矩陣adj_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)個(gè)數(shù)來確定鄰接矩陣的寬度，并能輸入案例上的的數(shù)據(jù)，用其來進(jìn)行測(cè)試。5.3輸入數(shù)據(jù)input_dat程序functionadj_mat=input_dat()%定義輸入數(shù)據(jù)函數(shù)length=input('請(qǐng)輸入節(jié)點(diǎn)的數(shù)量');%定義結(jié)點(diǎn)個(gè)數(shù)adj_mat=zeros(length);%定義一個(gè)鄰接矩陣fori=1:1:lengthforj=i:1:lengthifi~=jfprintf('請(qǐng)輸入結(jié)點(diǎn)%d到結(jié)點(diǎn)%d的長(zhǎng)度(沒有則輸入0)',i,j)adj_mat(i,j)=input(':');%輸入結(jié)點(diǎn)間的距離ifadj_mat(i,j)==0adj_mat(i,j)=inf;endadj_mat(j,i)=adj_mat(i,j);%對(duì)稱成為一個(gè)完整的對(duì)稱矩陣endendend該段程序完成的是輸入數(shù)據(jù)的過程，通過在界面上輸入的結(jié)點(diǎn)數(shù)，以及從各結(jié)點(diǎn)到其后面的結(jié)點(diǎn)之間的距離，在對(duì)輸入的數(shù)據(jù)進(jìn)行對(duì)稱，使其成為一個(gè)完整的矩陣，為以后的計(jì)算做鋪墊。5.4迪杰斯特拉算法main程序m=length(adj_mat);%定義m的長(zhǎng)度lengs=linspace(0,0,m);%產(chǎn)生行矢量fori=1:1:mifi~=stalengs(i)=adj_mat(sta,i);iflengs(i)~=infpaths(i)=sta;endendend%for循環(huán)求起始點(diǎn)到各鄰點(diǎn)的距離index=1;%標(biāo)號(hào)fori=1:1:mifi~=stamin=inf;%讓最小值min為∞forj=1:1:miflengs(j)<=mink=j;min=lengs(j);endend%for循環(huán)求最小值，并將lengs(j)的值賦給min，最后確定距起始點(diǎn)最近的點(diǎn)know(index)=k;index=index+1;forj=1:1:mif(lengs(i)+adj_mat(i,j))<lengs(j)lengs(j)=lengs(i)+adj_mat(i,j);paths(j)=i;endend%for循環(huán)球最短路并確定結(jié)點(diǎn)endend%循環(huán)計(jì)算，求取最短路的距離該段程序是完成dijkstra算法的主要程序。在該段程序中先定義一個(gè)起點(diǎn)，再?gòu)钠瘘c(diǎn)出發(fā)將起點(diǎn)的鄰接矩陣求出，并從中找出距離起點(diǎn)最近的點(diǎn)作為下一個(gè)起點(diǎn)，再?gòu)脑撈瘘c(diǎn)出發(fā)求其鄰接矩陣，找出該鄰接矩陣以及上一個(gè)鄰接矩陣中除該點(diǎn)外的其他距離中最小的值所表示的結(jié)點(diǎn)作為新的起點(diǎn)，以此類推，直到求到目的結(jié)點(diǎn)為止。如此即可完成dijkstra算法，求出從已知起點(diǎn)到目的點(diǎn)的最短距離及其具體的路徑。六．主要任務(wù)6.1最短路的計(jì)算選擇節(jié)點(diǎn)10為基點(diǎn)可得：，，，M={1,2,3,4,5,6,7,8,9}；；；；；；；；，，即10-->9，，，M={1,2,3,4,5,6,7,8,}；；；；；；；，，即10-->7，，，M={1,2,3,4,5,6,8}；；；；；；，，即10-->8，，，M={1,2,3,4,5,6}；；；；；，，即10-->5，，，M={1,2,3,4,6}；；；；，，即10-->6，，，M={1,2,3,4}；；；，，即10-->3，，，M={1,2,4}；；，，即10-->4或10-->8-->4或10-->5-->4，，，M={1,2}；，，即10-->1或10-->3-->1，，，M={2}，，即10-->2或10-->7-->2最后得到的具體結(jié)果如下所示：起點(diǎn)為10點(diǎn)，終點(diǎn)為1點(diǎn)的最短距離為22，其路徑為10-->1或10-->3-->1。起點(diǎn)為10點(diǎn)，終點(diǎn)為2點(diǎn)的最短距離為22，其路徑為10-->2或10-->7-->2。起點(diǎn)為10點(diǎn)，終點(diǎn)為3點(diǎn)的最短距離為17，其路徑為10-->3。起點(diǎn)為10點(diǎn)，終點(diǎn)為4點(diǎn)的最短距離為18，其路徑為10-->4或10-->8-->4或10-->5-->4。起點(diǎn)為10點(diǎn)，終點(diǎn)為5點(diǎn)的最短距離為15，其路徑為10-->5。起點(diǎn)為10點(diǎn)，終點(diǎn)為6點(diǎn)的最短距離為16，其路徑為10-->6。起點(diǎn)為10點(diǎn)，終點(diǎn)為7點(diǎn)的最短距離為11，其路徑為10-->7。起點(diǎn)為10點(diǎn)，終點(diǎn)為8點(diǎn)的最短距離為11，其路徑為10-->8。起點(diǎn)為10點(diǎn)，終點(diǎn)為9點(diǎn)的最短距離為10，其路徑為10-->9。6.2測(cè)試6.2.1測(cè)試1以案例3的數(shù)據(jù)作為默認(rèn)數(shù)據(jù)對(duì)Dijkstra算法程序進(jìn)行測(cè)試。現(xiàn)取10點(diǎn)為起始點(diǎn)，以2點(diǎn)