牟东旭物流运输与配送最短路问题案例3任务书

《牟东旭物流运输与配送最短路问题案例3任务书》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、辽宁工业大学物流运输与配送课程设计（论文）题目：MATLAB下Dijkstra算法的实现院（系）：汽车与交通工程学院专业班级：物流工程092学号：091204046学生姓名：牟东旭指导教师：宛剑业职称：教授起止时间：2012.12.17—2012.12.28课程设计（论文）任务及评语院（系）：汽车与交通工程学院　　　教研室：物流工程教研室学号091204046学生姓名牟东旭专业班级物流工程092课程设计（论文）题目MATLAB下Dijkstra算法的实现课程设计（论文）任务在掌握Dijkstra算法的基础上，综合运用《物流运输与配送

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

3、a算法的原理、程序框图、部分主要程序及说明、最终结果、结果分析极任务书上要求完成的内容等。指导教师评语及成绩成绩：指导教师签字：年月日辽宁工学院课程设计说明书（论文）目录一．设计目的1二．Dijkstra算法的原理12.1Dijkstra算法原理1适用条件与限制1算法流程12.2 Dijkstra算法22.3Dijkstra算法思想22.4 Dijkstra算法具体步骤2三.程序框图2四．主要程序说明34.1菜单menu程序44.2原始数据default_dat程序54.3输入数据input_dat程序54.4迪杰斯特拉算法main

4、程序5五．任务75.1手动计算75.2测试85.2.1测试185.2.2测试295.2.2测试395.3数据输入105.4计算最短路径11参考文献1111辽宁工学院课程设计说明书（论文）MATLAB下Dijkstra算法的实现一．设计目的物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识，另外也为以后毕业设计工作做一次综合训练，学生应当通过物流运输与配送课程设计达到以下几个目的：1.培养学生综合运用《物流学》、《物流运输与配送》、《运筹学》等课程理论

5、知识的能力。2.培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利用MATLAB软件进行程序设计，提高理论与实际相结合的应用能力。3.能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合运用能力。同组组员：卢骏鹏，佟连庆，苗灵卉，胡冰。二．Dijkstra算法的原理2.1Dijkstra算法原理Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的

6、点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。如果用本算法求一个图中全部的最短路，则要以每个点为源调用一次Dijkstra算法。适用条件与限制§有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边。§用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测)算法流程在以下说明中，s为源，w[u,v]为点u和v之间的边的长度，结果保存在dist[]§初始化：

7、源的距离dist[s]设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。§循环n-1次：§在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。11辽宁工学院课程设计说明书（论文）§对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果dist[u]+w[u,v]

8、型最短路算法，用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短路径的最优解，但由于它遍历计算的节点很多，所以效率低。Dijkstra算法是很有代表性的最