GIS网络分析中最短路径的实现.pdfVIP

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