文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 自然科学 > 天文/地理 > 基于数据库中间件与GIS实现的最短路径算法
侵权投诉

基于数据库中间件与GIS实现的最短路径算法

计 算 机 工 程 第 31 卷 第13期

Vol.31 № 13 Computer Engineering · 软件技术与数据库 ·

文章编号:1000—3428(2005)13—0078—03

文献标识码:A

2005年7月

July 2005

中图分类号:TP311

基于数据库中间件与GIS实现的最短路径算法

倪 凯1,叶 雷2,鲁 铭1,张 超1

(1.华东师范大学地理信息科学教育部重点实验室,上海 200062; 2.上海商学院连锁经营系,上海 200255)

摘 要: 地理信息系统中的空间网络分析有最短路径分析、资源分配分析、等时性分析等等, 而最短路径分析是其中关键的环节, 因而对其算法进行优化很有必要, 为此在传统的最短路径算法, 即Dikstra 算法的基础上, 采用关系数据库的存储机制,实现对最短路径查询,不但降低了系统的开销,而且较好地解决空间数据访问的并发控制问题和数据安全性问题。通过具体案例分析表明, 该方法是有效可行的。 关键词:Dijkstra算法; 最短路径; 数据库中间件; 地理信息系统

Implementation of Shortest Path Algorithm

Based on Database Middle-ware & GIS

NI Kai1, YE Lei2, LU Ming1, ZHANG Chao1

(1.Key Laboratory of Geographic Information Science, Ministry of Education, ECNU ,Shanghai 200062;

2.Department of Chain, Shanghai Business School, Shanghai 200255 )

【Abstract】In GIS, it is necessary to optimize the analysis function of the shortest path as the hinge of spatial network analysis, which includesshortest path analysis, resource allocation and isochrone, and so on. Here derived from the traditional calculating method, ie. Dijkstra algorithm, thequery about shortest path is based on relationship database. This technique not only solves the problem of spatial data sharing but also improvetheefficiency of computer system.

【Key words】Dijkstra algorithm; Shortest path; Database middle-ware; GIS

在空间信息分析中,网络分析是GIS 核心功能之一。 网络分析中最基本问题是最短路径问题,在交通网络分析系统中,它说明任意两个结点间的最短距离通路。从网络模型的角度看,最短路径分析是指在指定网络中两结点之间找一条阻碍强度最小的路径,根据阻碍强度的不同定义,最短路径不仅仅指一般地理意义上的距离最短,还可以引申到其它的度量,如时间、费用、线路容量等。最短路径问题作为许多领域中选择最优问题的基础,广泛应用于汽车导航系统以及各种应急系统等中,如110报警、119火警以及医疗救护系统,特别是SARS传染疾病的出现,使地理信息系统中对最短路径的分析具有特别重要的意义。

抽象为图的结构。这就需要先对原始道路图进行处理,建立

其相应的网络拓扑关系。处理的工作主要包括: (1) 对原始的道路图进行线元素的拓扑检查, 生成线和线相互交叉的道路图; (2) 对道路图创建拓扑关系,并定义其属性特征,如起始节点、终止节点、道路名称、道路距离等; (3) 生成有拓扑关系的拓扑文件; (4) 选取合适算法进行最短路径的计算。 1.2 最短路径的算法

关于最短路径的算法,目前所公认的最好的求解方法是1959年由E.W.Dijkstra提出的标号法。该方法之所以被称为标号法,是因为这个方法在求解过程的每一个步骤中,都对于网络图中的每一个顶点赋予一个或几个相应的数,这个数或这些数就称为该顶点的标号。这个算法的一个突出优点是:它不仅可以求出起点致终点的最短路径及其长度,而且可以求出起点到其它任何一个顶点的最短路径及其长度。

设G =(V ,A)是一个赋权有向图,即对于图中的每一条边e =(vi ,vj) 都赋予了一个权值wij 。在图G 中指定两个顶点,确定为起点各终点,不妨设v1 为起点vk 为终点。标号法的基本思想是:首先从v1 开始,给第1个顶点标一个数(称为标号);标号分P 标号和T 标号两种,P 标号表示从起点v1 到该点最短路径权的上界,称为临时标号;P 标号表示从v1 到该点的最短路权,称为固定标号。已得到P 标号的顶点不再改变,凡是没有标上P 标号的顶点,标上T 标

基金项目:上海科技发展基金资助项目(02DZ15003-01)

作者简介:倪 凯(1968─),男,硕士生,主研方向:地理信息系统,WebGIS;叶 雷、鲁 铭,博士生;张 超,教授、博导 定稿日期:2005-02-11 E-mail:ecnunk@163.com

1最短路径问题

1.1 何为最短路径

最优路径是基于数据结构中图的理论而产生,从数据结构的角度说,它是对图的一种搜索和权值的相加,此处的权表示为从一个顶点到另一个顶点的距离或耗费。在地理网络中权可以代表多种不同的含义。如纯距离意义上的最短路径、经济距离上的最短路径和时间意义上最短路径等。对于城市交通网说,更关心的是纯距离意义上最短路径。

要对城市道路网进行最短路径分析,首先必须将现实中的城市道路网络实体抽象化为网络图论理论中的网络图, 然后通过图论中的网络分析理论来实现道路网络的最短路径分析。在实际应用中,城市道路网的表现形式一般为数字化的矢量地图,其网络空间特征中的交叉路口坐标和道路位置坐标是在地图上借助图形来识别和解释的; 而为了能够高效率地进行最短路径分析,必须首先将其按结点和弧的关系 —78—

第1页

你可能喜欢

  • GIS最短路径
  • 弗洛伊德算法
  • Floyd算法
  • Dijkstra算法
  • 消防规划
  • 应急物资调度
  • 蚁群算法

热门文档

相关文档

  • 最短路径算法在GIS中的应用与分析

    最短路径算法在GIS中的应用与分析_IT/计算机_专业资料。最短路径算法... 就不能直接采用 Dijkstra 最短路径算法来实现, 主 要有以下原因: 1)数据...

  • GIS网络分析中最短路径的实现

    GIS网络分析中最短路径的实现_IT/计算机_专业资料。GIS网络分析中最短路径的...了一种基于矢量角度的最短路径搜索算法,设计出一种类似于面向对象的数据存储结构...

  • 基于MapX和数据库的最短路径搜索算法及实现

    http://www.paper.edu.cn 基于 MapX 和数据库的最短路径搜索算法及实现常...引言地理信息系统(GIS)是一个集计算机科学、地理信息学和空间科学等的产物,它...

  • GIS城市道路最短路径算法研究

    [2] [1] 2 公交网络空间数据库特点 GIS 中的数据(如道路、管网、线路等)...从上面可以看出,在按标记法实现 Dijkstra 算法的过程中,核心步骤就是从未标记的...

  • 中间件在GIS开发中的应用

    介绍中间件的一些作用以及在 GIS 开发中的应用 ,并着重介绍基于中间件技术开始...采用 COM 组件实现对数据库的连接 , GeoServ2 er 中间件不仅可以多个用户请求...

  • GIS中最短路径搜索算法

    GIS中最短路径搜索算法_IT/计算机_专业资料。GIS最短路径算法的研究实现维普资讯 http://www.cqvip.com GI S中最 短 路径 搜 索算 法李春葆 (汉大学计 ...

  • GIS的路径分析算法及实现

    地理信息系统 ( GIS) 是综合处理和分析空间数据的技术系统 。它集成了多学科的...第 1 期 张文君 ,等 GIS 的路径分析算法及实现 53 2. 3 基于 MAP GIS ...

  • 最短路径在GIS中的实现和应用

    (GIS) 是以计算机图形图像处理、数据库 技术、测绘遥感技术及现代数学研究方法为...本文正是立足于该问题,利用ESRI 公司的GIS 软 件实现了传统的最短路径算法,...

  • GIS城市道路最短路径算法研究

    2 公交网络空间数据库特点 GIS 中的数据( 如道路、 管网、线路等) 要进行最...从上面可以看出,在按标记法实现 Dijkstra 算法的过程 中,核心步骤就是从未标记...

  • 基于GIS和改进遗传算法的最优路径规划

    基于GIS 和改进遗传算法的最优路径规划蔡 , 崔 , 丁 , 蔡 菲健宁 (11 ...数据库 , 利用 Map Info 公司的空间数据引擎 SpatialWare 作为中间件 , 实现 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email