基于最短路问题的研究及应用令狐采学姓名：Fanmeng学号：指导老师：摘要最短路问题是图论中的一大问题，对最短路的研究在数学建模和实际生活中具有很重要的实际意义，介绍最短路问题的定义及这类问题的解决办法Dijkstra算法，并且能够在水渠修建实例运用到此数学建模的方法，为我们解决这类图论问题提供了基本思路与方法。
关键字数学建模最短路问题Dijkstra算法水渠修建。
目录第一章．研究背景1第二章．理论基础22.1 定义22.2 单源最短路问题Dijkstra求解:22.2.1 局限性22.2.2 Dijkstra算法求解步骤22.2.3 时间复杂度22.3 简单样例3第三章．应用实例43.1 题目描述43.2 问题分析43.3符号说明43.4 模型假设53.5模型建立与求解53.5.1模型选用53.5.2模型应用及求解53.6模型评价5第四章. 参考文献5第五章．附录6第一章．研究背景在现实生活中中，我们经常会遇到图类问题，图是一种有顶点和边组成，顶点代表对象，在示意图中我们经常使用点或者原来表示，边表示的是两个对象之间的连接关系，在示意图中，我们使用连接两点G点直接按的下端来表示。
顶点的集合是V，边的集合是E的图记为G[V,E] ,连接两点u和v的边用e(u,v)表示[1]。
最短问题是图论中的基础问题，也是解决图类问题的有效办法之一，在数学建模中会经常遇到，通常会把一个实际问题抽象成一个图，然后来进行求的接任意两点之间的最短距离。
因此掌握最短路问题具有很重要的意义。
第二章．理论基础2.1 定义最短路问题（short-path problem ）：若网络中的每条边都有一个数值（长度、成本、时间等），则找出两节点，（通常是源节点和目标节点）之间总权和最小的路径就是最短路问题。
最短路问题是网络理论解决的典型问题之一，可用来解决管道铺设，线路安装，厂区布局和设备更新等实际问题[2]。
2.2 单源最短路问题Dijkstra 求解: 2.2.1局限性Dijkstra 算法不能够处理带有负边的图，即图中任意两点之间的权值必须非负。
2.2.2Dijkstra 算法求解步骤(1).先给图中的点进行编号，确定起点的编号。
(2).得到图的构成，写出写出图的矩阵0000(,)(,)(,)(,)n n n n u u u u G u u u u=(3).根据要求求出发点S 到终点E 的最短距离，那么需要从当前没被访问过的结点集合unvist={u | u {1,2,3...}}n ∈中找到一个距离已经标记的点的集合中vist={u | u {1,2,3...}}n ∈的最短距离，得到这个顶点；(4).利用这个顶点来松弛其它和它相连的顶点距离S 的值(5).重复步骤(2)和(3)，直到再也没有点可以用来松弛其它点，这样我们就得到了由起点S 到其它任意点的最短距离。
2.2.3时间复杂度时间复杂度达到2()O N2.3简单样例给出对应的结点之间的关系注释：其中（A,B）= 2 表示结点A到B 的长度为2第一步：进行编号，假定A点即为起点。
第二步：得到图02151010201115151102071012003105730G=第三步：首先从起点A开始找到距离A最近的点，那就是A点了；第四步：把A点标记到已经用过的的集合{}vist A=用A来更新其它点{,,,}unvist B C D E=到起点的距离得到的集合dist =02151010A B C D E表示起点到B,C,D,E的距离分别为2,15,10,10第五步：重复上述步骤：得到{,}vist A B=,{,,}unvist C D E=,dist =021337A B C D E继续重复上述步骤，最后的到{,,,,}vist A B C D E=,unvist=∅,得到的dist =021336A B C D E，即最短路求解完毕。
第三章．应用实例3.1 题目描述农村的孩子应该都会听到大人们经常谈论这样的问题-------修建水渠。
在我们北方采用深井灌溉，所以说修建水渠更加普遍，因为一般都是水渠直接引流到田地旁边。
经常一些土地需要开发，在这个过程中，我们需要能够将在某一个地点的水源引流到新建的田地里面，这个过程很麻烦，有时候大家很激动的去引流，结果最后修建的水渠并不能满足要求，往往浪费了大量的物力人力和财力，所以现在我们要设计一定的数学模型来帮助农民来规划一下，如何修建的水渠最优，并且给出修建的路径。
通常是通过步长来估计两个点之间的长度，我们通常可以这样理解，每两步可以认为是1米。
给出的点之间的关系描述关系为（其他因素先可以不用考虑）：注：A表示的是总的进水口，其余字母表示的是每块田地的进水口的位置,这只是部分数据。
3.2 问题分析问题是让我们来规划一下水渠该如何来修建的问题，并且已经知道了出水口所在的位置，并且简单的知道了一些点之间的距离，让我们帮农民找到一条最优的水渠来完成引流工作。
既然给出的是关于长度的问题，那么长度一定是很重要的标记量了，那么我们只需要找到一条从总出水到某一块地的修建的距离最短即可。
3.3符号说明3.4 模型假设假设其余条件不会影响水渠修建，比如土壤硬度假设水渠宽度不会对水流量造成影响即水渠内的流量会满足要求3.5模型建立与求解3.5.1模型选用最短路模型最短路模型解决的就是图论中任意两点之间的最短路问题。
3.5.2模型应用及求解我们的指标是（X,Y） = min(x,y) | x∈∈{{,....},{,,...}}L A B y A B首先对数据进行抽取，得到我们所需要的数值，并把它存储到矩阵G这应该是一个9*9的矩阵，其次我们可以按照最短路的模型使用Dijkstra算法来进行求解，得到的值便是S到任一点的最短距离值，最后按照路径还原的思想还原修建的路径即可。
3.6模型评价最短路模型的是行能够较好的解决单源最短路径问题，可以较好的模拟出路径修建，得到的一定是最短的路径，能够达到预期要求的效果，得到的最终结果如附录里“3.应用实例结果输出”所示第四章.参考文献[1]. 韩中庚著，《数学建模方法与应用》，高等教育出版社[2].[3].[美] Frank R.Giordano著《数学建模》（原书第五版）[4].刘晓妍著《基于最短路的设备更新问题的数学建模》河南教育学院学报(自然科学版) 第22卷第四期2013年12月[5].杨启帆、边馥萍著，《数学模型》，浙江大学出版社第五章．附录1.应用实例矩阵011120030040050060010234257312010611121314131001001234 G2004610001020304030021111005060604005122205002334500713330602301260031444060341202.应用实例C++程序#include <iostream>#include <cstring>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <vector>usingnamespacestd;constdouble INF = 0xFFFFFFF;constint MAX_N = 10005;//表示最大有顶点10005个；intn,m;//表示有n个结点；给出了m条边double G[MAX_N][MAX_N];//用邻接矩阵来从这个图doubledist[MAX_N];//表示起点到当前点的最短距离boolvist[MAX_N];intprev[MAX_N];vector <int>getpath(int t){ //路径还原可变长数组类型vector<int> path;for(; t !=-1; t =prev[t]){path.push_back(t);}reverse(path.begin(),path.end());return path;}voidDijkstra(int s){//求得最短路径dist[s]= 0;while(true){int v =-1;double mx = INF;for(inti= 1;i<= n;i++){//挑选出未被标记集合最短的点if(!vist[i]&& mx >dist[i]){mx=dist[i];v =i;}}if(v ==-1){break;}vist[v]=true;for(inti= 1;i<= n;i++){ //用当前的到的值来松弛其他不在标记的集合中的值if(!vist[i]&&dist[i]>dist[v]+G[v][i]){dist[i]=dist[v]+G[v][i];prev[i]= v;}}}}voidinit(){ //初始化值for(inti= 1;i<= n;i++){for(int j = 1; j <= n; j++){G[i][j]= INF;G[i][i]= 0;}dist[i]= INF;vist[i]=false;prev[i]=-1;}}int main(){freopen("data.in","r",stdin);//默认数据读入用data.infreopen("data.out","w",stdout);//输出默认到data.outcin>> n;init();for(inti= 1;i<= n;i++){for(int j = 1; j <= n; j++){cin>> G[i][j];}}Dijkstra(1);for(inti= 1;i<= n;i++){printf("出水口到目标点%d 的最短距离= %.0f\n",i,dist[i]);vector<int> q =getpath(i);令狐采学创作printf("目标点%d 的路径为\n",i);printf("%d",q[0]);for(inti= 1;i<(int)q.size();i++){printf("-> %d ",q[i]);}printf("\n");}return 0;}3.应用实例结果输出出水口到目标点1 的最短距离= 0目标点1 的路径为1出水口到目标点2 的最短距离= 1目标点2 的路径为1-> 2出水口到目标点3 的最短距离= 1目标点3 的路径为1-> 3出水口到目标点4 的最短距离= 1目标点4 的路径为1-> 4出水口到目标点5 的最短距离= 5目标点5 的路径为1-> 2 -> 5出水口到目标点6 的最短距离= 2目标点6 的路径为1-> 4 -> 6出水口到目标点7 的最短距离= 3目标点7 的路径为1-> 4 -> 7出水口到目标点8 的最短距离= 4目标点8 的路径为1-> 4 -> 8出水口到目标点9 的最短距离= 4目标点9 的路径为1-> 2 -> 9令狐采学创作。
