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

《GIS工程与应用报告-最佳路径》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《GIS工程与应用》课程实验报告项目名称：最佳路径小组成员：学生学号：2009070,200920090指导教师：完成日期：2013-1-2一、背景最短最优化路径问题是一个重要的问题，也是地理信息系统、通信、物流管理、计算机科学等领域的研究热点。目前，国内外学者对此问题进行了大量的研究，在这些研究成果中，绝大部分都是基于静态网络的，也就是说路径寻优中网络弧段的权值是固定不变的，然而实际生活中的很多问题，其网络弧段的权值是随时间变化的，比如道路交通网络和通信网络。本文主要基于地理信息系统GIS，对校园

2、网络中的两点之间的最短最优化路径进行实现。二、意义近几十年来，静态网络最短路径算法已经得到充足的发展，但在现实生活中很多应用领域如110报警、119火警、医疗救护等，都需要尽快获得到达目得地的最快路径，以便处理突发事故。相对于静态最短路径算法而言，基于GIS的时变最短路径成果还很少，时变最短路径算法能与全球定位系统、GIS和ITS技结合在一起，综合每条道路不同时段的不同路况，找出最短最优的路径。本文就最简单最基本的校园两点之间的最短最优化路径，做了几个简单的功能实现。三、系统功能输入Ｎ（Ｎ<10）个

3、校园出发点，每两个地点之间有对应的距离和费时（可以不能到达），要求实现如下程序：ａ）给出任意两个校园出发点之间的最短距离，及其到达方式；ｂ）给出任意两个校园出发点之间的最少用时，及其到达方式；ｃ）权衡距离和费用，给出任意两个城市之间的最优路径，及其到达方式；PS：1.距离矩阵和费用矩阵由同学自己给出；2.题c)的最优路径由自己定义。四．算法设计欲求得每一对顶点之间的最短路径，解决这一问题的办法是采用弗洛伊德算法。弗洛伊德算法仍从图的带权邻接矩阵出发，其主要思想是：设集合S的初始状态为空集合，然后依次

4、向集合S中加入顶点V0,V1,V2，…，Vn-1，每次加入一个顶点，我们用二维数组D保存每一对顶点之间的最短路径的长度，其中，D[i][j]存放从顶点Vi到Vj的最短路径的长度。在算法执行中，D[i][j]被定义为：从Vi到Vj的中间只经过S中的顶点的所有可能的路径中最短路径的长度（如果从Vi到Vj中间只经过S中的顶点当前没有路径相通，那么d[i][j]为一个大值MaxNum）。即d[i][j]中保存的是从Vi到Vj的“当前最短路径”的长度。每次加入一个新的顶点，Vi和Vj之间可能有新的路径产生，将

5、它和已经得到的从Vi到Vj的最短路径相比较，d[i][j]的值可能需要不断修正，当S=V时，d[i][j]的值就是从Vi到Vj的最短路径。因为初始状态下集合S为空集合，所以初始化D[i][j]=A[i][j]（A[i][j]是图的邻接矩阵）的值是从Vi直接邻接到Vj，中间不经过任何顶点的最短路径。当S中增加了顶点V0,那么D(0)[i][j]的值应该是从Vi到Vj，中间只允许经过v0的当前最短路径的长度。为了做到这一点，只需对D(0)[i][j]作如下修改：D(0)[i][j]=min{D[i][j

6、],D[i][0]+D[0][j]}一般情况下，如果D(k-1)[i][j]是从Vi到Vj，中间只允许经过{V0,V1,V2，…，Vk-1}的当前最短路径的长度，那么，当S中加进了Vk，则应该对D进行修改如下:D(k)[i][j]=min{D(k-1)[i][j],D(k-1)[i][k]+D(k-1)[k][j]}五．概要设计1.数据结构二维数组来表示邻接矩阵，数组中存储元素表示邻接点之间的距离，或费时。2.抽象数据类型有向图3.函数接口Voidmain()主函数VoidDispmat()输出邻接

7、矩阵函数VoidFloyed()计算最短路径函数VoidDispath()输出最短路径函数六．详细设计Main函数的流程图如下：结束将矩阵ＡＢＣ初始化，矩阵元素均为ＩＮＦ输入校园出发点个数和弧数g.n和g.e构造距离矩阵Ａ开始g.edges[i][j]=A[i][j];DispMat(g)Floyd(g)构造时间矩阵g.edges[i][j]=B[i][j]DispMat(g)Floyd(g)输入权值系数a0和b0构造矩阵Ｃg.edges[i][j]=C[i][j]DispMat(g)Floyd(g

8、)DispMat(MGraphg)函数流程图如下：i