物流运输与配送说明书

1、辽 宁 工 业 大 学 物流运输与配送 课程设计（论文）题目：MATLAB下Dijkstra算法的实现院（系）： 汽车与交通工程学院 专业班级： 物流工程 091 学 号： 091204016 学生姓名： 卢骏鹏 指导教师： 王殿超 职 称： 助教 起止时间： 2012.12.172012.12.28 课程设计（论文）任务及评语院（系）：汽车与交通工程学院 教研室：物流工程教研室学 号091204016学生姓名卢骏鹏专业班级物流工程091课程设计（论 文）题 目MATLAB下Dijkstra算法的实现课程设计（论文）任务在掌握Dijkstra算法的基础上，综合运用物流运输与配送、运筹学、物流学

2、等课程理论知识，学会利用MATLAB软件编制设计程序，提高理论与实际相结合的应用能力。 要求运用节约法进行配送线路设计，解决课程设计指导书上案例3，计算应用MATLAB软件。编写设计程序，并调试运行，完成以下任务：（1）同组同学每人以一个不同的节点作为出发点手动进行最短路的计算； （2）利用MATLAB软件编写程序，以案例3的数据作为默认数据对Dijkstra算法程序进行测试；（3）实现输入数据的界面操作；（4）输入起始点和终点能够自动计算最短路径里程及最短路径。完成课程设计说明书。主要内容包括：Dijkstra算法的原理、程序框图、部分主要程序及说明、最终结果、结果分析及任务书上要求完成的内

3、容等。指导教师评语及成绩成绩： 指导教师签字： 年 月 日辽 宁 工 学 院 课 程 设 计 说 明 书（论 文）目录一设计目的1二Dijkstra算法的原理12.1 两个指定顶点之间的最短路径12.2 Dijkstra算法原理2三Dijkstra算法的操作步骤2四Dijkstra算法的程序框图34.1菜单程序框图34.2输入程序框图44.3 main框图5五部分主要程序及其说明65.1菜单menu程序65.2原始数据default_dat程序65.3输入数据input_dat程序75.4迪杰斯特拉算法main程序7六主要任务96.1最短路的计算96.2测试106.2.1测试1106.2.2测

4、试2116.3实现输入数据界面116.4最短路径求取12参考文献1313MATLAB下Dijkstra算法的实现同组同学：佟连庆，胡冰，苗灵卉，牟东旭一设计目的物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识，另外也为以后毕业设计工作做一次综合训练，学生应当通过物流运输与配送课程设计达到以下几个目的：1.培养学生综合运用物流学、物流运输与配送、运筹学等课程理论知识的能力。2.培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利用MATLAB软件进行程序设计，提高理论与实际相结合的应用能力。3

5、.能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合运用能力。二Dijkstra算法的原理2.1 两个指定顶点之间的最短路径问题如下：给出了一个连接若干个客户的道路网络，在这个网络的两个指定客户间，找一条最短的路线。以各客户为图G 的顶点，两客户间的直通路为图G 相应两顶点间的边，得图G 。对G 的每一边e，赋以一个实数w(e)直通路的长度，称为e的权，得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点，间的具最小权的轨。这条轨叫做，间的最短路，它的权叫做，间的距离，亦记作 。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，

6、其基本思想是按距从近到远为顺序，依次求得到G 的各顶点的最短路和距离，直至（或直至G 的所有顶点），算法结束。2.2 Dijkstra算法原理Dijkstra算法原理：首先，引进一个辅助向量D，它的每个分量D表示当前所找到的从始点v到每个终点的最短路径的长度。如D3=2表示从始径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到有弧，则D为弧上的权值；否则置D为。显然，长度为 V 的路径就是从v出发的长度最短的一条最短路径。此路径为。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是，则可想而知，

7、这条路径或者是(v, )，或者是(v, , )。它的长度或者是从v到的弧上的权值，或者是和从到的弧上的权值之和。 一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。因此，下一条长度次短的最短路径的长度必是V-S其中，D或者是弧(v, )上的权值，或者是 (S)和弧(,)上的权值之和。 迪杰斯特拉算法描述如下：（1）arcs表示弧上的权值。若不存在，则置arcs为。S为已找到从v出发的最短路径的终点的集合，初始状态为空集。那么，从v出发到图上其余各顶点可能达到的最短路径长度的初值为 Loc

8、ate 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为止。四Dijkstra算法的程序框图4.1菜单程序框图主菜单的程序是使界面上直接显示所需完成的内容，

9、主要完成默认数据导入，输入数据，查看数据，求取路径，退出程序的任务，其具体程序的框图如下图 图1 菜单程序menu框图 所示。图1 菜单menu程序框图4.2输入程序框图 输入程序是为了完成从外界输入数据形成一个新的邻接矩阵，产生一组新的数据进行最短路的求解。输入程序框图如下图 图2 输入input_dat程序框图 所示。图2 输入input_dat程序框图4.3 main框图main程序是这个系统的主程序，它完成的从任一结点开始到指定的结点为止的最短路程。main框图如下图 图3 main框图 所示。图3 main框图五部分主要程序及其说明5.1菜单menu程序choice = input(

10、'欢迎来到dijkstra算法求取最短路径系统n请选择:n1.使用默认数据 2.输入数据n3.查看数据 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('

11、最短路径为%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时，程序调用迪杰斯特拉算法程序即m

12、ain，并在界面上输入起始点和目的点，通过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)=1

13、7;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,

14、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

15、 = 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

16、= 1:1:m if (lengs(i) + adj_mat(i,j) < lengs(j) lengs(j) = lengs(i) + adj_mat(i,j); paths(j) = i; end end %for循环球最短路并确定结点end end %循环计算，求取最短路的距离该段程序是完成dijkstra算法的主要程序。在该段程序中先定义一个起点，再从起点出发将起点的邻接矩阵求出，并从中找出距离起点最近的点作为下一个起点，再从该起点出发求其邻接矩阵，找出该邻接矩阵以及上一个邻接矩阵中除该点外的其他距离中最小的值所表示的结点作为新的起点，以此类推，直到求到目的结点为止。如此即可完成

17、dijkstra算法，求出从已知起点到目的点的最短距离及其具体的路径。六主要任务6.1最短路的计算选择节点10为基点可得： ，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 -

18、>3->1，M=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

19、点，终点为6点的最短距离为16，其路径为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 所示。图4 测试结果16.2.2测试2现取10点为起始点，以8点为终点。其手动计算结果为最短路径长度为11，其路径是10 ->8。通过MATLAB计算得到结果如下图5 测试结果2 所示。图5 测试结果