GIS网络分析功能的实现
- 格式：pdf
- 大小：40.06 KB
- 文档页数：1
２００７．９（下旬刊）
网络分析作为ＧＩＳ应用最主要的功能之一，在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。
随着计算机及测绘技术的不断发展，地理信息产业得以蓬勃发展，近几年来我中心面向社会的ＧＩＳ应用开发不断增多，逐渐形成以ＭａｐＧｕｉｄｅ为主流的ＧＩＳ应用开发体系。
ＭａｐＧｕｉｄｅ是Ａｕｔｏｄｅｓｋ公司的商业Ｗｅｂｇｉｓ产品，该产品合理的分配了客户机和服务器的运算，实现了矢量数据的直接访问，优良的性能、可扩展性强，是ｗｅｂｇｉｓ应用的首选产品之一。
ＭａｐＯｂｊｅｃｔ是美国ＥＳＲＩ生产的控件式ＧＩＳ系统，它性能稳定，价格适中，是目前非常流行的ＧＩＳ系统开发平台。
但这两个系统都没有现成的网络分析功能，为了满足用户的应用需求，我们通过二次开发为ＭａｐＧｕｉｄｅ和ＭａｐＯｂｊｅｃｔ分别定制了网络分析功能。
网络分析中最基本最关键的问题是最短路径问题。
最短路径不仅仅是指一般地理意义上的距离最短，还可以引申到其他的度量，如时间、费用、线路容量等。
其实，无论是距离最短、时间最快还是费用最低，它们的核心算法都是最短路径算法。
最短路径的求解，必须把现实生活中的道路、管线等各种网络抽象成一种数学结构，这种抽象出来的数学结构被称为网络拓扑结构。
于是各种网络分析技术实现的关键在于网络拓扑结构的建立和高效能最短路径算法。
下面我们就这两个问题进行深入探讨。
１．最短路径算法
最短路径算法，关键是半一个物理网络结构抽象为一个数学网络结构，再利用数学方法进行求解。
１．１算法选择
在数学和计算机领域网络被抽象为图，再利用图论的方法计算最短路径。
目前提出的基于图论的最短路径的算法大约有１７种．经专家测试，其中有３种效果比较好，它们分别是：ＴＱＱ、ＤＫＡ以及ＤＫＤ。
其中ＴＱＱ算法的基础是图增长理论；后两种算法则是基于Ｄｉｊｋｓｔｒａ的算法。
Ｄｉｊｋｓｔｒａ算法为理论基础，只是不同系统对Ｄｉｊｋｓｔｒａ算法采用了不同的实现方法。
１．２经典Ｄｉｊｋｓｔｒａ算法的主要思想
将顶点分成两个集合Ｓ和Ｔ，已求出最短路的点置于Ｓ中，其它点置于Ｔ中。
开始时Ｓ中仅含起点ｖｓ，其中点全在Ｔ中，随着求最短路迭代工作的进行，Ｓ中的点逐渐增多，当终点ｖｔ也被纳入Ｓ中时，迭代结束。
为了便于计算和区分各顶点组成，记为（ｄ（ｖｓ，ｖｋ），ｉ）其中ｉ为ｖｋ到起点最短路上的前点，ｄ（ｖｓ，ｖｋ为从起点ｖｓ到ｖｋ的最短路长．因每个标号含有两部分，故称为双标号法．最短路径算法的基本过程如下：（１）给始点ｖｓ赋以标号（０，ｓ），并置ｖｓ于置，其它顶点于集合Ｔ中（２）对图Ｇ里起点在Ｓ中终点在Ｔ中的ｅｉ计算：
Ｄ（ｖｓ，ｓｋ）＝｛ｄ（ｖｓ，ｖｉ）＋ｍｉｎｊ［Ｗｉｊ］—ｖｉ∈Ｔ｝并将ｖｋ置于ｓ中，同时赋给它标号（ｄ（ｖｓｓｋ），ｉ）。
（３）重复步骤（２），当ｖｔ∈Ｓ时计算结束ｖｔ的第一个标号给出ｖｓ→ｖｔ的最短路长；利用第二个标号反向追踪，可得最短路径。
２．网络拓扑关系的获取与高效访问
要想用计算机程序实现Ｄｉｊｋｓｔｒａ算法，关键技术是用什么样的方式抽象出网络拓补结构，及节点与节点的连通关系，并对网络拓补结构进行高效能访问。
２．１拓补关系的获取
ＧＩＳ中的数据（如道路、管网、水系等）要进行最短路径的计算，就必须首先将其按节点和边的关系抽象为图的结构，这在ＧＩＳ中称为构建网络的拓补关系。
只有建立了拓补关系，我们才能进行网络路径分析。
ＧＩＳ数据通常是图形数据的属性数据的有机结合，在ＡＲＣ／ＩＮＦＯ下利用命令ＣＬＥＡＮ对道路网络数据构建网络拓补，我们可以看到属性表，其属性结构中包括＿Ｆｎｏｄｅ（起点）和＿Ｔｎ－ｏｄｅ（终点）两个属性项。
该属性表中包含了一个完备的网络拓补关系的，即记录了该图拥有多少个节点，又记录了节点与节点的连通关系，不同的＿Ｆｎｏｄｅ、＿Ｔｎｏｄｅ标号代表不同的节点，及一条线的起始节点和终止节点，拥有相同节点的线相连，从该表大家应该很清楚的看出道路网的拓补结构。
构建网络拓补是一个复杂的过程，在搭建用户应用系统时，一般使用ＡＲＣ／ＩＮＦＯ等专业软件好网络拓补关系，使用时只需访问ＧＩＳ数据的数学表即可。
２．２网络拓补关系的高效访问
利用上面的属性表我们可以又效的解读出一个网络拓补关系，在按标记法实现Ｄｉｊｋｓｔｒａ算法的过程中，核心步骤就是从未标记的点中选择一个权值最小的弧段，即上面所术算法的２）～３）步。
下面主要就如何从含拓扑关系的属性表中解析一个简洁高效的网络拓扑存储结构进行讨论。
在数学和计算机领域中网络拓扑被抽象为图，所以其基础是图的存储表示。
一般而言，无向图可以用邻接表和十字链表表示。
综合以上４种存储结构的优缺点，我们采用了两个数组来存储网络图，一个用来存储和弧段相关的数据（Ｎｅｔ－Ａｒｃｌｉｓｔ），另一个则存储和顶点相关的数据（ＮＥＴ－Ｎｏｄｅｌｎｄｅｘ）。
Ｎｅｔ－Ａｒｃｌｉｓｔ用一个数组维护并且以弧段起点的点号来顺序排列，同一起点的弧段按权值排序。
这个数组类似于邻接矩阵的压缩存储方式，其内容则具有邻接多重表的特点，即一条边以两顶点表示。
Ｎｅｔ－ＮｏｄｅＩｎｄｅｘ则当于一个记录了顶点出度的索引表，通过它可以很容易地得到此顶点的出度和与它相连的第一条弧段在弧段数组中的位置。
这样就可以以最快速度搜索出与任意节点相连的边在顶点已编号的情况下，建立Ｎｅｔ－ＡｒｃＬｉｓｔ和Ｎｅｔ－ＮｏｄｅＩｎｄｅｘ两个表以及对Ｎｅｔ－ＡｒｃＬｉｓｔ的排序其时间复杂度共为Ｏ（２ｎ＋ｌｇｎ），否则为Ｏ（ｍ＋２ｎ＋ｌｇｎ）。
这个结构所需的空间也是必要条件下最小的，记录了ｍ个顶点有及ｎ条边的相关信息，与邻接多重表是相同的。
参考文献：
［１］李德仁．当前国际ＧＩＳ的研究和应用现状．１９９５．
［２］李斌．我国ＧＩＳ软件工业面临的机遇和挑战．１９９９．
ＧＩＳ网络分析功能的实现
□胡明光张亮
（固始县房地产管理所河南・固始４６５２００）
摘要网络分析作为ＧＩＳ的重要功能在电子导航、交通旅游、城市规划以及电力、通讯等各种管网、管线的布局设计中发挥了重要的作用。
随着ＧＩＳ系统集成应用的不断深入，为了满足用户的应用需求，我们通过二次开发的手段，为一些ＧＩＳ平台定制了网络分析功能。
利用经典的Ｄｉｊｋｓｔｒａ算法，结合ＧＩＳ数据和平台特点，通过简单的程序设计可实现复杂的网络分析功能。
关键词网络分析Ｄｉｊｋｓｔｒａ算法网络拓朴关系
中图分类号：Ｎ９９文献标识码：Ａ文章编号：１６７２－７８９４（２００７）０９－２１６－０１
理工科研
２１６。
