浅谈GIS中网络分析与最短路径的实现

浅谈 GIS 中网络分析与最短路径的实现 专业 交通信息工程及控制 本科生 程海峰 主导老师 林科 摘摘 要要 网络分析作为 GIS 的重要功能在电子导航 交通管理 城市规划 管线的布局设 计中发挥了重要的作用 本文侧重于从网络拓扑关系的获取到最短路径算法的实现 为进一步研究 GIS 中网络分析的高效访问奠定基础 文章首先介绍了网络拓扑数据模型的一些基本概念 根据已有的研究经验 提出 了自己有关网络数据模型中最基本的两个概念 网线和结点 的理解 在这个框架之 下 又分析了网络拓扑关系的建立过程 得出了网络拓扑关系获取的一般过程 第二 部先介绍了最短路径算法选择的有关问题 通过查阅有关文献发现 目前解决系统最 短路径问题应用最为广泛的是 Dijkstra 算法的思想 最后阐述了有关经典 Dijkstra 算法 的主要思想并利用有关数据结构方面的知识写出了具体算法的实现过程 关键词 网络拓扑关键词 网络拓扑 网络数据模型网络数据模型 Dijkstra 算法算法 目目 录录 摘 要 I 1 引 言 1 2 网络拓扑关系的建立 2 2 1 网络数据模型的基本概念 2 2 2 网络拓扑关系的获取 2 3 最短路径算法 5 3 1 算法选择 5 3 2 传统 DIJKSTRA算法的主要思想 5 3 3 经典 DIJKSTRA算法的实现 6 参考文献 8 附 录 9 1 引 言 随着地理信息系统产业的建立和数字化信息产品在全世界的普及 地理信息系统 已经深入到各行各业 其中 网络分析是地理信息系统 GIS 最主要的功能之一 对 地理网络 如交通网络 城市基础设施网络 如各种网线 电力网线 电话网线 供 排水网线等 进行地理分析和模型化 是地理信息系统中网络分析的主要目的 近几 年来面向社会的 GIS 应用开发不断增多 逐渐形成以 MapObject 和 MapGuide 为主流的 GIS 应用开发体系 但这两个系统都没有现成的网络分析功能 只有通过二次开发才能 实现 MapObject 和 MapGuide 的网络分析功能 1 网络分析中最基本最关键的问题是最短路径问题 最短路径不仅仅指一般地理意 义上的距离最短 还可以引申到其他的度量 如时间 费用 线路容量等 相应地 最短路 径问题就成为最快路径问题 最低费用问题等 其实 无论是距离最短 时间最快还是 费用最低 它们的核心算法都是最短路径算法 最短路径的求解 必须把现实生活中的道路 管线等各种网络抽象成一种数学结构 这种抽象出来的数学结构被称为网络拓扑结构 于是各种网络分析技术实现的关键在 于网络拓扑结构的建立和高效能最短路径算法 下面我就分别从这两方面讨论起 2 网络拓扑关系的建立网络拓扑关系的建立 网络分析是空间分析的一个重要方面 是依据网络拓扑关系 线性实体之间 线 性实体与结点之间 结点与结点之间的连结 联通关系 并通过考察网络元素的空间 属性数据 对网络的性能特征进行多方面的分析计算 对地理网络 城市基础设施 2 网络进行地理分析和模型化的关键技术是用什么样的方式抽象出网络拓扑结构 及节点 与节点的连通关系 并对网络拓扑结构进行高效能访问 2 1 网络数据模型的基本概念网络数据模型的基本概念 网络是由若干线性实体互连而成的一个系统 资源由网络来传输 实体间的联络 也由网络来达成 网络数据模型是真实世界中网络系统 如交通网 通讯网 自来水 网等 的抽象表示 构成网络的基本元素是上述线性实体以及这些实体的连结交汇点 前者被称为网线或链 link 后者一般称为结点 node 网线构成网络的骨架 3 是资源传输或通讯网络的通道 可以代表公路 铁路 航线 水管 河流等 结点是 网线的端点 又是网线的交汇点 可以表示交叉路口 中转站 河流汇合点等 除了 上述基本网络元素之外 网络还可能有若干附属元素 如在路径分析中用来表示途径 地点的站点 在资源分配中用来表示资源发散地点或资源汇聚地点的中心 对资源传 输或通讯网络起阻断作用的障碍等 针对网络分析的需要 作为网络基本元素的网线 或结点除自身的常规属性外 还要具有一些特殊属性的数据 比如 为了实施路径分 析和资源分配 网线数据应包含正反两个方面上的阻碍度以及资源需求量 而节点数 据也应该包含资源需求量 2 2 网络拓扑关系的获取网络拓扑关系的获取 GIS 中的数据 如道路 管网 水系等 要进行最短路径的计算 就必须首先将其按结 点和边的关系抽象为图的结构 这在 GIS 中称为构建网络的拓扑关系 只有建立了拓扑 关系 我们才能进行网络路径分析 在 GIS 系统拓扑数据结构中 通常具有如下三种重 要的拓扑形式 说明线串如何相连的连通性 即线串是在结点上相互连接的 多边形是由一系列相连通的线串组成的 记录多边形的相邻信息已表示拓扑结构的连续性是根据线串的走向 可以决定谁 是左多边形 同时 量多变形之所以相邻是因为二者具有共同的边界 为了能够更好的描述路网拓扑结构的建立过程 首先介绍一下描述路网的基本要 素及各要素的属性 描述路网的基本要素 点对象 路网中道路和道路的交叉点以及道路的端点 先对象 用弧或链表示路段 形成路段的基本规则是 道路的所有车道合在一起 两结点之间的部分形成一个路段 面对像 有路段线围成的封闭区域 相关路网要素的属性 路段标识符 用编号表示 起 终点标识符 用编号表示 路段名称 路段长度 道路类别 结点表示符号 结点坐标 通常 可以用赋权图来表示路网 具体做法是分别存储点状实体 结点 线状 实体 两点间的路段 结点和路段的属性信息 以及实体间的拓扑关系 主要是连 通性和方向性 这样从图论的角度看 便将路网转化为一个图 进一步还可以在每一 条边上定义权 这样便得到了一个赋权图 从而 确定某两地间的最优路线问题便可 以转化为在赋权图上求两点间的最短路径问题 对于矢量图形的拓扑关系的描述 主要有基于网路的拓扑模型和基于点集拓扑理 论的拓扑模型 基于网络的拓扑模型具有直观 结构清晰 互换性强 便于组织存 4 储等优点 路网拓扑关系主要讨论线与线之间的联通性关系 即将其按结点和边的关 系抽象为图的结构 这在 GIS 中称为构建网络的拓扑关系 在计算机中这种拓扑关系 与面无关 拓扑关系中只记录了线与结点的关系 而没有线与面的关系 所以不是完 备的拓扑关系 路网拓扑结构主要包括两种对象 结点 Node 对象和边 Link 对 象 结点对象主要包括结点序号 结点属性和它附近的相关信息 及与之相连接的编 序号 边对象应包括编序号 长度信息 两个端点序号 根据结点对象相连接的边序 号和边对象的两个端点序号 就建立了结点之间的连接特性 路网的拓扑结构的生成主要找出各路段之间的直接连通性 实现算法是找出相应 图层中的所有线图元 然后判断任意两线图元是否相交 根据交点和顶点得到结点 根据橡胶关系判断两条边是否直接相连接 再根据相关信息对相应边赋权值 利用拓 扑得到的带权图来查询最短路径 拓扑结构的建立过程表示为图 2 1 的流程图 图 2 1 拓扑关系建立过程流程图 3 最短路径算法最短路径算法 由于网络特征的复杂性和问题的不同特征 最短路径的算法也表现出多样性 但 总的来说可以按问题的类型 网络特征和实现的算法进行分类 其中最经典 应用最 广泛的的还是 Dijkstra 算法 在实际应用当中 应该根据不同问题的类型选择适合于该 问题的算法 3 1 算法选择算法选择 最短路径算法选取的原则一般包括 1 算法速度快 2 算法占用资源少 3 算法稳 定性强 据统计 目前提出来的最短路径算法大约有 17 种 F BenJiama 等人对其中的 15 种进行了测试 结果显示有三种效果比较好 他们分别是 TQQ graph growth with to queues DKA the Dijkstra s algorithm with approximate buckets 以及 DKD the Dijkstra s implemented with double buckets 其中 TQQ 算法的基础是图增长理论 较适 合于单点到其他各点的最短距离 后两种算法则都是基于 Dijkstra 的算法 较适合于计 算两点间最短距离 目前多数系统解决最短路径问题采用的是 Dijkstra 算法为理论 5 基础 只是不同系统对 Dijkstra 算法采用了不同的实现方法 针对不同的网络特征 应 用需求及具体的硬件环境 各种算法在时间复杂度 空间复杂度 实的难易程度等方 面各具特色 3 2 传统传统 Dijkstra 算法算法的主要思想的主要思想 Dijkstra 算法的基本思路是 假设每个顶点都有一对标号 其中是从起 jj pd j d 点 s 到终点 j 的最短路径长度 则是从 s 到 j 的最短路径中 s 的前一点 求解从 s 到 j p j 的最短路径的算法的基本过程如下 初始化 起始点设置为 为空 所有其它点 0ds j p i d i p 标记起始点 s 计 k s 其它所有点设为为标记的 检验从所有以标记的点 k 到其直接连接的标记点 j 的距离 并设置 min kjkjj lddd 式中 是从点 k 到 j 的直接连接距离 kj l 选取下一个点 从所有为标记的结点中 选取中最小的一个 i j d min jdd ji 所有未标记的点 点 i 就被选为最短路径中的一点 并设为以标记的 找到点 i 的前一点 从以标记的点中找到直接连接到点 i 的点 作为前一点 设 j 置 ji 标记点 i 如果所有点以标记 则算法完全退出 否则 记 k i 转到 2 在继续 3 3 经典经典 Dijkstra 算法的实现算法的实现 首先 引进一个辅助向量 D 它的每个分量 D 表示当前所找到的从始点 v 到每个 终点 vi 的最短路径的长度 如 D 3 2 表示从始点 v 到终点 3 的路径相对最小长度为 2 这里强调相对就是说在算法过程中 D 的值是在不断逼近最终结果但在过程中不一定 就等于最短路径长度 它的初始状态为 若从 v 到 vi 有弧 则 D 为弧上的权值 否则 置 D 为 显然 长度为 D j Min D vi V 的路径就是从 v 出发的长度最短的一条 最短路径 此路径为 v vj 那么 下一条长度次短的最短路径是哪一条呢 假设该次 短路径的终点是 vk 则可想而知 这条路径或者是 v vk 或者是 v vj vk 它的长度 或者是从 v 到 vk 的弧上的权值 或者是 D j 和从 vj 到 vk 的弧上的权值之和 一般情 况下 假设 S 为已求得最短路径的终点的集合 则可证明 下一条最短路径 设其终 点为 X 或者是弧 v x 或者是中间只经过 S 中的顶点而最后到达顶点 X 的路径 因 此 下一条长度次短的最短路径的长度必是 D j Min D vi V S 其中 D 或者是弧 v vi 上的权值 或者是 D k vk S 和弧 vk vi 上的权值之和 迪杰斯特拉算法描述如 下 1 arcs 表示弧上的权值 若不存在 则置 arcs 为 在本程序中为 MAXCOST S 为已找到从 v 出发的最短路径的终点的集合 初始状态为空集 那么 从 v 出发到 图上其余各顶点 vi 可能达到的最短路径长度的初值为 D arcs Locate Vex G v i vi V 2 选择 vj 使得 D j Min D vi V S 3 修改从 v 出发到集合 V S 上任一顶点 vk 可达的最短路径长度 下面为用 C 语言描叙的迪杰斯特拉算法 void ShortestPath DIJ MGraph G int v0 PathMatrix final v0 true 开始主循环 每次求得 v0 到某个 v 定点的最短路径 并且加 v 入到 s 集 for i 1 i G vexnum i min infinity infinity 是无穷的大数 for w 0 w G vexnum w if final w if D w min v w min D w final v true for w 0 w G vexnum w 更新当前最短路径和距离 if final w P w w true 参考文献参考文献 1 胡明光 张亮 GIS 网络分析功能的实现 J 科教文汇 2007 年 9 月下旬刊 2 Michael N DeMers 武法东 付宗棠等译 地理信息系统基本原理 M 电 子工业出版社 2001 年第二版 第 45 47 页 3 张荣梅 智能交通地理信息系统的设计与实现 J 计算机应用研 究 2000 年第一期 第 97 98 页 4 王行风 贾凌 GIS 支持下的城市交通网络最短路径研究 J 计 算机与现代化 2005 年第四期 第 9 12 页 5 F B ZHAN Three fastest Path Algorithms on Real Road Networks J Journal of Geographic Information and Decision Analysis 1997 1 2 56 57 附附 录录 下面是一个有关用邻接矩阵实现的一个简单 C 程序 include include define MAX 10 p 二维数组 存放权值 n 顶点个数 d i i 距离出发点的最短路径 path i 最短路径上 i 前面顶点的编号 s 出发点 void shortestPath int p 8 int n int d int path int s 判断出发点有没有邻接点 for int i 0 i n i if p s i MAX break else if i n return 顶点 v 是否并入集合 S 中 bool isUnion n 初始化 for int i 0 i n i d i MAX path i 1 isUnion i false 初始化出发点相邻接的顶点距离 for int i 0 i n i if p s i MAX d i p s i path i s isUnion s true d s 0 选择最短路径 int min t for int i 1 i