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

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

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

3、容等。指导教师评语及成绩成绩： 指导教师签字： 年 月 日辽 宁 工 学 院 课 程 设 计 说 明 书（论 文）目录一设计目的1二Dijkstra算法的原理12.1Dijkstra算法原理1适用条件与限制1算法流程12.2 Dijkstra算法22.3 Dijkstra算法思想22.4 Dijkstra算法具体步骤2三. 程序框图2四主要程序说明34.1菜单menu程序44.2原始数据default_dat程序54.3输入数据input_dat程序54.4迪杰斯特拉算法main程序5五 任务75.1手动计算75.2测试85.2.1测试185.2.2测试295.2.2测试395.3数据输入10

4、5.4计算最短路径11参考文献1111MATLAB下Dijkstra算法的实现一设计目的物流运输与配送课程设计是在学生完成物流运输与配送课程学习后必修的教学环节。它一方面要求学生在设计中能初步学会综合运用过去所学的全部知识，另外也为以后毕业设计工作做一次综合训练，学生应当通过物流运输与配送课程设计达到以下几个目的：1.培养学生综合运用物流学、物流运输与配送、运筹学等课程理论知识的能力。2.培养学生初步掌握配送中心选址、配送线路优化的基本方法和基本理论，学会利用MATLAB软件进行程序设计，提高理论与实际相结合的应用能力。3.能够进一步强化学生收集整理资料的能力，提高对文献资料的归纳、写作、综合

5、运用能力。同组组员：卢骏鹏，佟连庆，苗灵卉，胡冰。二Dijkstra算法的原理2.1Dijkstra算法原理Dijkstra算法是一种求单源最短路的算法，即从一个点开始到所有其他点的最短路。其基本原理是：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。不过根据这个原理，用Dijkstra求最短路的图不能有负权边，因为扩展到负权边的时候会产生更短的距离，有可能就破坏了已经更新的点距离不会改变的性质。 如果用本算法求一个图中全部的最短路，则要以每个点为源调用一次Dijkstra

6、算法。 适用条件与限制 有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边。 用来求最短路的图中不能存在负权边。(可以利用拓扑排序检测) 算法流程在以下说明中，s为源，wu,v为点u和v之间的边的长度，结果保存在dist 初始化：源的距离dists设为0，其他的点距离设为无穷大，同时把所有的点的状态设为没有扩展过。 循环n-1次： 在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。 对于每个与u相邻的点v，执行Relax(u,v)，也就是说，如果distu+wu,v,path(i);endfprintf(%dn,path(k);endend该段程序完成的是从菜单界面

7、进入程序并选择完成的任务。当输入值为1时，程序默认使用原始数据程序即default_dat，并在界面上输出默认数据已被启用。当输入值为2时，程序调用输入程序即input_dat。当输入值为3时，程序输出数据，并在界面上显示。当输入值为4时，程序调用迪杰斯特拉算法程序即main，并在界面上输入起始点和目的点，通过main的计算，能输出最短路径和经过的路径。当输入值为5时，退出程序。4.2原始数据default_dat程序function adj_mat=default_dat() %定义原始数据函数length=10; %定义结点个数adj_mat=zeros(length); %邻接矩阵adj

8、_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; %原始数据该段程序通过定义结点个数来确定邻接矩阵的宽度，并能输入案例上的的数据，用其来进行测试。4.3输入数据input_dat程序function adj_mat =input_dat() %定义输入数据函数length = input(请输入节点的数量 ); %定义结点个数adj_ma

9、t=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 该段程序完成的是输入数据的过程，通过在界面上输入的结点数，以及从各结点到其后面的结点之间的距离，在对输入的数据进行对称，使其成为一个完

10、整的矩阵，为以后的计算做铺垫。4.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; m

11、in = 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) 1。通过MATLAB计算得到结果如下图2 测试结果1 所示。图 2 测试结果15.2.2测试2现取5点为起始点，以2点为终点。其手动计算结果为最短路径长度为16，其路径是5 -6 -2。通过MATLAB计算得到结果如下图3 测试结果 2 所示。图3 测试结果25.2.2测试3现取5点为起始点，以8点为终点。其手动计算结果为最

12、短路径长度为6，其路径是5 -8。通过MATLAB计算得到结果如下图4 测试结果 3 所示。图 4 测试35.3数据输入进行菜单选择的界面操作如图 5菜单选择界面所示。在该界面可以完成使用默认数据，输入数据，查看数据，求取路径和退出程序等功能。而且使用该界面能更直观的让使用者使用。图 5 菜单选择界面以下是实现输入数据与查看数据的任务，在该过程中，可以输入结点的数量，并能输入各结点之间的距离，显示一个对称的矩阵，为以后的求解做准备。其具体的操作步骤如图6 输入数据 所示。图6输入数据5.4计算最短路径该程序可以完成输入起始点和终点能够自动计算最短路径里程及最短路径。现输入4个结点，且结点1到结点2的距离为44，结点1到结点3的距离为16，结点1到结点4的距离为23，结点2到结点3的距离为5，结点2到结点4的距离为9，结点3到结点4的距离为3。现计算结点1到结点4的距离，其最短路径为5，路径是1 -3-4。使用MATLA