GIS工程与应用报告-最佳路径.doc

GIS工程与应用课 程 实 验 报 告 项目名称：最佳路径小组成员：学生学号：2009070,200920090指导教师：完成日期：2013-1-21、 背景最短最优化路径问题是一个重要的问题，也是地理信息系统、通信、物流管理、计算机科学等领域的研究热点。目前，国内外学者对此问题进行了大量的研究，在这些研究成果中，绝大部分都是基于静态网络的，也就是说路径寻优中网络弧段的权值是固定不变的，然而实际生活中的很多问题，其网络弧段的权值是随时间变化的，比如道路交通网络和通信网络。本文主要基于地理信息系统GIS，对校园网络中的两点之间的最短最优化路径进行实现。2、 意义 近几十年来，静态网络最短路径算法已经得到充足的发展，但在现实生活中很多应用领域如110报警、119火警、医疗救护等，都需要尽快获得到达目得地的最快路径，以便处理突发事故。相对于静态最短路径算法而言，基于GIS的时变最短路径成果还很少，时变最短路径算法能与全球定位系统、GIS和ITS技结合在一起，综合每条道路不同时段的不同路况，找出最短最优的路径。本文就最简单最基本的校园两点之间的最短最优化路径，做了几个简单的功能实现。三、系统功能 输入（10）个校园出发点，每两个地点之间有对应的距离和费时（可以不能到达），要求实现如下程序：）给出任意两个校园出发点之间的最短距离，及其到达方式；）给出任意两个校园出发点之间的最少用时，及其到达方式；）权衡距离和费用，给出任意两个城市之间的最优路径，及其到达方式；PS：1. 距离矩阵和费用矩阵由同学自己给出；2. 题 c)的最优路径由自己定义。四算法设计 欲求得每一对顶点之间的最短路径，解决这一问题的办法是采用弗洛伊德算法。 弗洛伊德算法仍从图的带权邻接矩阵出发，其主要思想是：设集合S的初始状态为空集合，然后依次向集合S中加入顶点V0,V1,V2，Vn-1，每次加入一个顶点，我们用二维数组D保存每一对顶点之间的最短路径的长度，其中，Dij存放从顶点Vi到Vj的最短路径的长度。在算法执行中，Dij被定义为：从Vi到Vj的中间只经过S中的顶点的所有可能的路径中最短路径的长度（如果从Vi到Vj中间只经过S中的顶点当前没有路径相通，那么dij为一个大值MaxNum）。即dij中保存的是从Vi到Vj的“当前最短路径”的长度。每次加入一个新的顶点，Vi和Vj之间可能有新的路径产生，将它和已经得到的从Vi到Vj的最短路径相比较，dij的值可能需要不断修正，当S=V时，dij的值就是从Vi到Vj的最短路径。因为初始状态下集合S为空集合，所以初始化Dij=Aij（Aij是图的邻接矩阵）的值是从Vi直接邻接到Vj，中间不经过任何顶点的最短路径。当S中增加了顶点V0,那么D(0)ij的值应该是从Vi到Vj，中间只允许经过v0的当前最短路径的长度。为了做到这一点，只需对D(0)ij作如下修改：D(0)ij=minDij,Di0+D0j一般情况下，如果D(k-1)ij是从Vi到Vj，中间只允许经过 V0,V1,V2，Vk-1的当前最短路径的长度，那么，当S中加进了Vk，则应该对D进行修改如下: D(k)ij=minD(k-1)ij,D(k-1)ik+D(k-1)kj五概要设计1.数据结构 二维数组来表示邻接矩阵，数组中存储元素表示邻接点之间的距离，或费时。2.抽象数据类型 有向图3.函数接口 Void main() 主函数 Void Dispmat() 输出邻接矩阵函数Void Floyed() 计算最短路径函数Void Dispath() 输出最短路径函数六详细设计Main 函数的流程图如下：结束将矩阵初始化，矩阵元素均为输入校园出发点个数和弧数g.n 和g.e构造距离矩阵 开始g.edgesij=Aij;DispMat(g)Floyd(g)构造时间矩阵g.edgesij=BijDispMat(g)Floyd(g)输入权值系数a0和b0构造矩阵g.edgesij=CijDispMat(g)Floyd(g)DispMat(MGraph g) 函数流程图如下：ig.nNYYEND开始g.edgesij=INFprintfprintf(%.2lf,g.edgesij)NDispath(double AMAXV,int pathMAXV,int n)函数流程图如下： YNAij=INFYNYY开始 i=0,j=0injnprintf(从%d到%d的路径为:,i,j);printf(%d,i); ppath(path,i,j);printf(%d,j);printf(t路径长度为:%.2lfn,(double)Aij);i!=jprintf(从%d到%d没有路径n,i,j)j+结束Floyd(MGraph g)函数流程图如下： 开始injnYNYNi+i=0,j=0Aij=g.edgesij;pathij=-1;j+K=0,i=0,j=0 knprintf(n输出最短路径:n);Dispath(A,path,n); /输出最短路径结束Ni + inY jAik+Akjj +NAij=Aik+Akj;pathij=k;Y七运行结果显示首先请输入校园出发点个数和弧数(整型数据):4 8。1.下面计算任意两个出发点之间的最短距离： 2.下面计算任意两个校园出发点之间的最少用时:3.权衡距离和时间，给出任意两个校园出发点之间的最优路径，及其到达方式。此时定义最短路径为两邻接点之间的距离乘以a0与两邻接点之间的费用乘以b0的和.六附件附有源程序如下：#include#define INF 32767typedef int InfoType;#define MAXV 100 /最大顶点个数/以下定义邻接矩阵类型typedef structint no; /顶点编号InfoType info; /顶点其他信息，这里用于存放边的权值VertexType; /顶点类型typedef struct /图的定义double edgesMAXVMAXV; /邻接矩阵int n,e; /顶点数，弧数VertexType vexsMAXV; /存放顶点信息MGraph; /图的邻接矩阵类型void DispMat(MGraph g)/输出邻接矩阵Gint i,j;for(i=0;ig.n;i+)for(j=0;jg.n;j+)if(g.edgesij=INF)printf(%3s,);else printf(%.2lf,g.edgesij);printf(n);void ppath(int pathMAXV,int i,int j)int k;k=pathij;if(k=-1)return;ppath(path,i,k);printf(%d,k); ppath(path,k,j);void Dispath(double DistanceMAXV,int pathMAXV,int n)int i,j;for(i=0;in;i+)for(j=0;jn;j+)if(Distanceij=INF)if(i!=j)printf(从%d到%d没有路径n,i,j);else printf(从%d到%d的路径为:,i,j); printf(%d,i);ppath(path,i,j);printf(%d,j);printf(t路径长度为:%.2lfn,(double)Distanceij);/采用弗洛伊德算法求每对顶点之间的最短路径void Floyd(MGraph g)double DistanceMAXVMAXV;int pathMAXVMAXV;int i,j,k,n=g.n;for(i=0;in;i+)for(j=0;jn;j+)Distanceij=g.edgesij;pathij=-1;for(k=0;kn;k+)for(i=0;in;i+)for(j=0;jDistanceik+Distancekj)Distanceij=Distanceik+Distancekj;pathij=k;printf(n输出最短路径:n);Dispath(Distance,path,n); /输出最短路径void main()int i,j,u=0,m,k;MGraph g;double DistanceMAXVMAXV,TimeMAXVMAXV;double CMAXVMAXV,a0,b0,num;for(k=0;kMAXV;k+)for(m=0;mMAXV;m+)Distancekm=INF;for(k=0;kMAXV;k+)for(m=0;mMAXV;m+)Timekm=INF;for(k=0;kMAXV;k+)for(m=0;mMAXV;m+)Ckm=INF; printf(请输入校园出发点个数和弧数：n); scanf(%d %d,&g.n,&g.e);printf(1.下面计算任意两个出发点之间的最短距离：n);printf( 请输入距离矩阵的边(以-1 -1 -1作为结束标志):n); while(1) scanf(%d,&i); scanf(%d,&j);scanf(%lf,&num); if(i=-1 & j=-1 & num=-1) break; if(i=g.n) | (j=g.n) printf(输入错误!); Distanceij=Distanceji=num; for(i=0;ig.n;i+)for(j=0;jg.n;j+)g.edgesij=Distanceij;printf(n);printf(有向图G的邻接矩阵:n);DispMat(g);Floyd(g);printf(n);printf(2.下面计算任意两个出发点之间的费用：n); printf( 请输入费用矩阵的边(以-1 -1 -1作为结束标志):n); while(1) scanf(%d,&i); scanf(%d,&j);scanf(%lf,&num); if(i=-1 & j=-1 & num=-1) break; if(i=g.n) | (j=g.n) printf(输入错误!); Timeij=Timeji=num; for(i=0;ig.n;i+)for(j=0;j0 & b00 & a0+b0=1 a0和b0都为小数):n); scanf(%lf,&a0); scanf(%lf,&b0); if(a0=-1 & b0=-1) break; for(k=0;kg.