网络分析的实现

网络分析的实现目录CONTENTS二、路径分析算法设计一、数据准备一、数据准备在现实生活中，常将空间事物抽象成点、线、面等几何要素。点、线建立拓扑关系，可以组成网络。网络在几何上由边连成，边的端点、交点是网络的节点。例如，道路网可以定义为几何上的“网”，行车路线可以定义为网络的“边”，车站站点可以定义为网络的“节点“。这样就把现实世界中的客观对象抽象成网络、节点、边之间的关系。对应几何特征又有相应的属性特征，例如道路网中的行车路线的距离等特征，转向点的通行规则等特征。一般，网络在数学和计算机领域中是被抽象为“图”这个概念的，所以其基础是图的存储表示。数据准备一、项目概况

1、数据准备网络分析是建立在拓扑关系基础上的,因此要进行网络分析就要建立相应拓扑关系,这就决定了需要什么样的数据，应该怎么组织。以交通道路网为例，要对其进行网络分析，就必须构建交通道路拓扑网络，如图所示。数据准备a数据分类对于给定的城市交通道路网，要在其基础上进行最短路径分析，最佳乘车方案分析，就必须构建道路拓扑网络，这才能进行最基本的分析。。以城市公交网络为例，数据分类如下。（1）公交路线线段：是公交网络中的最小线单元，以公交连接点为端点。（2）公交连接点：是公交路线线段端点。（3）公交路线：是一组公交路线线段的有序排列，为公交车辆行驶构建一个物理路径。其定义了公交网络中的一个有向路径。数据准备（4）公交线路；是复杂要素，指一组具有共同名称或编号的公交路线。大多数情况下，公交线路包含两个公交路线，每个代表不同的方向。（5）公交车站：是乘客上下公交车辆的地点。（6）公交换乘区：由一个或多个邻近的公交车站所构成。是乘客可在步行距离内换乘公交线路的公交车站的集合。（7）公交点：是公交网络中可设定地址的位置。该点可以有明确的物理意义，如景观点。数据准备b数据组织假设图4.1为一个公交网络。图中的每个小方块表示一个车站站点，边表示各站点之间的距离。如何用一定的数据结构来存储该网络图呢？可以采用“结点-弧段(可有多条弧段)-结点”的数据组织方式，按照公共汽车线路选择所经过的"站点-路线-站点"形成路径分析中的有向线。一般网络都是由节点、弧段两大基本要素组成。为了便于分析我们把这些信息组织成最基本的三类文件，即节点文件、弧段文件、目标文件。数据准备节点文件主要记录每个属于节点集的点，其数据项包括：点的ID、点的地理坐标、点的名称、类型标识码等，见下表。点的ID号XY节点名称类型标识码……………Node_IDi462.58912431.6324火车站1……………Node_IDj510.63242276.9718汽车总站0……………数据准备

表1节点文件结构弧段文件主要记录弧段的ID、起始节点、终止节点编号、中间点串以及弧段权值（可描述弧段各种属性信息，一般主要用来描述距离信息），见表2。弧段的ID起始节点ID终止节点ID中间点串权值……………Arc一IDiNode_IDiNode_IDj…110……………数据准备

表2弧段文件结构目标文件主要记录以点目标为端点，在两个端点之间加入若干点目标和弧段目标形成一种有方向的线（如公交线路），如果考虑到现实生活中线路的有向性,还可以由已经存在的有向线目标反向形成。对于每条有向线，记录其ID、几何类型、节点索引、节点数目、弧段索引、弧段数目、弧段名称，见表3。目标ID几何类型点数点集弧段数弧段集弧段名称…………………Obj_IDi1n...Node_IDi...n...ArcIDi...XX…………………数据准备表3目标文件结构节点文件、弧段文件、目标文件构成了网络的基本信息，而它们之间的相互关系则构成了完整的网络拓扑关系。三种数据之间的相互关系如图所示。图

文件结构级相互之间的关系这种拓扑关系数据将在数据采集时构造，并以文件形式保存下来，直至网络数据发生变化。若数据未发生变化，每次运算就直接从文件中读取所需的拓扑关系，这样有利于检索和分析速度的提高。数据准备二、路径分析算法设计一、项目概况路径分析算法设计前面路径分析中已经提到在电子地图中一般采用Dijkstra算法来实现最短路径求解问题。原始Dijkstra算法将网络节点分为未标记节点、临时标记节点和永久标记节点3种类型。首先要将网络中所有节点初始化为未标记节点，在搜索过程中和最短路径节点相连通的节点为临时标记节点，每一次循环都是从临时标记节点中搜索距源点路径长度最短的节点作为永久标记节点，直至找到目标节点或者所有节点都成为永久标记节点才结束算法。目前在实际应用中，空间存储问题已不是要考虑的主要问题，因此可以用空间换时间来提高最短路径算法的效率。邻接点优化算法已经被广泛的应用于电子地图的路径分析中，算法效率也优于其他优化算法。一、项目概况路径分析算法设计Dijkstra算法的数据组织基础是构造M×N的邻接矩阵，N是网络的节点数。当网络的节点数很大时，而各节点的邻接节点数又不多的情况下，有大量的∞元素存在，尤其是对于以真实的地图为对象的实际应用问题，这样将占用大量的存储空间，并且运算也很浪费时间。下面阐述在Dijkstra算法的基础上,采用邻接点算法，来提高运算速度。电子地图中静态网络分析的理论及算法已经很完备。但在实际应用中，网络特征可能时刻会发生变化，这就需要在算法设计时考虑实时性等因素。而动态网络是一个与实际应用结合紧密、发展前景广阔的研究领域，随着研究的不断深入，