数学建模模最短路

《数学建模模最短路》由会员分享，可在线阅读，更多相关《数学建模模最短路（11页珍藏版）》请在装配图网上搜索。

1、基于最短路问题得研究及应用姓名: Fanmng 学号: 指导老师： 摘要最短路问题就是图论中得一大问题,对最短路得研究在数学建模与实际生活中具有很重要得实际意义,介绍最短路问题得定义及这类问题得解决办法jtra算法,并且能够在水渠修建实例运用到此数学建模得方法,为我们解决这类图论问题提供了基本思路与方法。关键字 数学建模 最短路问题 Dijkstra算法 水渠修建。目录第一章.研究背景1第二章.理论基础2、1 定义22、2单源最短路问题Djkstra求解：2、1局限性22、2、2Djkstra算法求解步骤22、2、3 时间复杂度22、3 简单样例3第三章.应用实例43、 题目描述3、问题分析4

2、、3符号说明、 模型假设53、5模型建立与求解53、5、1模型选用53、5、2模型应用及求解53、6模型评价5第四章、参考文献第五章.附录7第一章.研究背景 在现实生活中中,我们经常会遇到图类问题,图就是一种有顶点与边组成,顶点代表对象，在示意图中我们经常使用点或者原来表示,边表示得就是两个对象之间得连接关系,在示意图中,我们使用连接两点G点直接按得下端来表示。顶点得集合就是V，边得集合就是E得图记为GV,E ,连接两点与得边用e(,)表示。最短问题就是图论中得基础问题,也就是解决图类问题得有效办法之一,在数学建模中会经常遇到,通常会把一个实际问题抽象成一个图,然后来进行求得接任意两点之间得最

3、短距离。因此掌握最短路问题具有很重要得意义。第二章.理论基础2、1定义最短路问题(sort-ath problm):若网络中得每条边都有一个数值(长度、成本、时间等),则找出两节点,（通常就是源节点与目标节点)之间总权与最小得路径就就是最短路问题。最短路问题就是网络理论解决得典型问题之一,可用来解决管道铺设,线路安装，厂区布局与设备更新等实际问题2。2、 单源最短路问题iktra求解:2、2、1 局限性Dijktra算法不能够处理带有负边得图,即图中任意两点之间得权值必须非负。2、2 jksta算法求解步骤(1)、先给图中得点进行编号,确定起点得编号。（2）、 得到图得构成,写出写出图得矩阵(

4、3)、根据要求求出发点S到终点得最短距离,那么需要从当前没被访问过得结点集合中找到一个距离已经标记得点得集合中得最短距离，得到这个顶点;()、利用这个顶点来松弛其它与它相连得顶点距离S得值(5)、 重复步骤（2)与(),直到再也没有点可以用来松弛其它点,这样我们就得到了由起点S到其它任意点得最短距离。2、2、3时间复杂度时间复杂度达到、3简单样例给出对应得结点之间得关系表1为对应得结点之间得关系长度BCDEA21101B201115C1111207D10120E0573注释:其中(A,B）= 2 表示结点A到B 得长度为2第一步:进行编号，假定A点即为起点。第二步:得到图 第三步:首先从起点A

5、开始找到距离A最近得点，那就就是A点了；第四步:把点标记到已经用过得得集合用A来更新其它点到起点得距离得到得集合表示起点到B,D,E得距离分别为，15,10,1第五步：重复上述步骤:得到,继续重复上述步骤，最后得到,得到得 ,即最短路求解完毕。第三章.应用实例、1 题目描述农村得孩子应该都会听到大人们经常谈论这样得问题-修建水渠。在我们北方采用深井灌溉,所以说修建水渠更加普遍，因为一般都就是水渠直接引流到田地旁边。经常一些土地需要开发，在这个过程中,我们需要能够将在某一个地点得水源引流到新建得田地里面，这个过程很麻烦，有时候大家很激动得去引流，结果最后修建得水渠并不能满足要求,往往浪费了大量得

6、物力人力与财力,所以现在我们要设计一定得数学模型来帮助农民来规划一下，如何修建得水渠最优,并且给出修建得路径。通常就是通过步长来估计两个点之间得长度,我们通常可以这样理解,每两步可以认为就是1米。给出得点之间得关系描述关系为(其她因素先可以不用考虑）: 表2、描述进水口之间得关系步数ABCEFGHIA00500600B1032573C2D4E0340F36642334H5072I6420注：A表示得就是总得进水口，其余字母表示得就是每块田地得进水口得位置,这只就是部分数据。3、问题分析问题就是让我们来规划一下水渠该如何来修建得问题,并且已经知道了出水口所在得位置,并且简单得知道了一些点之间得距

7、离，让我们帮农民找到一条最优得水渠来完成引流工作。既然给出得就是关于长度得问题,那么长度一定就是很重要得标记量了,那么我们只需要找到一条从总出水到某一块地得修建得距离最短即可。3、符号说明由长度构成得矩阵表示从X到得最短距离S总出水口E田地进水口3、4模型假设假设其余条件不会影响水渠修建,比如土壤硬度假设水渠宽度不会对水流量造成影响即水渠内得流量会满足要求、5模型建立与求解3、5、1模型选用最短路模型 最短路模型解决得就就是图论中任意两点之间得最短路问题。3、5、2模型应用及求解我们得指标就是 首先对数据进行抽取,得到我们所需要得数值,并把它存储到矩阵 这应该就是一个99得矩阵，其次我们可以按

8、照最短路得模型使用Dksr算法来进行求解,得到得值便就是S到任一点得最短距离值，最后按照路径还原得思想还原修建得路径即可。、6模型评价最短路模型得就是行能够较好得解决单源最短路径问题,可以较好得模拟出路径修建，得到得一定就是最短得路径，能够达到预期要求得效果,得到得最终结果如附录里“3、 应用实例结果输出”所示第四章、 参考文献1、 韩中庚著,数学建模方法与应用,高等教育出版社2、 、美n、Girdao著数学建模(原书第五版）4、刘晓妍著基于最短路得设备更新问题得数学建模河南教育学院学报(自然科学版) 第2卷 第四期 013年2月、 杨启帆、边馥萍著,数学模型,浙江大学出版社第五章.附录1.

9、应用实例矩阵2. 应用实例C+程序#inlue incude #inclue #nclude #incle #incud mth#incudnaespace td;cons double IN =0xFFFF;onst in M_ = 0005;/ 表示最大有顶点10005个;int n，;/ 表示有n个结点;给出了条边dobl GMX_NMAN;/ 用邻接矩阵来从这个图doub istMAXN;/ 表示起点到当前点得最短距离bool vistAN;it revMAXN;ctor intetpth(int t) /路径还原可变长数组类型 veor path; fr(; != -1； t=pvt

10、) pth、puh_back(t); evee（p、begin(）,ath、en(）; retur pat;od Dijktra（int ) /求得最短路径 dists= 0; whie(tru） itv= -1; oblemx= INF; or(int i ; i di） mx diti； v= ; f(v = 1) reak; vistv = rue; for(nt i = 1; i dsv+Gvi) disti = distv+Gv; prev =v; void init（) /初始化值 or（nt = 1; i = n； +） fr(itj = 1; j n; init()； for(

11、n i= 1;i= n; +) for(in j1; j=n;j+) cin ij； Dijksr(1)； fr(int i = 1； = n; i+) pitf(出水口到目标点 %d得最短距离 = %、fn,i，dti); vector q epath(i)； rintf(目标点 %d 得路径为n,i); printf(d，q0); fo(int 1; i （int）q、sze(); i+) pitf( % ,qi）； prinf(); return 0;3. 应用实例结果输出出水口到目标点1 得最短距离 = 目标点1 得路径为1出水口到目标点得最短距离 =目标点 2 得路径为 2 出水口到目标点3 得最短距离 = 1目标点 得路径为1- 3 出水口到目标点 4 得最短距离 1目标点 得路径为1 4出水口到目标点 得最短距离 5目标点5 得路径为1 -5出水口到目标点 6 得最短距离 = 2目标点 6得路径为1 4 -6 出水口到目标点7 得最短距离 = 3目标点 得路径为1- 7 出水口到目标点 8 得最短距离 目标点 得路径为- 4 - 出水口到目标点 9得最短距离 = 目标点 9得路径为1-