配送说明书101204031..doc

辽宁工业大学
物流运输与配送课程设计(论文)
题目:MATLAB下Dijkstra算法的实现
院(系): 汽车与交通工程学院
专业班级: 物流工程102
学号: 101204031
学生姓名: 王斌
指导教师: 宛剑业
职称: 教授
起止时间: ——

同组同学:秦卫东刘雨祥王家祥王博冯静
课程设计(论文)任务及评语
院(系):汽车与交通工程学院教研室:物流工程教研室
学号
101204031
学生姓名
王斌
专业班级
物流工程102
课程设计(论文)题目
MATLAB下Dijkstra算法的实现
课程设计(论文)任务
在掌握Dijkstra算法的基础上,综合运用《物流运输与配送》、《运筹学》、《物流学》等课程理论知识,学会利用MATLAB软件编制设计程序,提高理论与实际相结合的应用能力。
要求运用节约法进行配送线路设计,解决课程设计指导书上案例3,计算应用MATLAB软件。编写设计程序,并调试运行,完成以下任务:
(1)同组同学每人以一个不同的节点作为出发点手动进行最短路的计算;
(2)利用MATLAB软件编写程序,以案例3的数据作为默认数据对Dijkstra算法程序进行测试;
(3)实现输入数据的界面操作;
(4)输入起始点和终点能够自动计算最短路径里程及最短路径。
完成课程设计说明书。主要内容包括:Dijkstra算法的原理、程序框图、部分主要程序及说明、最终结果、结果分析及任务书上要求完成的内容等。
指导教师评语及成绩
成绩: 指导教师签字:
年月日
目录
1
1
两个指定顶点之间的最短路径 1
Dijkstra算法原理 1
2
3
main框图 3
4
4
4
5
5
7
7
8
9
10
10
11
参考文献 11
物流运输与配送课程设计

物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识,另外也为以后毕业设计工作做一次综合训练,学生应当通过物流运输与配送课程设计达到以下几个目的:
《物流学》、《物流运输与配送》、《运筹学》等课程理论知识的能力。
、配送线路优化的基本方法和基本理论,学会利用MATLAB软件进行程序设计,提高理论与实际相结合的应用能力。
,提高对文献资料的归纳、写作、综合运用能力。

两个指定顶点之间的最短路径
问题如下:给出了一个连接若干个客户的道路网络,在这个网络的两个指定客户间,找一条最短的路线。
以各客户为图G 的顶点,两客户间的直通路为图G 相应两顶点间的边,得图G 。对G 的每一边e,赋以一个实数w(e)—直通路的长度,称为e的权,得到赋权图G 。G 的子图的权是指子图的各边的权和。问题就是求赋权图G 中指定的两个顶点,间的具最小权的轨。这条轨叫做,间的最短路,它的权叫做,间的距离,亦记作。求最短路已有成熟的算法:迪克斯特拉(Dijkstra)算法,其基本思想是按距从近到远为顺序,依次求得到G 的各顶点的最短路和距离,直至(或直至G 的所有顶点),算法结束。
Dijkstra算法原理
Dijkstra算法原理:首先,引进一个辅助向量D,它的每个分量D表示当前所找到的从始点v到每个终点的最短路径的长度。如D[3]=2表示从始径相对最小长度为2。这里强调相对就是说在算法过程中D的值是在不断逼近最终结果但在过程中不一定就等于最短路径长度。它的初始状态为:若从v到
有弧,则D为弧上的权值;否则置D为∞。显然,长度为{∈V} 的路径就是从v出发的长度最短的一条最短路径。此路径为。那么,下一条长度次短的最短路径是哪一条呢?假设该次短路径的终点是,则可想而知,这条路径或者是(v, ),或者是(v, , )。它的长度或者是从v到的弧上的权值,或者是和从到的弧上的权值之和。一般情况下,假设S为已求得最短路径的终点的集合,则可证明:下一条最短路径(设其终点为X)或者是弧