dijkstra算法在gis实际应用中的优化

《dijkstra算法在gis实际应用中的优化》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、Dijkstra算法在GIS实际应用中的优化摘要：地理信息系统（GIS）的实际应用中，对城市道路最短路径的搜索一直是人们研究的重点。Dijkstra算法是最适合拓扑X络中两点间最短路径搜索的算法之一，但由于在城市里对道路最短路径搜索受到道路的畅通等原因所影响，故单纯利用Dijkstra算法并不能很好解决人们的实际需求。本文通过在GIS系统中增加一个设置、查询路障功能来解决以上提到的问题。关键词：Dijkstra；算法；优化1.引言近年来，GIS被广泛的应用在城市管理等方面上，GIS最主要、最具体的任务是负责管理大型X状设施(如城市中的各类地下管线、交通线、通讯线路等)

2、，使得其对X络最短路径分析功能的需求日益增长。在对最短路径搜索的问题上，Dijkstra算法是综合各方面性能较好的算法之一。可在实际道路搜索中，最短路径的意义不仅是指地理上的最短距离，还应包括时间上的，即能用最短的时间到达目的路，这对安排抢险救援的路线尤其重要。本文针对城市应急中的最短路径分析进行了深入的研究，并提出了相应的解决办法。2.Dijkstra算法的应用与实现传统的Dijkstra算法将X络节点分为未标记结点、临时结点和永久标记结点三种类型。X络中所有结点首先初始化为未标记结点，在搜索过程中和最短路径结点相连通的节点为临时标记结点，每一次循环都是从临时标记结

3、点中搜索距离源点路径长度最短的结点作为永久标记结点，直至找到目标结点或者所有结点都成为永久标记结点才结束算法。该算法能有效解决有向图中单个源点到其他顶点的最短路径问题。在本文讨论的GIS中，用MapObjects实现的具体思路为：(1)在地图上获取一点，作为起点，并获取到该点的点对象FMoPoint。(2)以FMoPoint作为源点调用MO的方法对指定的单位图层搜索该点附近很小范围内的图元元素，搜索到的第一个图元元素作为起点的起始地址；若搜索不到，则把步骤(3)得到的道路名称作为起始地址。(3)以FMoPoint作为源点调用MO的方法搜索最短路径图层，找到距离原点最近

4、的一条道路作为开始的道路。具体的搜索的方法为：①以某一指定的步长作为搜索范围的半径，搜索FMoPoint作为圆点的圆形范围；搜索的结果若为空，则增加步长的值，再重新开始搜索，直到搜索结果不为空。②将搜索到的结果作为一个线段的集合，计算源点到每条线段的最短距离，距离源点最近的一条线段作为开始的线段（道路），并记录下该线段到源点距离最短的点作为FNode（开始结点）。(4)同理，在地图上获取第二点TMoPoint作为终点，并得到终点的地址，和终点（结束）的线段（道路）及TNode（结束结点）。(5)得到开始线段和结束线段后，计算出FNode到开始线段的两个端点的距离，TN

5、ode到结束线段两个端点的距离；因为FNode和TNode是作为临时创建的点，故要计算出所需的距离，用于最短距离计算。(6)以FNode作为起点，TNode作为终点，用Dijkstra算法对最短路径图层计算出最短路径来。(7)判断FMoPoint是否在开始线段上，如果不在则计算FMoPoint到FNode的距离；如果在，则计算实际的最短路径由FMoPoint经过开始线段的端点的距离。(8)同理，判断TMoPoint是否在结束线段上，并进行相应的处理。最后调整最短路径的实际距离。最短路径计算结束。3.改进的设计与实现由于上述算法中得到只是行驶长度的最短路径，但在实际情况

6、中，这个长度并不真正就意味着是救援者到现场的最优路径，因这其中还涉及到道路等级、路面状况等因素。为此本系统还增加了一个设置路障、查询路障的功能，使查找最短路径时能避开这些无效路径，从而得到实际中的最优路径。实现的具体思路为：(1)首先得到要设置的道路，方法有两个：①通过MO的方法用SQL语句来查询所要设置的道路。②通过点取地图上的道路线段来获得所要设置的线段。实现为在地图上点一点，然后调用MO的搜索方法搜索该点附近的线段来获取要设置的线段。(2)得到要设置的道路线段后，通过MO的方法获得该线段两个端点的经纬度。计算这两点的经度值之差的绝对值（LongV）和纬度值之差的

7、绝对值（LatV）。比较LongV和LatV的大小，如果LongV>LatV，那么认为该道路线段是沿着经度方向的，反之，则认为该道路线段是沿着纬度方向的。(3)MO的每条线段都是点的集合，假定对应数组PointAry[i](i=0,1,2,……,PointCount-1)，并且把PointAry[0]当作该线段的起点，把PointAry[PointCount-1]当作终点。如果起点的纬度值大于终点的纬度值，则该线段默认的纬度方向是从东向西，反之，则是从西向东。同理，如果起点的经度值大于终点的经度值，则该线段默认的经度方向是从北朝南，反之，则是从南朝北