物流运输与配送课程设计辽宁工业大学概要

1、辽宁工业大学物流运输与配送课程设计（论文）题目：MATLAB 下 Dijkstra 算法的实现院（系）：汽车与交通工程学院专业班级：_学 号：_学生姓名：ZP 丄 ou_指导教师：_职 称：_起止时间：2012.12.17 2012.12.28课程设计（论文）任务及评语院（系）：汽车与交通工程学院教研室：物流工程教研室号学伏题现实的法算课程设计论文任务物应帕S纟实算0立日、亍“二,#氧DD曲M 3 J m 加阳纳程眾、夂n宅)少序案短M径理内皿程上铁最饋路原的fB计书任行卩短啲成站设导下进剧最m完酣制指以切射叔算求范扁十戈手孩E扌罢狀m忖秋心3W初卧容果忖用朋序茁W出mM结础利线程不编操够要、

2、基会送计个件面能主跻学何欣软伽紅也紳算此曲扁人AB据和明呼1 HI血卄5閒M;zw几握WJ的运AA同利出实输课序掌爭合r) ) ) )程在少结要何(1d程(3(4完要学相M法主流际用算分指导教师评语及成绩日月年指成目录一设计目的. 1二. Dijkstra 算法的原理 . 12.1 两个指定顶点之间的最短路径 . 12.2 Dijkstra 算法原理 . 2三. Dijkstra 算法的操作步骤. 2四. Dijkstra 算法的程序框图. 34.1 菜单程序框图. 34.2 输入程序框图. 44.3 main 框图. 5五. 部分主要程序及其说明. 65.1 菜单 menu 程序. 65.2

3、 原始数据 default_dat程序 . 65.3 输入数据 input_dat 程序 . 75.4 迪杰斯特拉算法 main 程序. 7六. 主要任务. 96.1 最短路的计算. 96.2 测试. 106.2.1 测试 1. 106.2.2 测试 2. 116.3 实现输入数据界面. 11辽宁工业大学课程设计说明书（论文）6.4 最短路径求取. 12参考文献. 13辽宁工业大学课程设计说明书（论文）辽宁工学院课程设计说明书(论 文)1一.设计目的物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环 节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识， 另外也

4、为以 后毕业设计工作做一次综合训练，学生应当通过物流运输与配送课程设计达到以下几个 目的：1. 培养学生综合运用物流学、物流运输与配送、运筹学等课程理论知识的 能力。2. 培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利 用MATLAB件进行程序设计，提高理论与实际相结合的应用能力。3. 能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合 运用能力。Dijkstra 算法的原理2.1 两个指定顶点之间的最短路径问题如下：给出了一个连接若干个客户的道路网络，在这个网络的两个指定客户间，找一条最短的路线。以各客户为图 G 的顶点，两客户间的直通路为图 G

5、相应两顶点间的边，得图 G。 对 G的每一边 e,赋以一个实数 w(e)直通路的长度，称为 e 的权，得到赋权图 G。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点 u0，v0间的具最小权的轨。这条轨叫做 u0，v0间的最短路，它的权叫做 Uo，v0间的距离，亦记作 d Uo，v。求最短路已有成熟的算法：迪克斯特拉( Dijkstra)算法，其基本思想是按 距 U0从近到远为顺序，依次求得 U0到 G 的各顶点的最短路和距离，直至 V。(或直至 G 的 所有顶点)，算法结束。MATLA下 Dijkstra 算法的实现辽宁工学院课程设计说明书(论 文)22.2 Dijk

6、stra 算法原理Dijkstra 算法原理：首先，引进一个辅助向量 D，它的每个分量 D 表示当前所找 到的从始点 v 到每个终点 v 的最短路径的长度。如 D3=2 表示从始径相对最小长度为 2。 这里强调相对就是说在算法过程中 D 的值是在不断逼近最终结果但在过程中不一定就等 于最短路径长度。它的初始状态为：若从 v 到 y 有弧，则 D 为弧上的权值；否则置 D 为 竝显然，长度为D Ij I - Min D |Vi V的路径就是从v出发的长度最短的一条最短 路径。此路径为(V,Vj)。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路 径的终点是 Vk，则可想而知，这条路径或者是

7、(V, Vk)，或者是(V, Vj, Vk)。它的长度或 者是从 v 到 Vk的弧上的权值，或者是D lj 1 和从 Vj到 Vk的弧上的权值之和。一般情况下，假设 S 为已求得最短路径的终点的集合，则可证明：下一条最短路径(设其终点为X)或者是弧(v,x)，或者是中间只经过 S 中的顶点而最后到达顶点 X 的路径。因此，下一条 长度次短的最短路径的长度必是 D I j I - Min D W V-S其中，D 或者是弧(v, vj 上的权 值，或者是 D Ik (Vk S)和弧(Vk, v )上的权值之和。迪杰斯特拉算法描述如下：(1) arcs 表示弧上的权值。若不存在，则置 arcs 为花

8、 S 为已找到从 v 出发的最短 路径的终点的集合，初始状态为空集。那么，从 V 出发到图上其余各顶点 Vi可能达到的 最短路径长度的初值为D =arcsLocate Vex(Gv),i vi V ；(2) 选择 vj，使得 D lj I - Mi n D |v V-S;(3) 修改从 v 出发到集合 V-S 上任一顶点 Vk可达的最短路径长度。三. Dijkstra 算法的操作步骤Dijkstra 算法的操作步骤：1.初始时令回路 S 二V。，T=其余顶点，T 中顶点对应的距离值若存在 V0,V；，dM,VJ 为 Vo，VL；.弧上的权值，若不存在W，d(Vo,Vi)为；2. 从 T 中选取

9、一个其距离值为最小的顶点 W 且不在 S 中，加入到 S 中；3. 对 T 中顶点的距离值进行修改：若加进 W 作中间顶点，从 Vo到 Vi的距离值比不 加W 的路径要短，则修改此距离值；4. 重复上述步骤 2、3 直到 S 中包含所有顶点，即 S=T 为止。辽宁工学院课程设计说明书（论 文）3四. Dijkstra 算法的程序框图4.1 菜单程序框图主菜单的程序是使界面上直接显示所需完成的内容，主要完成默认数据导入，输入数据，查看数据，求取路径，退出程序的任务，其具体程序的框图如下图图 1 菜单程序 menu 框图 所示。辽宁工学院课程设计说明书（论 文）4辽宁工学院课程设计说明书（论 文）

10、54.2 输入程序框图输入程序是为了完成从外界输入数据形成一个新的邻接矩阵，产生一组新的数据进行最短路的求解。输入程序框图如下图图 2 输入 input_dat 程序框图 所示。开始输入全局变量 length,i,jadj_mat=zeros(length);i=1j=j+1skipYadj_mat(i,j)=input(:);adj_mat(j,i)=adj_mat(i,j)结束skipskipi=i+1;j=ii=jYNi,path(i);endfprin tf(%dn,path(k);endend该段程序完成的是从菜单界面进入程序并选择完成的任务。当输入值为 1 时，程序默认使用原始数据

11、程序即default_dat,并在界面上输出默认数据已被启用。当输入值为 2 时，程序调用输入程序即 input_dat。当输入值为 3 时，程序输出数据，并在界面上显示。当输入值为 4 时，程序调用迪杰斯特拉算法程序即main,并在界面上输入起始点和目的点，通过 main 的计算，能输出最短路径和经过的路径。当输入值为 5 时，退出程序。5.2 原始数据 default_dat 程序辽宁工学院课程设计说明书（论 文）9fun cti on adj_mat=default_dat()%定义原始数据函数辽宁工学院课程设计说明书(论 文)10len gth=10;adj_mat=zeros(len

12、gth);%定义结点个数%邻接矩阵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;%原始数据该段程序通过定义结点个数来确定邻接矩阵的宽度，并能输入案例上的的数据，用其来进行测试。5.3 输入数据 input_dat 程序fun cti on adj_mat =in put_dat() length = in put(请输入节点的数量

13、);adj_mat=zeros(le ngth);for i =1:1:le ngth%定义输入数据函数%定义结点个数%定义一个邻接矩阵for j =i:1:le ngthif i =jfprintf(请输入结点%d 到结点%d 的长度(没有则输入 0),i,j)adj_mat(i,j) = in put(:);% 输入结点间的距离if adj_mat(i,j) = 0adj_mat(i,j) = inf;endadj_mat(j,i) = adj_mat(i,j);end%对称成为一个完整的对称矩阵endend该段程序完成的是输入数据的过程，通过在界面上输入的结点数，以及从各结点到其后面的结

14、点之间的距离， 在对输入的数据进行对称， 使其成为一个完整的矩阵， 为以 后的计算做铺垫。5.4 迪杰斯特拉算法 main 程序m=le ngth(adj_mat);lengs =li nspace(0,0,m);for i = 1:1:m if i =stalen gs(i) = adj_mat(sta,i);if len gs(i)=inf%定义 m 的长度%产生行矢量辽宁工学院课程设计说明书（论 文）11辽宁工学院课程设计说明书(论 文)12paths(i) = sta;endendend%for 循环求起始点到各邻点的距离in dex = 1;for i = 1:1:mif i = s

15、tamin = inf;for j = 1:1:mif len gs(j) = mink = j;min = len gs(j);end end%for 循环求最小值，并将 lengs(j)的值赋给 min，最后确定距起始点最近的点kno w(i ndex) = k;in dex=in dex+1;for j = 1:1:mif (le ngs(i) + adj_mat(i,j) 7i =7，Vi=11，Vj =：:，M=1,2,3,4,5,6,8V1二 V7D71=11 12 = 23; V2二 V7D72=1111 = 22 ；V3二 V7D73=11 7 = 18 ；V4二 V7D74=

16、11 10 =21 ；V.二 V7D75=1110 = 21;V6二 V7D76= 119= 20 ；V8二 V7D78=11 8 =19Vmin二 V8=11，j =8，即 10 8i =8，Vi=11，Vj:，M=1,2,3,4,5,6V1二 V8D81=1116=27 ；V2二 V8D82=11 18 = 29 ； V3二 V*Dg3=11 12 = 23；V4二 V8D84=11 7=18 ； V5二 V8D85=11 6=17 ； V6二V8D86=11 14 = 25Vmin二 V5=15，j = 5，即 10 -5i =5，Vi=15，Vj:，M=1,2,3,4,6V1二 V5D

17、51=15 12 =27 ；V2二 V5D52=15 17 = 32；V3二 V5D53= 15 9 = 24 ；V4二 V5D54=15 3=18 ；V6二 V5D56=15 8=23i =0， =0, VjVi -Vio Dpi= 22V5 -V10 D105-15V9 -V10D10-10Vmin二 V9“O，j =9，即 10 -9辽宁工学院课程设计说明书(论 文)14Vmin二 V6=16，j =6，即 10 -6i =6，Vi=16，Vj -:，M=1,2,3,4V1二 V6d61=16 14 =30 ； V2二 V6d62=16 8 =24 ；V3二 V6d63= 16 11 =

18、 27 ；V4二 V6d64=16 17 =33Vmin=V3=17,j-3，即10 -3i =3, Vi=17 , Vj広,M=1,2,4V1二 V3d31=17 5 =22; V2二 V3d32=17 9 =26 ； V,=V3d34=17 7 = 24Vmin=V4=18,j =4，即 10 -4 或 10 -8-4 或 10 -5-4i =4, V=18,VjM=1,27、=V4d41=18 9 =27;V2=V4d42=18 15 = 33Vmin=V1=22,j =1,即卩 10 -1 或 10 -3-1i =1, V =22 , Vj=血,M=2V2 =V川2=22 8 = 30

19、Vmin “2=22 ,j -2，即 10 -2 或 10 -7-2最后得到的具体结果如下所示：起点为 10 点，终点为 1 点的最短距离为 22，其路径为 10 -1 或 10 -3-1。起点为 10 点，终点为 2 点的最短距离为 22，其路径为 10 -2 或 10 -7-2。起点为 10 点，终点为 3 点的最短距离为 17,其路径为 10 -3。起点为 10 点，终点为 4 点的最短距离为 18,其路径为 10 -4 或 10 -8-4 或10 -5-4 。起点为 10 点，终点为 5 点的最短距离为 15,其路径为 10 -5。起点为 10 点，终点为 6 点的最短距离为 16,其

20、路径为 10 -6。起点为 10 点，终点为 7 点的最短距离为 11,其路径为 10 -7。起点为 10 点，终点为 8 点的最短距离为 11,其路径为 10 -8。起点为 10 点，终点为 9 点的最短距离为 10,其路径为 10 -9。6.2 测试 6.2.1 测试 1以案例 3 的数据作为默认数据对 Dijkstra 算法程序进行测试。现取 10 点为起始点， 以 2点为终点。其手动计算结果为最短路径长度为 22,其路径是 10 -2。通过 MATLAB 计算得到结果如下图 4 测试结果 1 所示。惑:迴 1并至片 di jk 匸仝短去號收艰短貉if壬爭绽i.-Geffljsx 认臧

21、土居a-3.J 半耳丈喻壬吁.d底出栏仔I败认竝4JS匕 Wi 启用惑开口未笔 i| di jk=-t 輕：去工氐書訐跆讦序纟左i*T.ia+ =1 -使认缈増2-锚人歿辽宁工学院课程设计说明书（论 文）15寸-ZELE=tfefJ利-乘厢.路1R- :IJE.血花呈仔2惑;迎并圭 i| di jke-t 丄旺铤：主皐迂绘岡 z粘 位.# 轴1- tfc FH躲认魏垢2.諭入藏揖n H 石欺 a -卓取.剧 r 任 d nE 山柱仔图 4 测试结果 1622 测试 2现取 10 点为起始点，以 8 点为终点。其手动计算结果为最短路径长度为11,其路径是 10 -8。通过 MATLAB 计算得到

22、结果如下图 5 测试结果 2 所示。我迎来到 di jkMt raffi法求取昴垣賂径奉统 请选挥：1”使坤默认數握2.SuASHe3.查看裁据4.求取路拄弓.退出程序1默认数帼己被启用改迎来刊五 j kct r 炉法求取最 SS路径系纸i 百选择：】*使用默:认数据氏输入数据九査看馥据4 ”求取 B8 径 5.迟出程作a请输入起妬结点：10请输入目的地油rath -10 8最短路径拘 11境过路磴対：W-8改迎来到 di j kst r曲法求取最趣路径系统i 百选择：】*使用默认数据2.输入数据九查看魏据4.求取略径氐迟出程丽图 5 测试结果 2通过以上随机取的两组数据， 经过 MATLAB

23、 的计算与手动的计算，可以看出其结果是完全相同的，能够判断出 Dijkstra 程序的准确性。6.3 实现输入数据界面进行菜单选择的界面操作如图 6 菜单选择界面 所示。在该界面可以完成使用默 认数据，输入数据，查看数据，求取路径和退出程序等功能。而且使用该界面能更直观 的让使用者使用。Couand lindov辽宁工学院课程设计说明书（论 文）16欢迎来帥 jkmt 谴繇取聽路经系统W：点服认蹴2 输入孵11W4.求取路蝕毗駢图 6 菜单选择界面辽宁工学院课程设计说明书（论 文）如图 8 求取结杲17以下是实现输入数据与查看数据的任务，在该过程中，可以输入结点的数量，并能 输入各结点之间的距

24、离，显示一个对称的矩阵，为以后的求解做准备。其具体的操作步殴迎味到 di讣处艺的 H去求取最短蹈径:手続 i青选扛:1.使用默认救据3.垂石藏锯2诘倫入啪点的救串话愉入箱点 1到绪焉总的怅区 圻迂育则輸入口八 2 诂输人结点1到结点勺的怅虔 住更有.则输入口）= 4 诘犒入詔点 1 剧给点理的垃底（滾右贝肋席入口）: S 话輸人结点 2到蜡点 3的冬區 召迂育则愉人 G =日 诂输入纸点 g 到结点 4的怔虚 岳更有.则输入口）: 2 诘输入蝸点;J 到给点 q 的也度（滾右则输入5 政迪来到 dijks-tr 比舁洙求取披理昭任吞銃1 使用默认数扼3.疋石瞰据3政迎来到日:L -ik=r去求取尿短蹈径手统i 青选扛:1 f 申用默认救据2愉入救据3-玄右皺壻4.求取蹈径氐退出程序I图 7 输入数据6.4 最短路径求取该程序可以完成输入起始点和终点能够自动计算最短路径里程及最短路径。现输入 4 个结点，且结点 1 到结点 2 的距离为 2,结点 1 到结点 3 的距离为 4,1 到结点 4 的距离为 5,结