第32卷第5期2007年9月
测绘科学
science0fsuⅣeyingaIldMapping
voL32No.5
sep.
GIS网络分析中最短路径的实现
王秀斌
(福建省地图出版社,福州350003)
【摘要】本文提出了一种基于矢量角度的最短路径搜索算法,设计出一种类似于面向对象的数据存储结构来存
储网络图中的节点及弧段对象,在最短路径的搜索上引入矢量夹角标量值作为搜索因子,充分利用了网络图中各点元素和线元素间的拓扑关系,提高了搜索的趋势性,同时还考虑了各弧段的长度值(或权值),较好的将网络图中对象的空间信息和属性信息相结合。
【关键词】最短路径;矢量角度;拓扑关系【中图分类号】P208【文献标识码l
1
A
【文章编号】1009-2307(2007)05枷61旬2
DimArcIDAsIntegerDimEnd
引言
kn舢As
Double
’弧段ID,唯一标识弧段
7弧段长
随着地理信息产业的建立和数字化信息产品在全世界的普及,地理信息系统已深入到各行各业甚至各家各户,成为人们生产、生活学习和工作中不可缺少的工具和助手。地理信息系统中网络分析功能的主要目的是对地理网络(如交通网络)、城市基础设施网络(如各种网线、电力线、电话线、供排水管线等)进行地理分析和模型化。
最短路径问题是地理信息系统网络分析中最基本、最关键的问题,在交通网络结构的分析、交通运输线路的选择、通讯线路的建造与维护、运输货流的最小成本分析、城市公共交通网络的规划等,都有直接应用的价值。关于最短路径问题,目前为人们所公认的最好求解方法,是1959年由E.w.Diikstar提出的标号法,但在具体实现中,多数求解方法在存储空间及运行效率上还存在着一定的问题。如乐阳同志,实现的最短路径方法就以牺牲存储空间的方法来换取算法的运行效率旧o,张福浩同志实现的最短路径方法仅针对单幅地图数据,多图幅的网络分析还存在效率上的问题¨1。
本文从图形数据的存储结构及最短路径顶点的搜索策略两个方面对D珧stra算法进行了改进,提出了一种基于矢量角度的最短路径搜索算法。
Type
其中节点对象中的三个数组大小在初始化时利用邻接弧段数量设置大小,因此对应不同的节点对象其大小是不固定的,使用此种结构,对于有向图不会造成数据的冗余,而对应于无向图也仅多存储了一倍的弧段ID,邻接节点ID及矢量角度,相对于经典Dijkstra算法来说,需要的存储空间仍较小。对于弧段对象来说,其中的kngtIl可以设置为弧段长度,也可根据需要设置为时间、费用等相应的权值。
3算法原理
由两点之间直线最短的定理,构造一条理想最短路径(如图1中的AB),这条直线段一定是A、B两点间弧段中距离最短的一条。但实际上这条直线段作为一段道路存在的可能性极小,但这条从起点到终点的直线段却代表了一个路线的趋势,从概率的角度,顺着这个方向的某些路段的集合组成最短路径的可能性较大。
以矢量夹角标量值作为最短路径顶点选取的第一要素。由于最短路径顶点一定是在当前节点的邻接节点中产生,故在每次搜索过程中,只在当前节点的邻接节点范围中比较。
构造两个矢量:矢量一是以当前节点为起点,B点为终点。矢量二是以当前节点的邻接节点为起点,B为终点。将矢量二的方向值与矢量一的方向值相减得到两矢量间夹角。每一个邻接节点将对应一个矢量夹角的标量值。构造标识分别为正负的两个队列,其中标识为正的队列中包含所有标量值为正的节点(包括标量值为0的节点),标识为负的队列中包含所有标量值为负的节点,两个队列均根据节点对应标量值的绝对值进行排序。由于在一般的道路网络图中,每个节点的邻接节点数范围一般为2—5个,而所有邻接节点将分布在两个队列之中,故对于标量值的排序过程使用一般的比较排序方法即可。
分别从正负两个队列中选出排在最前位的节点,即分别选出两个方向上夹角标量值最小的两个节点加入到最短路径顶点集合中。需要注意的是,最短路径顶点集合中的节点并不一定是最终求得的最短路径的顶点,而是成为最

短路径顶点可能性较大的节点。
图1求解A、口两点
问的最短路程
2道路网络数据结构
构造类似于面向对象的数据结构存储网络图:
Public
DimDimDimDimDim
TypeMyllode(点结构)NodeIDAsImeger’节点ID,唯一标识节点
AdjoinNumAsInteger’邻接弧段数量
AdjoinArcID()AsInteger’邻接弧段IDAdjoinNodeID()AsInteger7邻接节点ID
AdjoinCl锄p()AsDouble指向邻接节点的矢量
的角度
End
Type
TypeMyArc(弧结构)
Public
作者简介:王秀斌(1954-),男,福建平潭人,副社长,高级工程师,主要从事地图编制与GIS应用工作。
E—mail:xiubin_w@toncom
收稿日期:2007旬5-22
《交通 GIS 及应用》课程论文 浅谈 GIS 中网络分析与最短路径的实现 专业:交通信息工程及控制 本科生:程海峰 主导老师:林科摘 要网络分析作为 GIS 的重要功能...
第6期 王辛岩等:基于 GIS 的最短路径分析 43 注:这里的“Total cost:15”指的是从起点到目的地 总共经过了 14 个网络节点,如果把两个网络节点当作一个 ...
最短路径在 GIS中的实现和应用陈志远,赵思健摘 (汕头大学土木系,汕头 515063) 要: 最短路径问题是交通网络分析系统的一个基本问题,在理论上得到了广泛深入的...
1.1 系统网络分析功能模块的实现 1.1.1 最优路径查询的实现本模块是对最短路径的求解, 给定的两个点之间找到一个最短路径, 下拉 框里列出了用于分析的街道...
40 文章编号 :049420911 ( 2004) 0920040203 jkstra 最短路径算法的实现方法 。...GIS 摘要 :针对 GIS 中网络拓扑图的一般特点和对网络分析实时性的要求 , 以 ...
GIS中网络最短路径的不确定性分析 数模相关方法数模相关方法隐藏>> 第25 卷...的实现则依赖于数据结构的最短路径算法.本文讨论了电子地图如何在复杂的交通网络...
GIS网络分析功能的实现_天文/地理_自然科学_专业资料。理工科研 2007.9 ( 下...于是各种网络分析技术实现的关键在于网络拓扑结构的建立和 高效能最短路径算法。...
GIS中网络最短路径的不确定性分析_经济学_高等教育_教育专区。数模相关方法...3 使用改进的蚁群算法求最短路径问题的实现 式 ( 4) 表示所有经过边 ( i ...
基于GIS的城市道路网最短路径分析_天文/地理_自然科学_专业资料。基于现实城市...Floyd 算法、A* 算法等 , 各种算法在 空间复杂度、时间复杂度、易实现性等...
热门文档