配送说明书101204031.doc

辽 宁 工 业 大 学 物流运输与配送 课程设计（论文）题目：MATLAB下Dijkstra算法的实现院（系）： 汽车与交通工程学院 专业班级： 物流工程102 学 号： 101204031 学生姓名： 王斌 指导教师： 宛剑业 职 称： 教授 起止时间： 2013.12.162013.12.27 同组同学：秦卫东 刘雨祥 王家祥 王博 冯静课程设计（论文）任务及评语院（系）：汽车与交通工程学院 教研室：物流工程教研室学 号101204031学生姓名王斌专业班级物流工程102课程设计（论 文）题 目MATLAB下Dijkstra算法的实现课程设计（论文）任务在掌握Dijkstra算法的基础上，综合运用物流运输与配送、运筹学、物流学等课程理论知识，学会利用MATLAB软件编制设计程序，提高理论与实际相结合的应用能力。 要求运用节约法进行配送线路设计，解决课程设计指导书上案例3，计算应用MATLAB软件。编写设计程序，并调试运行，完成以下任务：（1）同组同学每人以一个不同的节点作为出发点手动进行最短路的计算； （2）利用MATLAB软件编写程序，以案例3的数据作为默认数据对Dijkstra算法程序进行测试；（3）实现输入数据的界面操作；（4）输入起始点和终点能够自动计算最短路径里程及最短路径。完成课程设计说明书。主要内容包括：Dijkstra算法的原理、程序框图、部分主要程序及说明、最终结果、结果分析及任务书上要求完成的内容等。指导教师评语及成绩成绩： 指导教师签字： 年 月 日辽 宁 工 学 院 课 程 设 计 说 明 书（论 文）目 录一设计目的1二Dijkstra算法的原理12.1 两个指定顶点之间的最短路径12.2 Dijkstra算法原理1三Dijkstra算法的操作步骤2四Dijkstra算法的程序框图34.1 main框图3五部分主要程序及其说明45.1菜单menu程序45.2原始数据default_dat程序45.3输入数据input_dat程序55.4迪杰斯特拉算法main程序5六主要任务76.1最短路的计算76.2测试86.3实现输入数据界面96.4最短路径求取106.5结果分析106.6课设感受11参考文献11物流运输与配送课程设计一设计目的物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识，另外也为以后毕业设计工作做一次综合训练，学生应当通过物流运输与配送课程设计达到以下几个目的：1.培养学生综合运用物流学、物流运输与配送、运筹学等课程理论知识的能力。2.培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利用MATLAB软件进行程序设计，提高理论与实际相结合的应用能力。3.能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合运用能力。二Dijkstra算法的原理2.1 两个指定顶点之间的最短路径问题如下：给出了一个连接若干个客户的道路网络，在这个网络的两个指定客户间，找一条最短的路线。以各客户为图G 的顶点，两客户间的直通路为图G 相应两顶点间的边，得图G 。对G 的每一边e，赋以一个实数w(e)直通路的长度，称为e的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点，间的具最小权的轨。这条轨叫做，间的最短路，它的权叫做，间的距离，亦记作 。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距从近到远为顺序，依次求得到G 的各顶点的最短路和距离，直至（或直至G 的所有顶点），算法结束。2.2 Dijkstra算法原理Dijkstra算法原理：首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点的最短路径的长度。如D3=2表示从始径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到有弧，则D为弧上的权值；否则置D为。显然，长度为 V 的路径就是从v出发的长度最短的一条最短路径。此路径为。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是，则可想而知，这条路径或者是(v, )，或者是(v, , )。它的长度或者是从v到的弧上的权值，或者是和从到的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是V-S其中，D或者是弧(v, )上的权值，或者是 (S)和弧(,)上的权值之和。 迪杰斯特拉算法描述如下：（1）arcs表示弧上的权值。若不存在，则置arcs为。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点可能达到的最短路径长度的初值为 Locate Vex(G,v),i V； （2）选择vj，使得V-S；（3）修改从v出发到集合V-S上任一顶点可达的最短路径长度。三Dijkstra算法的操作步骤Dijkstra算法的操作步骤：1初始时令回路，T=其余顶点，T中顶点对应的距离值若存在，为弧上的权值，若不存在，为 ； 2从T中选取一个其距离值为最小的顶点W且不在S中，加入到S中； 3. 对T中顶点的距离值进行修改：若加进W作中间顶点，从到的距离值比不加W的路径要短，则修改此距离值；4. 重复上述步骤2、3直到S中包含所有顶点，即S=T为止。接下来的问题就是如何表示两个节点之间的距离。经过查阅资料结合以前的数据结构知识可以知道表示方法有邻接表、邻接矩阵等，MATLAB语言本身最初就是用于矩阵计算，对矩阵支持有先天性的优势，因此我认为邻接矩阵是最好的表达方式。对于矩阵中的任意位置的数adj_mat(i,j)的值代表从节点i到节点j的长度。程序中默认使用的是无向图，即adj_mat(i,j)的值与adj_mat(j,i)的相等。但实际上，dijkstra对图是有向还是无向并不作要求，因此对于有向图，算法也能正确工作。不过为了输入上的简便故采用无向图。四Dijkstra算法的程序框图4.1 main框图main程序是这个系统的主程序，它完成的从任一结点开始到指定的结点为止的最短路程。main框图如下图图3main框图所示。设定初始解计算每个点到初始点的距离解集是否为空计算最近的点，并设为下次的初始解输出结果图1 main框图五部分主要程序及其说明5.1菜单menu程序choice = input(欢迎来到dijkstra算法求取最短路径系统n请选择:n1.使用默认数据 n 2.输入数据n3.查看数据n 4.求取路径5.退出程序n );elseif choice = 3disp(adj_mat); elseif choice = 4sta = input(请输入起始结点:);dst = input(请输入目的地:);if sta = dstfprintf(起始结点与目的结点不能相同rn);elseleng,path = main program(adj_mat , sta , dst); fprintf(最短路径为%dn,leng);k = length(path);fprintf(经过路径为:);for i = 1:1:k-1fprintf(%d -,path(i);endfprintf(%dn,path(k);endend该段程序完成的是从菜单界面进入程序并选择完成的任务。当输入值为1时，程序默认使用原始数据程序即default_dat，并在界面上输出默认数据已被启用。当输入值为2时，程序调用输入程序即input_dat。当输入值为3时，程序输出数据，并在界面上显示。当输入值为4时，程序调用迪杰斯特拉算法程序即main，并在界面上输入起始点和目的点，通过main的计算，能输出最短路径和经过的路径。当输入值为5时，退出程序。5.2原始数据default_dat程序function adj_mat=default_dat() %定义原始数据函数length=10; %定义结点个数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; %原始数据该段程序通过定义结点个数来确定邻接矩阵的宽度，并能输入案例上的的数据，用其来进行测试。5.3输入数据input_dat程序function adj_mat =input_dat() %定义输入数据函数length = input(请输入节点的数量 ); %定义结点个数adj_mat=zeros(length); %定义一个邻接矩阵for i =1:1:length for j =i:1:lengthif i = jfprintf(请输入结点%d到结点%d的长度(没有则输入0),i,j)adj_mat(i,j) = input(:); %输入结点间的距离if adj_mat(i,j) = 0adj_mat(i,j) = inf;endadj_mat(j,i) = adj_mat(i,j); %对称成为一个完整的对称矩阵endendend 该段程序完成的是输入数据的过程，通过在界面上输入的结点数，以及从各结点到其后面的结点之间的距离，在对输入的数据进行对称，使其成为一个完整的矩阵，为以后的计算做铺垫。5.4迪杰斯特拉算法main程序m=length(adj_mat); %定义m的长度lengs =linspace(0,0,m); %产生行矢量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循环求起始点到各邻点的距离index = 1; %标号for i = 1:1:m if i = sta min = inf; %让最小值min为for j = 1:1:m if lengs(j) = mink = j; min = lengs(j); end end %for循环求最小值，并将lengs(j)的值赋给min，最后确定距起始点最近的点know(index) = k; index=index+1;for j = 1:1:m if (lengs(i) + adj_mat(i,j) 5i=5 ，M=1,2,3,4,6,7,9,10；，i=4，即8 -4i=4 ，M=1,2,3,6,7,9,10；，i=7，即8 -7i=7 ，M=1,2,3,6,9,10； ，i=9，即8 -9 i=9 ，M=1,2,3,6,10；，i=10，即8 -11i=10，M=1,2,3,6;；，i=3，即8 -3i=3，M=1,2,6;，i=6，即8 -6i=6，M=1,2;，i=1，即8 -1i=1，M=2;，i=2，即8 -2最后得到的具体结果如下所示：起点为8点，终点为1点的最短距离为16，其路径为8 -1或8 -4-1起点为8点，终点为2点的最短距离为18，其路径为8 -2。起点为8点，终点为3点的最短距离为12，其路径为8 -3。起点为8点，终点为4点的最短距离为7，其路径为8 -4。起点为8点，终点为5点的最短距离为6，其路径为8 -5。起点为8点，终点为6点的最短距离为14，其路径为8 -6或8 -5 -6起点为8点，终点为7点的最短距离为8，其路径为8 -7。起点为8点，终点为9点的最短距离为11，其路径为8 -9。起点为8点，终点为10点的最短距离为11，其路径为8 -10。6.2测试以案例3的数据作为默认数据对Dijkstra算法程序进行测试。现取8点为起始点，以4点为终点。其手动计算结果为最短路径长度为7，其路径是8-4。通过MATLAB计算得到结果如下图2测试数据的结果1所示。图2 测试数据的结果16.3实现输入数据界面进行菜单选择的界面操作如图3 菜单主要选择操作界面所示。在该界面可以完成使用默认数据，输入数据，查看数据，求取路径和退出程序等功能。而且使用该界面能更直观的让使用者使用。图3 菜单主要选择操作界面 以下是实现输入数据与查看数据的任务，在该过程中，可以输入结点的数量，并能输入各结点之间的距离，显示一个对称的矩阵，为以后的求解做准备。其具体的操作步骤如图4 输入新的数据所示。图4 输入新的数据6.4最短路径求取该程序可以完成输入起始点和终点能够自动计算最短路径里程及最短路径。现输入4个结点，且结点1到结点2的距离为2，结点1到结点3的距离为4，结点1到结点4的距离为5，结点2到结点3的距离为6，结点2到结点4的距离为2，结点3到结点4的距离为3。现计算结点1到结点4的距离，其最短路径为4，路径是1 -2-4。使用MATLAB程序计算其结果如图5计算的结果所示。图5 计算的结果6.5结果分析MATLAB下Dijkstra算法的实现中，首先是开始弄给定具体距离能求