数学建模模最短路

基于最短路问题的研究及应用

姓名： Fanmeng

学号：

指导老师：

摘要

最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。

关键字 数学建模 最短路问题 Dijkstra算法 水渠修建。

目录

第一章．研究背景 ............................................................. 1

第二章．理论基础 ............................................................. 2

定义.................................................................... 2

单源最短路问题Dijkstra求解: ............................................ 2

局限性 .............................................................. 2

Dijkstra算法求解步骤 ............................................... 2

时间复杂度 .......................................................... 2

简单样例 ................................................................ 3

第三章．应用实例 ............................................................. 4

题目描述 ................................................................ 4

问题分析 ................................................................ 4

符号说明 ................................................................. 5

模型假设 ................................................................ 5

模型建立与求解 ........................................................... 5

模型选用 ............................................................. 5

模型应用及求解 ....................................................... 5

模型评价 ................................................................. 5

第四章. 参考文献 ............................................................. 6

第五章．附录 ................................................................. 7

第一章．研究背景

在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。因此掌握最短路问题具有很重要的意义。

第二章．理论基础

定义

最短路问题（short-path problem）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。

单源最短路问题Dijkstra求解:

局限性

Dijkstra算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。

Dijkstra算法求解步骤

(1). 先给图中的点进行编号，确定起点的编号。

(2). 得到图的构成，写出写出图的矩阵

0000(,)(,)(,)(,)nnnnuuuuGuuuu

(3). 根据要求求出发点S到终点E的最短距离，那么需要从当前没被访问过的结点集合unvist={u | u{1,2,3...}}n中找到一个距离已经标记的点的集合中vist={u | u{1,2,3...}}n的最短距离，得到这个顶点；

(4). 利用这个顶点来松弛其它和它相连的顶点距离S的值

(5). 重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S到其它任意点的最短距离。

时间复杂度

时间复杂度达到2()ON

简单样例

给出对应的结点之间的关系

表1为对应的结点之间的关系

长度 A B C D E

A 0 2 15 10 10

B 2 0 11 1 5

C 15 11 1 20 7

D 10 10 20 0 3

E 10 5 7 3 0

注释：其中（A,B）= 2 表示结点A到B 的长度为2

第一步：进行编号，假定A点即为起点。

第二步：得到图

02151010201115151102071012003105730G

第三步：首先从起点A开始找到距离A最近的点，那就是A点了；

第四步：把A点标记到已经用过的的集合{}vistA用A来更新其它点{,,,}unvistBCDE到起点的距离得到的集合

dist = 02151010ABCDE

表示起点到B,C,D,E的距离分别为2,15,10,10

第五步：重复上述步骤：得到{,}vistAB,{,,}unvistCDE,dist = 021337ABCDE

继续重复上述步骤，最后的到{,,,,}vistABCDE,unvist,得到的dist = 021336ABCDE ，

即最短路求解完毕。

第三章．应用实例

题目描述

农村的孩子应该都会听到大人们经常谈论这样的问题-------修建水渠。在我们北方采用深井灌溉，所以说修建水渠更加普遍，因为一般都是水渠直接引流到田地旁边。经常一些土地需要开发，在这个过程中，我们需要能够将在某一个地点的水源引流到新建的田地里面，这个过程很麻烦，有时候大家很激动的去引流，结果最后修建的水渠并不能满足要求，往往浪费了大量的物力人力和财力，所以现在我们要设计一定的数学模型来帮助农民来规划一下，如何修建的水渠最优，并且给出修建的路径。通常是通过步长来估计两个点之间的长度，我们通常可以这样理解，每两步可以认为是1米。给出的点之间的关系描述关系为（其他因素先可以不用考虑）：

表2、描述进水口之间的关系

步数 A B C D E F G H I

A 0 1 1 1 200 300 400 500 600

B 1 0 2 3 4 2 5 7 3

C 1 2 0 10 6 11 12 13 14

D 1 3 10 0 100 1 2 3 4

E 200 4 6 100 0 10 20 30 40

F 300 2 11 1 10 0 50 60 60

G 400 5 12 2 20 50 0 23 34

H 500 7 13 3 30 60 23 0 12

I 600 3 14 4 40 60 34 12 0

注：A表示的是总的进水口，其余字母表示的是每块田地的进水口的位置,这只是部分数据。

问题分析

问题是让我们来规划一下水渠该如何来修建的问题，并且已经知道了出水口所在的位置，并且简单的知道了一些点之间的距离，让我们帮农民找到一条最优的水渠来完成引流工作。既然给出的是关于长度的问题，那么长度一定是很重要的标记量了，那么我们只需要找到一条从总出水到某一块地的修建的距离最短即可。