-
1 教学内容
-
2 PPT
-
3 小节作业
6．网络分析
对地理网络（如交通网络）、城市基础设施网络（如各种网线、电力线、电话线、供排水管线等）进行地理分析和模型化，是地理信息系统中网络分析功能的主要目的。网络分析是运筹学模型中的一个基本模型，它的根本目的是研究、筹划一项网络工程如何安排，并使其运行效果最好，如一定资源的最佳分配，从一地到另一地的运输费用最低等。其基本思想则在于人类活动总是趋于按一定目标选择达到最佳效果的空间位置。这类问题在社会经济活动中不胜枚举，因此在地理信息系统中此类问题的研究具有重要意义。
6．1网络数据结构
网络数据结构的基本组成部分和属性如下：
1）链（Link）
网络中流动的管线，如街道、河流、水管等，其状态属性包括阻力和需求。
2）结点（Node）*
网络中链的结点，如港口、车站、电站等，其状态属性包括阻力和需求等。结点中又有下面几种特殊的类型。
l 障碍（Barrier），禁止网络中链上流动的点。
l 拐点（Turn），出现在网络链中的分割结点上，状态属性有阻力，如拐弯的时间和限制（如在8：00到18：00不允许左拐）。
l 中心（Center），是接受或分配资源的位置，如水库、商业中心、电站等，其状态属性包括资源容量（如总量），阻力限额（中心到链的最大距离或时间限制）。
l 站点（Stop），在路径选择中资源增减的结点，如库房、车站等，其状态属性有资源需求，如产品数量。
除了基本的组成部分外，有时还要增加一些特殊结构，如邻接点链表用来辅助进行路径分析。
6．2主要网络分析功能
6．2．1路径分析
1）静态求最佳路径：在给定每条链上的属性后，求最佳路径。
2）N条最佳路径分析：确定起点或终点，求代价最小的N条路径，因为在实践中最佳路径的选择只是理想情况，由于种种因素而要选择近似最优路径。
3）最短路径或最低耗费路径：确定起点、终点和要经过的中间点、中间连线，求最短路径或最小耗费路径。
4）动态最佳路径分析：实际网络中权值是随权值关系式变化的，可能还会临时出现一些障碍点，需要动态的计算最佳路径。
6．2．2计算最短路径的Dijkstra算法
为了进行网络最短路径分析，需要将网络转换成有向图。无论是计算最短路径还是最佳路径，其算法都是一致的，不同之处在于有向图中每条弧的权值设置。如果要计算最短路径，则权重设置为两个节点的实际距离；而要计算最佳路径，则可以将权值设置为从起点到终点的时间或费用。Dijkstra算法可以用于计算从有向图中任意一个节点到其它节点的最短路径。下面是该算法的描述。
1）用带权的邻接矩阵Cost来表示带权的n个节点的有向图，Cost[i,j]表示弧<vi,vj>的权值，如果从vi到vj不连通，则Cost[i,j]=∞。图8-14表示了一个带权有向图以及其邻接矩阵。
图8-14：带权的有向图和邻接矩阵
然后，引进一个辅助向量Dist，每个分量Dist[i]表示从起始点到每个终点vi的最短路径长度。假定起始点在有向图中的序号为i0，并设定该向量的初始值为：
Dist[i]=Cost[i0,i] vi∈V。
令S为已经找到的从起点出发的最短路径的终点的集合。
2）选择Vj，使得
Dist[j]=Min{ Dist[i]|Vi∈V-S} vi∈V
vj就是当前求得的一条从vi0出发的最短路径的终点，令
S=S∪{vj}
3）修改从vi0出发到集合V-S中任意一顶点vk的最短路径长度。如果
Dist[j]+Cost[j,k]<Dist[k]
则修改Dist[k]为：
Dist[k]=Dist[j]+Cost[j,k]
4）重复第2、3步操作共n-1次，由此求得从vi0出发的到图上各个顶点的最短路径是依路径长度递增的序列。表8-1是图8-14根据Dijkstra计算的结果。
表8-1：用Dijkstra计算的结果
终点 | 从v0到其它各个节点的最短路径 | ||||
v1 | ∞ | ∞ | ∞ | ∞ | ∞ 无 |
v2 | 10 （v0,v2） | ||||
v3 | ∞ | 60 (v0,v2,v3) | 50 (v0,v4,v3) | ||
v4 | 30 （v0,v4） | 30 (v0,v4) | |||
v5 | 100 （v0,v5） | 100 （v0,v5） | 90 （v0,v4,v5） | 60 （v0,v4,v3,v5） | |
vj | v2 | v4 | v3 | v5 | |
在实际应用中，采用Dijkstra算法计算两点之间的最短路径和求从一点到其它所有点的最短路径所需要的时间是一样的，算法时间复杂度为O(n2)。
6．2．3资源分配
资源分配网络模型由中心点（分配中心或收集中心）及其属性和网络组成。分配有两种形式，一种是由分配中心向四周分配，另一种是由四周向收集中心分配。资源分配的应用包括消防站点分布和求援区划分、学校选址、垃圾收集站点分布，停水停电对区域的社会、经济影响估计等。
1）负荷设计
负荷设计可用于估计排水系统在暴雨期间是否溢流，输电系统是否超载等。
2）时间和距离估算
时间和距离估算除用于交通时间和交通距离分析外，还可模拟水、电等资源或能量在网络上的距离损耗。
网络分析的具体门类、对象、要求变化非常多，一般的GIS软件往往只能提供一些常用的分析方法、或提供描述网络的数据模型和存储信息的数据库。其中最常用的方法是线性阻抗法，即资源在网络上的运输与所受的阻力和距离（或时间）成线性正比关系，在这基础上选择路径，估计负荷，分配资源，计算时间和距离等。对于特殊的、精度要求极高的、非线性阻抗的网络，则需要特殊的算法分析。
