DWM地理信息系统毕业论文doc

1、第一章概论1.1 地理信息系统111 地理信息系统的定义及发展所谓地理信息系统是指反映人们赖以生存的现实世界（资源和环境）的现 势和变迁的各类空间数据及描述这些空间数据特征的属性，在计算机软件和硬 件支持下，以一定的格式输入、存贮、检索、显示和综合分析应用的技术系 统。它强调的是空间的数据结构和数据分析。地理信息系统是随着计算机的发展，在原有学科交叉处派生出来的一门新 兴边缘学科。它是用来处理和分析空间数据的一门综合信息技术，它是介于信 息科学、空间科学和地球科学之间的交叉学科。它的发展同计算机技术、遥感 技术、信息工程及现代地理学息息相关。目前，同地球资源与环境有关的各学 科中，地理信息系统

2、的应用极为广泛。地理信息系统起源于本世纪 60 年代,它作为有关空间数据管理、空间信息 分析及传播的计算机系统，在其 30 多年的发展历程中已经取得了很大的成 就，并广泛地应用于土地利用、资源管理、环境监测、交通运输、城市规划、 经济建设以及政府各职能部门。112 地理信息系统的功能地理信息系统的基本功能如下：1、数据采集、检验与编辑。主要用于获取数据，保证地理信息系统数 据库中的数据在内容与空间上的完整性、数据值逻辑一致、无错等。2、数据格式化、转换、概化，通常称为数据操作。3、数据的存贮与组织。这是一个数据集成的过程，也是建立地理信息系 统数据库的关键步骤，涉及到空间数据和属性数据的组织。

3、4、查询、检索、统计、计算功能。查询、统计、计算是地理信息系统以 及许多其他自动化地理数据处理系统应具备的最基本分析功能。d:wm毕业论文.doc5、空间分析是地理信息系统的核心功能，也是地理信息系统与其他计算 机系统的根本区别。模型分析意指在地理信息系统支持下，分析和解决问题的 方法体现，它是地理信息系统应用深化的标志。6、显示。地理信息系统为用户提供了许多用于显示地理数据的工具，其 表达形式既可以是计算机屏幕显示，也可以是诸如报表、表格、地图等硬拷贝 图件，尤其要强调的是地理信息系统的地图输出功能。一个好的地理信息系统 应能提供一种良好的、交互式的制图环境，以供地理信息系统的使用者能够设

4、计和制作出具有高品质的地图。1.2 电子地图系统简介近年来，随着计算机技术、激光技术和微电子技术的发展和应用，传统地 图的表现形式和记录方式已逐渐失去了它昔日的垄断地位。信息作为经济战略 资源，越来越受到人们的广泛关注，信息的及时传输和处理已变成了当今社会 生产力、竞争离和发展成功的关键，信息网络将是一种渗透到各个角落的技术 和社会力量，它将把整个社会结构紧密联接在一起，成为现代社会的一条命 脉。作为空间和时间信息表达、传输工具的地图，又以新的表现形式电子 地图面对着信息革命和社会经济发展需求的挑战。在 80 年代中期，随着数字地图及地理信息系统技术的发展和应用，随着 计算机视觉化研究的深入，

5、在侧重于空间信息的表现与显示的基础上，电子地 图应运而生。电子地图主要应用于政府宏观管理、科学研究、规划、预测、大 众传播媒介、信息服务等领域。另外，它与全球定位系统（gps）相结合，在 航天、航空领域、军事领域以及汽车导航中也发挥着十分广泛的作用2 。目 前，在国际上影响较大的电子地图有美国世界影象电子地图集、加拿大国家电 子地图集。随着发展，众多的地理信息系统的应用成果也都以电子地图的形式 来展示,好的电子地图应具有地理信息系统的所有功能。121 电子地图的基本特征电子地图是以地图数据库为基础，以数字形式存贮于计算机外存贮器上， 并能在电子屏幕上实时显示的可视地图，又称“屏幕地图”或“瞬时

6、地图”。 根据电子地图存贮介质的不同又可分为“磁盘地图”或“光盘地图”等2。电子地图的主要优点在于：1、电子地图数据库可包括图形、图象、文档、统计数据等多种形式，也可以与视频、音频信号相连，数据类型与数据量的可扩展性比较强。2、查询检索和分析功能；能够支持从地图图形到属性数据和从属性数据 到图形图形的双向检索。3、图形动态变化功能；从开窗缩放、浏览阅读等基本功能到地图动画功 能、多维动画图形模拟等。4、具有良好的用户界面；使读者介入读地图的生成过程。5、多级比例尺之间的相互转换；由于计算机屏幕幅面的限制和计算机潜 在的计算功能和巨大的存贮能力，要求具有多级比例尺不同程度的制图综合功 能。6、信

7、息的存贮、更新以及通讯方式较为简便，便于携带与交流。121 电子地图软件系统生成模块包括多种地图制图、文字编辑、图表生成、影象恢复、数据更新 等功能。分析模块依据不同的用户层次的具体要求而设计，全面考虑电子地图 的内容和用途，可设置各种专用模块，或者设置定性分析、定量分析、相关分 析、动态分析等功能。显示模块包括检索方式、属性查询、静态显示、动态显 示、图形缩放等功能。1.3 空间分析的内容及意义空间数据的分析是地理信息系统中的核心部分，也是地理信息系统有别于 计算机辅助设计（cad）的关键所在。在地理信息系统基础上发展起来的电子 地图，它不仅着重提高地图的表现力，而且强调地图的分析和应用功能

8、。空间数据分析是指地理信息系统为用户提供的解决问题的方法。空间数据 分析的目的是为用户提供一套空间数据的分析方法。空间数据的查询和检索只 是空间分析的基本功能，空间分析的更深层次的内容涉及各种空间模型分析， 包含内容广泛，通常，它不仅包括对一个目标的空间位置信息和属性信息的分 析，还包括对多个目标的分析。下面所列举的是空间数据分析的主要功能： 查询检索拓扑查询，位置查询，属性查询，区域查询等。形态分析面积量算，距离量算，质心计算，周长量算等。地形分析等值线分析，坡度坡向分析，分水岭分析，视域分 析，剖面分析等。叠置分析视觉信息复合，条件叠置，无条件叠置等。 邻域分析缓冲区分析，泰森多边形分析，

9、拟合分析等。 网络分析最短或最佳路径分析，空间规划等。 图象分析图象增强，图象分割，图象细化等。 应用模型分析数学模型，统计模型，逻辑模型等。网络分析作为空间分析的一种，在地理信息系统中有着广泛的应用领域。 例如在城市规划中，通信线路的铺设，交通管理线路的确定，以及旅游工作新 线路的开辟等。对地理网络（如交通网络），城市基础设施网络（如各种网线、电力线、 电话线、供排水管线等）进行地理分析和模型化，是地理信息系统中网络分析 功能的主要目的。网络分析是运筹学模型中的一个基本模型，它的根本目的是 研究、筹划一项网络工程如何安排，并使其运行效果最好，如一定资源的最佳 分配，从一地到另一地的运输费用最

10、低等。起基本思想则在于人类活动总是趋 向于按一定目标选择达到最佳效果的空间位置。这类问题在生产、社会经济活 动中不胜枚举，因此研究此类问题具有重大意义。1.4 本文研究的主要内容在城市电子地图中，公共交通信息模块是必不可少的，它应为各种交通信 息的搜索、查询、统计提供方便直观的手段。为了较好地定义交通网络、高效 率地获得最佳路径，方便用户查询公共交通信息，本论文研究的主要内容如 下：第一章：概略地介绍地理信息系统的发展、功能，电子地图的软件系统、 功能以及二者都所具有的最主要功能空间分析。第二章：网络分析的基本数据组织方式。主要介绍了网络分析的理论基 础图论，网络的拓扑性质，以及提出了一种适于

11、最短路径算法的数据组织 方式。第三章：最短路径问题及算法。在介绍经典的 dijkstra 最短路径算法的 基础上，从节省存贮空间和提高运算速度的角度出发，采用邻接点算法来求两 点之间的最短路径。第四章：电子地图中公交线路的查询。基于最短路径算法，求得地图上任 意两站点之间的最短路径，显示并计算出最佳乘车方案。第五章：结论和建议。联系实际，指出需要改进之处以及在实际应用中应 注意的问题。第二章网络分析的基本数据组织方式在 gis 中,常将空间事物抽象成点、线、面等几何要素。点、线建立拓扑 关系，可以组成网络。网络在几何上由边连成，边的端点、交点是网络的结 点。例如，道路网可以定义为几何上的“网”

12、，行车路线可以定义为网络的 “边”，车站站点可以定义为网络的“结点”。这样就把现实世界中的客观对象 抽象成 gis 中的网络、结点、边之间的关系。对应几何特征又有相应的属性特 征，例如道路网中的行车路线的距离等特征，转向点的通行规则等特征。一 般，网络在数学和计算机领域中是被抽象为图这个概念的，所以其基础是图的 存储表示。作为后述讨论的基础，本章将介绍一些图论的内容。21 图一个图由两部分组成，一部分是结点，图的术语中也称之为顶点 （vertex）；另一部分是顶点的偶对，称之为边（edge）。通常，图的任意一对 顶点间都允许有一条边。树和链表也可看作受限图。因此，从某种意义上来说，图是最基本的

13、数据结构。图被广泛应用于模拟真实事件或抽象问题，并在数百个问题中经常被利 用。下面列出图常用解决的几类主要问题：1、模拟计算机与通信网络的联接；2、表示一张地图的一组坐标以及坐标之间的距离，以求得最短路径；3、模拟交通网络的流量；4、寻找从开始状态到目标状态的路径，如人工智能问题求解；5、模拟计算机算法，显示程序状态的变化；6、为复杂活动各子任务的完成寻找较优顺序，如大型建筑的建造；7、模拟家族、商业活动或军事组织的自然科学中动植物分类中的各种关 系。3在本文中，作者主要用图来表示地图上一组坐标以及坐标之间的距离，以求得最短路径，从而对交通网中的公共交通信息进行查询。211 图论中的基本概念一

14、般在几何上将图定义为空间一些点（顶点）和连接这些点的线（边和弧 段）的集合，可以表示为一个偶对 g=（v，e），其中 v 表示顶点的集合，e 表 示边的集合，因此图 21 可以表示为：v=v1，v2，v3，v4，e=e1，e2，e3，e4，e5，e6. 除此以外，还可以用边的两个顶点来表示边。如果边 e 的两个端点是 u 和v，那么 e 可写成 e=，这里表示 u 和 v 的无序对，即和都表达了以 u，v 为端点的无向边。这样图 21 又可表示为：g=（v，e）， v=v1，v2，v3，v4， e=，图 21 中边的两个顶点是无序的，一般称为无向图；在实际应用中，将 图和每条边分配一个方向是很

15、自然的，这样的图称为有向图（如图 22）。对 有向图，有向边 e 用与其关联的顶点 u，v 的有序对来表示，即 e=（u，v），u 表示边 e 的起点，v 为边 e 的终点。因此图 22 就可以表示为：g=（v，e）， v=v1，v2，v3，v4，e=（v1，v2），（v1，v3），（v1，v4），（v4，v2），（v4，v3），（v2，v3） 如果顶点 v 是边 e 的一个端点，则称边 e 和顶点 v 相关联（incident）；d:wm毕业论文.doc对于顶点 u 和 v，若（u，v）e，则称 u 和 v 是邻接的（adjacent）；若两条 边有共同的顶点，也称这两条边是邻接的。顶点 v

16、 的度（degree）是和 v 相关 联的边的数目，记为 td（v）。例如，图 21 中 v2 的度是 3。对于有向图，以 顶点为头的弧的数目称为 v 的入度（indegree），记为 id（v）；以 v 为尾的弧 的数目称为 v 的出度（outdegree），记为 od（v）。那么，td（v）=id（v）+od（v） 应用中往往还需要对图中的边赋值，这个值称为权。它可以表示边的各种不同的意义：如经过边的是一条道路，则权就可能是它的长度，也可能是它的通行税赋或修建费用等。设边 ei 的权为 wj，则 e 可以表示为：e=（e1，w1），（e2，w2）， , （em，wm）或者设w=w1，w2，

17、 ，wm则 g 可以表示为一个三元组：g=v，e，w。212 图的表示方法图的模型复杂，应用广泛，所以图的表示方法也是多种多样的，如图的邻 接矩阵表示法、图的邻接表表示法、图的邻接多重表表示法。对应于不同的应 用问题有不同的表示方法，因为在后面的章节中要涉及到图的相邻矩阵表示 法，所以对该方法进行简要的介绍。图的邻接矩阵表示法邻接矩阵是表示结点间的邻接关系的矩阵，若 g 是一个具有 n 个结点的 图，则 g 的邻接矩阵是如下定义的 n*n 的矩阵 a：1， 若（vi，vj）或是图 g 的边；ai，j=0,若（vi，vj）或不是图 g 的边。图 23 无向图的邻接矩阵为 a：0110010100

18、a=110110010100110对于有向图 24 的邻接矩阵为 b：00011010b=10010100显然，无向图的邻接矩阵一定是对称的，而有向图的邻接矩阵不一定是对 称的。对于带权的图，其相邻矩阵中值为 1 的元素可以用边的权来代替。网络是一种带权的连通图，只要将邻接矩阵稍加扩充便可用来表示网络。 设网络 g=（v，e，w）具有 n 个顶点，编号为 1，2， ,n。描述网络 g 的带权 邻接矩阵为 n 阶方阵 a，其元素 aij 定义为wij 若顶点 i 到顶点 j 有邻接边，wij 为该边上的权。aij =0若 i=j。若顶点 i 到顶点 j 无邻接边。 例如图 25 中无向网络的邻接

19、矩阵为 c：05750877806139 76010 13 1004 9 40邻接矩阵 c用邻接矩阵法来表示图，需要存储一个 n*n 的邻接矩阵来表示结点间的相 邻关系，对于有向图，需 n2 个位来存储邻接矩阵。用邻接矩阵来表示图容易判定任意两个结点 vi 和 vj 之间是否有长度为 m 的路径相连，这只要考察邻接矩阵 的第 i 行和第 j 列元素是否为 0 就行了。以上介绍的是图论中有关网络的几个基本概念和表示方法。在 gis 网络分 析中，为了更充分、更高效的发挥图论的优势，必须有好的数据组织方式作为 基础，所以在下一节，我们将介绍一种较好的适合于最短路径查询的数据组织 方式。22 交通网

20、络数据管理空间数据管理是以给定的内部数据结构为基础，通过合理的组织管理，力 求有效地实现系统的应用要求。假若说内部数据结构是寻求一种描述地理实体 的有效的数据表示方法，那么空间数据管理就是应用要求建立实体的数据结构 和实体之间的关系，把它们合理地组织起来，便于应用。目前，空间信息系统 的数据管理基本上是采用数据文件管理方式。设计者根据应用目的，采取他自 己认为最方便、最有效的数据组织和存贮管理方法。交通信息数据不仅是为界 面显示的需要，也是系统功能得以实现的依托。因在查询交通信息时，需不断 的对表示交通信息的数据进行搜索、查询和提取，所以在组织数据时，必须使 数据结构能够满足各种查询、分析功能

21、。221 交通网络的内部数据结构描述地理实体的数据本身的组织方法，称为内部数据结构。内部数据结构基本上可分为两大类：即矢量结构和网络结构。两类结构都可以用来描述地理 实体的点、线、面三种基本类型。在数字化道路图时，有栅格编码和矢量编码两种形式。栅格编码形式可在 一定的比例尺内，比较详尽地表现地图上的所有信息，有利于地图的显示，但 不利于道路网信息的分析，如地图匹配、道路寻找等；而矢量编码形式提供了 严密的数据结构和有效的拓扑编码，因而对需要拓扑信息的操作更有效，如网 络分析。所以在进行地图数字化时，须以矢量形式进行存储，为在网络分析中 交通信息的再提取提供了可能和条件。222 交通网络的实用数

22、据分析在交通网络分析中，所需要的实用数据如下：1、道路网的空间信息。道路网的空间数据由一系列的结点以及连接这些 结点的曲线构成。这里的结点既包括道路中的站点，也包括道路的交叉点。曲 线为道路的中心线。这种简单的数据源因为缺乏对道路宽度的表示，使得用户 对整个道路网的路况和环境直观了解有一定的影响，但在对道路网的分析应用 非常重要，如寻求道路网的最佳路径等。2、道路网的空间信息拓扑结构。在网络分析查询中，不论是线路的搜 索，还是最佳路径的计算，都要以道路网的拓扑结构为基础。所以在组织数据 时，应存储道路网络的拓扑结构，比如在一个道路交叉点处，究竟有哪些道路 在此交汇；一条道路究竟与哪些道路相连等

23、。有了道路网的这些空间拓扑结构 信息，在进行道路网的最佳路径计算时，会大大缩小道路网的搜索范围，从而 提高运算速度。3、道路的属性。道路的属性是指对道路特征的描述，如道路的名称、道 路的等级、道路是否为单行道等。223 交通网络的数据组织假设下图为一个交通网络。图中的每个顶点表示一个车站站点，边表示各 站点之间的距离，各边上所标的数字为该边具有的权重值。如何用一定的数据 结构来存贮该网络图呢？采用“结点弧段（可有多条弧段）结点”的 数据组织方式，按照公共汽车线路选择所经过的“站点路线站点”形 成路径分析中的有向线，同时，也可由已有的有向线反向形成一条新的有向 线。弧段和结点之间的网络拓扑表示如

24、图 26 所示:对于每个属于结点集的点，其数据项包括：点的 id，点的地理坐标，点的 名称等。采用面向对象的方法对结点类的描述如下：class cgeopoint /成员变量private:unsigned long nodeid;/结点 idpoint m_pobjcoor;/结点坐标char m_cobjnameobj_name_len;/结点名称;对于每条弧段，记录了其 id、起始结点、终止结点编号，弧段上的坐标点 数，每点的坐标，以及弧段权值（可描述弧段各种属性信息，本文中主要用来 描述距离信息）。用程序对弧段类的描述如下：class cgeoarc /成员变量private:unsi

25、gned long arcid;/弧段 idunsigned long m_ulobjcoornum;/每段弧的坐标点数 point *m_pobjcoor;/每个坐标点的坐标unsigned long m_ulbeginnode;/弧段起始结点 unsigned long m_ulendnode;/弧段终止结点 double m_flength; /弧段的长度;以点目标为端点，在两个端点之间加入若干点目标和弧段目标形成一种有方向的线（如公车线路），如果考虑到现实生活中线路的有向性，还可以由已 经存在的有向线目标反向形成。对于每条有向线，记录其 id，结点索引，结点 数目，弧段索引，弧段数目，

26、线路名称。对有向线类的程序描述如下：class cgeodirline /成员变量private:unsigned long *m_ulnodeid;/结点索引unsigned long m_ulnodenum;/结点数目 unsigned long *m_ularcid;/弧段索引 unsigned long m_ularcnum;/弧段数目char m_cobjnameobj_name_len;/线路名称;这种拓扑关系数据将在数据采集时构造，并以文件形式保存下来，直至网 络数据发生变化。若数据未发生变化，每次运算是就直接从文件中读取所需的 拓扑关系，这样有利于检索和分析速度的提高。23 线

27、路网络图的表示获取当前所有的公共汽车线路遍历每条公共汽车线路 获取每段弧的始终结点 id计算对应的弧段距离记录结点 id 及弧段距离构造邻接矩阵图 27 构造邻接矩阵的流程在公共交通线路网络中，以某路公共汽车的路径作为有向线，以公共汽车 停靠的站点作为网络的结点，而网络的弧段就是两相邻站点之间的路径。根据 网络结点弧段构成有向线之间的拓扑关系，构造该公共交通线路网络的邻 接矩阵 m_pstation，矩阵的行数和列数都为网络中结点的总数 m_nstationnum（即该路网中所有的站点数）。m_pstationij表示有向边上的权值 (这里主要用来表示站点与站点之间的距离)；若不存在,即站点与

28、站点 之 间 无 通 路 , 则 置m_pstationij 为 ； 若i=j, 则 令m_pstationij=0。构造邻接矩阵的流程图如图 27 所示:根据邻接矩阵,就可以应用经典的 dijkstra 算法求得两站点之间的最短路 径。如果要采用邻接点算法，可以计算邻接矩阵来求得一个结点与其他结点相 邻的情况，计算网络的最大邻接结点数，然后构造邻接点矩阵和初始判断矩 阵。对于两种算法的描述将在下一章作具体的介绍。第三章最佳路径问题及算法网络分析的理论基础是图论，其典型应用是求最短路径问题。最短路径分 析是根据网络的拓扑性质，求图数据结构中，从一个顶点出发到其他各顶点之 间的最短路径，或求每对

29、顶点之间的最短路径。最佳路径中的这个“佳”包括很多含义，它不仅可以指一般地理意义上的 距离最短，还可以是时间最短、费用最少、线路利用率最高等标准。但是无论 引申为何种判断标准，其核心实现方法都是最短路径算法。最短路径是组合最 优化中很重要、很基本的课题，一大类组合最优化问题都可以化为求最短路 径，或者用最短路径的算法作为其子程序。例如，通讯网络中的最可靠路问 题，最大容量问题，统筹方法中求关键路径以及某些加工顺序问题都可以化为 求最短路径问题8，9。对于公共交通来说，距离因素是最重要的，所以在本论 文的中，主要讨论距离最短的路径。31 最短路径方程在欧氏空间 en 中，设 x，y，z 为任意三

30、点，令 d（x，y）为 xy 的距 离，则有 d（x，y）d（x，z）+d（z，y），当且仅当 z 在 x，y 的连线上时等 式成立。类似的，令 dk 为顶点 vi 到 vj 的最短距离，wij 为 vi 到 vj 上的权值，对 于（vi ，vj）不属于 e 的顶点对，令 wij=，显然：d1=0，dkdj+ wjkk，j=2，3， ,p并且，当且仅当边（vj ，vk）在 v1 到 vk 的最短路径上时,等式成立。由于 dk 是 v1 到 vk 的最短路，设该路的最后一段弧为（vj ，vk），则由局部与整体的 关系，路的前一段 v1 到 vj 的长度也必为从 v1 到 vj 的最短路。这个整体

31、最优则局部也最优的原理正是最短路径算法设计的重要指导思想。d1=0，dk=min（dj+ wjk）k，j=2，3， ,p ；jk.这就是最短路径方程，然而直接求解此方程比较困难，目前几乎所有的最 短路径算法都是围绕着怎样解这个方程的问题。32 两类最短路径问题若一条边的权表示它的长度,道路 u=e1,e2, ek,的长度即为 u 上 所有边的长度之和。在赋权图中给定一个顶点 vi（称为起点）和 vj（称为终 点），所谓最短路径问题就是在 vi 和 vj 之间的所有路径中，寻求长度最小的路 径，这样的路径称为 vi 从 vj 到的最短路径。其中，第一个顶点和最后一个顶点 相同的路径称为回路或环（

32、cycle），而顶点不重复出现的路径称为简单路径。最短路径算法常可分为两大类：单源点间的最短路径算法（single source shortest path）和所有点对间的最短路径算法（all pairs shortest path）。后者是在整个算法中，求得所有点间的最短距离。而前者仅求得一点 到其他点的最短路径。下面就两种基本算法分别讨论。3.2.1 单源点间最短路径问题设一个有向图 g=（v，e），已知各边的权值，以某指定点 v0 为源点，求从 v0 到图的其余各点的最短路径。以图 31 所示的图为例，若指定以顶点 v1 为源点 v0，可得知从 v1 到其余 各点的最短路径为：v1v2

33、：10；v1v3 （经 v4） ：50； v1v4 ：30；v1v5 （经 v4） ：60；01030100050cost=010200600图 32 邻接矩阵最短路径是 v1 经 v4 经 v3 到 v5，而不是 v1 直接到 v5。如何用一定的算法来求得最短路径？荷兰人迪杰斯特拉(dijkstra)在 1959 年提出了一种求最短路径的算法,被广泛采用,称之为迪杰斯特拉算法.假设我们用邻接矩阵表示所研究的图,规定对角线元素取零值,各有向边的 元素取该边的权值,若两顶点间无相应方向的边,则该元素取无穷大。如图 3-2 所示。此矩阵用一个（n*n）二维数组表示，无穷大元素用一个很大的有限值 代

34、替，如果得到的某路径“长度”等于此给定的很大值，说明实际上不存在此 路径。首先引入两个辅助向量，一个是向量 dist，它的每个分量 disti表示当 前找到的从始点 v 到每个终点 vi 的最短路径长度。另一个向量是 s，s 为已找 到的从 v 出发的最短路径的终点的集合，其初始值为空集。则算法的描述可归 纳成如下步骤：1求从 v 出发到图上各顶点 vi 可能达到的最短路径长度的初值为：disti=costordinal（v），i，viv 其中 ordinal（v）表示顶点 v 在有向图中的序号。2选择 vj，使distj=min disti | vi 不属于 s， viv vj 就是当前求得

35、的一条从 v 出发的最短路径的终点，且令s=sj即将 j 加入到 s 集合中。3修改从 v 出发到集合 v-s 上所有顶点 vk 可达到的最短路径长度。如果distj+costj,kdistk 则修改 distk为distk=distj+costj,k。4重复操作 2、3 共 n-1 次。最后可求得从 v 到图上其余各顶点的最短路径是依路径长度递增的序列。若对图 31 施行 dijkstra 算法，则所得从 v0 到其余各顶点的最短路径 如图 33 所示，其运算过程中距离的变化情况如表 3.1 所示：表 3.1 dijkstra 算法示例及计算过程终点从源点 v1 到各终点的距离值和最短路径的

36、求解过程v10v210(v1,v2)v360(v ,v ,v )50(v ,v ,v )v430(v ,v )30(v ,v )v5100(v ,v )100(v ,v )90(v ,v ,v )60(v ,v ,v ,v )vjv2，10v4，30v3，50v5，60sv1,v2v1,v2,v4v1,v2,v3,v4v1,v2,v3,v4,v5123143141415151451435由此可见，从源点到图上其余各顶点的最短路径是依路径长度递增的顺序 排列的，并且在求解从源点到某一特定终点的最短路径过程中还可以得到源点 到其它各点的最短路径，因此，这一计算过程的时间复杂度是 o（n2）7，其中

37、 年 n 为网络中的节点数。3.2.2 所有点对间最短路径此问题也就是求解每一对顶点之间的最短路径，解决这个问题的方法是使 用弗洛伊德（floyd）算法或重复执行 dijkstra 算法 n 次，无论何种方法，其 时间复杂度都为 o（n3）。从表面上看，这一算法似乎很有效，然而在地理信息 系统中，这一算法很不实际。最易见的问题是内存的需求。假设一个网络有5000 个结点，仅存贮它们间最短距离就至少需要 100mb 的内存，如果要存贮它 们所经过的路径，则内存所需量更大，因此是不可行的。1033 优化 dijkstra 最短路径算法迪杰斯特拉最短路径算法的数据组织基础是构造 n*n 的邻接矩阵,

38、n 是网络 的结点数。当网络的结点数很大时，而各结点的邻接结点数又不多的情况下， 有大量的元素存在，尤其是对于以真实的地图为对象的 gis 实际应用问题， 这样将占用大量的存储空间，并且运算也很浪费时间。作者在 dijkstra 算法 的基础上，采用邻接点算法，以提高运算速度。3.3.1 邻接点算法基本思想一个网络中，各结点的邻接结点的最大值称为该网络的最大邻接结点数。 取网络的最大邻接结点数作为矩阵的列，网络的结点总数作为矩阵的行，构造 邻接结点矩阵 m_pj 来描述网络结构。邻接结点矩阵的行按结点号从小到大顺 序排列，与结点 i 邻接的结点号写在矩阵的第 i 行，如果结点 i 的邻接结点数

39、 小于最大邻接结点数，则以 0 填充，直到填满矩阵。对照邻接结点矩阵，把邻 接结点矩阵中各元素邻接关系对应的边的权值填在同一位置上（对应 0 元 素），构造相应的初始判断矩阵 m_pdj。邻接结点矩阵节省了存储空间，为在计算机实现过程中进一步提高运算速 度，提供了更加有效的网络结构组织方式。3.3.2 邻接结点算法的实现方法为了更清楚地了解邻接结点算法求解最短路径问题的具体过程，现举一例 来说明（见图 34）。其步骤如下：1、从数据文件中装载网络数据。2、求网络的最大邻接结点数 m_inodenummax。在该网络中，结点 3 的邻接 结点数最多，有 5 个邻接结点。即该网络的最大邻 接结点数

40、 m_inodenummax=5。3、构造邻接结点矩阵 m_pj，m_pj 的行按结点序号由小到大顺序排列成 10 行，与结点 i 邻接的结点号写在第 i 行，如果结点 i 的邻接结点数小于 最大邻接结点数，则以 0 填充，各行中的结点序号可以前后随意放置。 在本例中，可构造一个 10*5 的邻接点矩阵 m_pj。对应邻接结点矩阵各 元素，把各元素对应的边的权值填在同一位置，构造初始判断矩阵 m_pdj。250001112143001182567810191015172000081639012519305370051093698015916737100017714107500616308900

41、046图 35 邻接结点矩阵图 36 初始判断矩阵4、有邻接结点矩阵和初始判断矩阵，就可以求网络中任意两点间的最短路 径。若起点 s，终点为 t。第一步，初始化标记向量 p ， pi=-1 ， i=1,2,. ， m_inodesnum ，（m_inodesnum 为网络结点总数）；第二步，根据起点 s，标记初始判断矩阵的第 s 行，ps=0,记最短距离m_fdistancemin=0；第三步，根据终点 t，判断初始判断矩阵的第 t 行是否标记，是则转第五 步，否则继续。第四步，在初始判断矩阵已标记的行中，求所有元素的最小值 dmin。若 dmin=,说明不存在最短路径，则退出。否则 m_fd

42、istancemin= dmin，记录最 小值元素的行 di、列 dj。然后在邻接结点矩阵中取（di,dj）元素，记为 w。若第 w 行还未标记，则 将初始判断矩阵的第 w 行标记，pw=di；并在邻接结点矩阵的第 w 行寻找值为di 的元素，记录该元素的行 ri、列 rj。将初始判断矩阵中刚获得标记的行中各元素值均加上 m_fdistancemin，并 使初始判断矩阵中的（di,dj）和（ri，rj）元素为。转第三步。第五步，从终点 t 开始，由标记向量 p 的分量循前点，直到起点 s，查得 最短路径 m_pways。m_fdistancemin 即为最短路径距离。用面向对象的方法对该算法的

43、描述（简化）如下：class cgeolayerunsigned longm_inodenummax;/网络的最大邻接结点数int* m_pj;/邻接点矩阵float*m_pdj;/对应邻接点矩阵的初始判断矩阵unsigned long*m_pways; /存放某条最短路径上的所有站点intnnodenum;/某条路径上的站点数float m_fdistancemin；/最短路径距离333 应用实例为了检测算法的效果，作者以武汉百事通电子地图中的数据进行了一 些实验。例如：在主频为 133、2.8g 硬盘、32m 内存的机器上，计算一条贯穿 东西（西郊公园为最西站点，白玉山为最东站点）的线路，

44、采用 dikstra 算法 约需时间 7 秒左右，而采用邻接点算法可缩短到 1 秒多。计算一条贯穿南北（烽火村为最北站点，至二八八厂为最南站点）的线路，采用 dikstra 算法约 需 6 秒左右，而采用邻接点算法需 1 秒左右。从这些例子可得出优化的算法在一定程度上提高了查询的运算速度。第四章电子地图中公交线路的查询查询功能是地理信息系统的面向用户的窗口，是用户感觉 gis 能力最直接 的具体体现。空间信息查询是按一定的要求对地理信息系统所描述的空间实体 及其空间信息进行访问，从众多的空间实体中挑选出满足用户要求的空间实体 及其相应属性。查询交互进行时，其结果能动态地通过两个视窗（图形窗和属

45、 性表格窗口）进行显示。41 交通信息查询查询411 公交线路查询由于结点、弧段组成有向线的数据组织方式，系统可很方便的根据线路名 称自动搜索并闪烁显示出该线路及各站点信息。图 41 线路查询结果图在该查询中，如果选择“66 路”，视图中就会显示 66 路车的路线以及它所 停靠的每个站点：广埠屯街道口洪山付家坡大东门武昌 火车站。如果在列表框中单击某站点，在视图中就显示该站点的位置。如选择“广 埠屯”站点，系统就会自动搜索并闪烁该站点在地图中的位置。如下图所示：图 42 站点查询结果图412 最短路径查询在公共交通中，两点之间的最短路径是非常最重要的。公共汽车司机希望 行驶最短的路程达到目的地

46、；乘客希望在最短的时间内到达所要去的地方；在 交通网络的规划、路线的安排中，如果充分考虑两点之间的最短路径，会在一 定程度上提高整个交通网络的效率。在电子地图中，根据用户指定的两个站点，系统自动所有可能的连通线路 并分别计算每条连通线路的长度，从而找到两个站点间的最短路径，最后在地 图上显示两点之间的最短路径。在武汉百事通电子地图中，用户选择任意两站点的对话框如下：图 43 公车线路查询对话框 在此对话框中，列表框中列出了采集的所有站点名，可通过鼠标单击获得起始站点和终止站点，也可以在编辑框中用键盘输入起始站点和终止站点。单击查询按钮，就可以获得所需的两点之间的最短路径，并在地图闪烁上显示这

47、两点之间的路径。图 44 最短路径结果图42 最佳乘车方案查询公共交通和人们日常生活息息相关，出门购物、探亲访友、出差旅游等都 离不开公共交通。在电子地图的查询中，公共交通信息的查询倍受用户的关 注。在最短路径查询后，可通过站点与站点间的弧段获得通过该弧段的所有公 共汽车路线。如下图所示，线路查询结果中显示从鲁巷到广埠屯所经过的所有 站点以及每两个站点之间所有经过该段的车次。图 45 线路查询结果 虽然从查询结果中可详细的知道每两个站点之间的车次，但对于从甲地经过若干站到达乙地究竟该乘哪一路车，中间是否需要转车，在哪儿转车，转车次数是几次等结果在上述查询中并未得到。所以，现在的问题是如何获得最

48、佳 的乘车方案。421 最佳乘车方案的数据组织假设求广埠屯到武昌火车站的最佳乘车方案，其数据如下：广埠屯 108 路、25 路、66 路、521 路、540 路、538 路、702 路 街道口 108 路、25 路、66 路、77、521 路、540 路、702 路 洪山 108 路、25 路、66 路、77 路、521 路、540 路、702 路 付家坡 108 路、25 路、66 路、77 路、557 路、564 路、702 路 大东门 108 路、66 路、77 路、557 路、564 路、572 路 武昌火车站。数据组织 的主要思想是构造站点和车次之间的关系矩阵，通过对矩阵的搜索来求得

49、最佳 乘车方案，其步骤如下：1以两点之间的站数（包括起始站点和终止站点）作为矩阵的行 n，在此 矩阵中 n=6；2以两点之间所有的通过的车次数作为矩阵的列 n，在此矩阵中 m=11；3构造站点车次矩阵 m_proutestation1, 如果 j 路车通过地 i 个站 点则 m_proutestation1ij=1 ，如果 j 路车不通过第 i 个站点则 m_proutestation1ij=0，逐路车进行判断通过每个站点情况，逐行填充该 矩阵。上述列子的矩阵构造如下：108256652154053870277557564572广埠屯11111110000街道口11111111000洪山111

50、11011000付家坡11111011110大东门11100011111火车站10100001111站点车次矩阵 m_proutestation14计算 m_proutestation1 矩阵得到一新矩阵 m_proutestation2。其中m_proutestation2ij=m_proutestation1nj108256652154053870277557564572广埠屯11111110000街道口22222221000洪山33333232000付家坡44444243110大东门55544254221火车站65644255332站点车次矩阵 m_proutestation2在具体的实

51、现过程中就可以对 m_proutestation2 进行判断，从而得到最 佳的乘车方案。421 最佳乘车方案的递归算法其递归判断过程如下：1、直达：对 m_proutestation2 的第 n 行（即第 6 行）进行判断，如果 m_proutestation2nj=n,（j=1 m）那么第 j 次车可以从起始站点直达终 止站点2、换车次数=1：从 m_proutestation2 的第 n-i（i=1 n-1）行开始判 断，如果 m_proutestation2n-ij=n-i( j=1 m),计算矩阵的第 n-i+1 行到 第 n 行,如果 m_proutestation2nj- m_proutestation2n-i+1j=i,即满 足 从 站 点n-i+1直 达 站 点n 。 那 么m_proutestati