卢骏鹏配送说明书

《卢骏鹏配送说明书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、辽宁工业大学物流运输与配送课程设计（论文）题目：MATLAB下Dijkstra算法的实现院（系）：汽车与交通工程学院专业班级：物流工程091学号：091204016学生姓名：卢骏鹏指导教师：王殿超职称：助教起止时间：2012.12.17——2012.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.2Dijkstra算法原理2三．Dijkstra算法的操作步骤2四．Dijkstra算法的程序框图34.1菜单程序框图34.2输入程序框图44.3main框图5五．部分主要程序及其说明65.1菜单menu程序65.2原始数据default_dat程序65.3输入数据input_dat程序75.4迪杰斯特拉算法main程序7六．主要任务96.

4、1最短路的计算96.2测试106.2.1测试1106.2.2测试2116.3实现输入数据界面116.4最短路径求取12参考文献1313辽宁工学院课程设计说明书（论文）13辽宁工学院课程设计说明书（论文）MATLAB下Dijkstra算法的实现同组同学：佟连庆，胡冰，苗灵卉，牟东旭一．设计目的物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识，另外也为以后毕业设计工作做一次综合训练，学生应当通过物流运输与配送课程设计达到以下几个目的：1.培养学生综合运用《物流学》、《物流

5、运输与配送》、《运筹学》等课程理论知识的能力。2.培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利用MATLAB软件进行程序设计，提高理论与实际相结合的应用能力。3.能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合运用能力。二．Dijkstra算法的原理2.1两个指定顶点之间的最短路径问题如下：给出了一个连接若干个客户的道路网络，在这个网络的两个指定客户间，找一条最短的路线。以各客户为图G的顶点，两客户间的直通路为图G相应两顶点间的边，得图G。对G的每一边e，赋以一个实数w(e)—直通路的长度，称为e的权，得

6、到赋权图G。G的子图的权是指子图的各边的权和。问题就是求赋权图G中指定的两个顶点，间的具最小权的轨。这条轨叫做，间的最短路，它的权叫做，间的距离，亦记作。求最短路已有成熟的算法：迪克斯特拉（Dijkstra）算法，其基本思想是按距从近到远为顺序，依次求得到G的各顶点的最短路和距离，直至（或直至G的所有顶点），算法结束。2.2Dijkstra算法原理Dijkstra算法原理：首先，引进一个辅助向量D，它的每个分量D13辽宁工学院课程设计说明书（论文）表示当前所找到的从始点v到每个终点的最短路径的长度。如D[3]=2表示从始径相对最小长度为2。这里强调相对

7、就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为：若从v到有弧，则D为弧上的权值；否则置D为∞。显然，长度为{∈V}的路径就是从v出发的长度最短的一条最短路径。此路径为。那么，下一条长度次短的最短路径是哪一条呢？假设该次短路径的终点是，则可想而知，这条路径或者是(v,)，或者是(v,,)。它的长度或者是从v到的弧上的权值，或者是和从到的弧上的权值之和。一般情况下，假设S为已求得最短路径的终点的集合，则可证明：下一条最短路径（设其终点为X）或者是弧(v,x)，或者是中间只经过S中的顶点而最后到达顶点X的路径。

8、因此，下一条长度次短的最短路径的长度必是{∈V-S}其中，D或者是弧(v,)上的权值，或者是(