共查询到20条相似文献,搜索用时 203 毫秒
1.
Dijkstra 最短路径算法的一种高效率实现 总被引:14,自引:1,他引:13
在已存在的一些最短路径算法测试总结的基础上,根据GIS中网络计算的实际情况,从网络结构的拓扑表示以及Dijkstra 算法中快速搜索技术的实现入手,提出了一种Dijkstra 最短路径算法的高效率实现方法。 相似文献
2.
3.
首先介绍了城市交通的重要性,接着进一步阐述了Dijkstra算法及其实现在城市交通中的应用占有的重要地位。从GIS中网络最短路径算法的实际情况出发,基于MapX以及网络拓扑结构的表示与建立,以及Dijkstra算法搜索技术的实现入手,最终实现了Dijkstra最短路径算法与其在城市交通查询中的应用。本文就以经典的最短路径算法——Dijkstra算法为原理,基于MapX在VisualBasic平台对其算法研究、验证,最终得出该算法的可行性。 相似文献
4.
GIS中最短路径算法的改进实现 总被引:14,自引:1,他引:13
针对GIS中网络拓扑图的一般特点和对网络分析实时性的要求,以Dijkstra最短路径算法为理论基础,采用快速排序和插入排序相结合的方式,使用地址排序的方法,改进原有最短路径算法中对最小权值的顶点的搜索策略,提出一种高效的实用的Di-jkstra最短路径算法的实现方法. 相似文献
5.
6.
最短路径问题是交通网络分析中的一个重要问题,也是交通地理信息系统中的一个研究热点。国内外大量专家学者对此问题进行过深入研究。最短路径问题可分为单源最短路径问题及全源最短路径问题两种。其中,单源最短路径问题更具有普遍意义。单源最短路径问题的算法有很多种,代表性的有基于邻接矩阵的Dijkstra算法、最大相关边法、最大相关点法,基于邻接表的Dijkstra算法、A*算法等等;纵观该方向的研究状况,人们对最短路径分析的分类及其实现算法和应用研究较多,而对交通中的限制条件研究较少。 相似文献
7.
文章针对Dijkstra和Floyd算法特点及在智能运输中的特点,将两种算法结合起来,形成求解物流配送中两点间最短路径的优化算法-混合算法.该方法用Floyd计算多对顶点之间的最短路径,在路径中少数顶点之间的邻接关系发生变化时,利用Dijkstra计算这些顶点之间的最短路径,加上其余部分路径就得到该图中各对顶点之间的新的最短路径,在约束条件下最终求出各点间最短路径.实验证明,混合算法比Dijkstra及Floyd效率提高11%-20%.本文研究结果可对物流配送中最短路径的选择有所帮助. 相似文献
8.
9.
10.
单源最短路径算法的图示教学设计与实践 总被引:1,自引:1,他引:0
单源最短路径是GIS网络分析的一个重点内容,对GIS、空间信息技术等相关专业的学生来讲,由于经典的最短路径算法(Dijkstra)描述较抽象,让学生掌握单源最短路径算法的本质思想较难。提出用图示教学法来教授GIS中单源最短路径算法的基本原理和思路,详细介绍了图示表示的过程,可以为最短路径算法及其应用的教学过程提供参考。 相似文献
11.
Dijkstra最短路径算法改进研究及其在GIS-T仿真分析中的应用 总被引:1,自引:0,他引:1
Dijkstra算法是求解最短路径问题的经典算法,但在实际应用中还存在一些问题。提出了对传统的Dijkstra最短路径算法改进的新方法,即对复杂的公路网数据进行预处理,生成路网拓扑结构数据文件,并结合Dijkstra算法按路径长度递增次序产生最短路径的思想来求解公路网复杂线状图形的最短路径问题。 相似文献
12.
李卫江 《测绘与空间地理信息》2007,30(6):15-18
最短路径算法是GIS空间分析研究的热点问题。本文将最短路径的实时计算转换为预计算,利用关系数据库将最短路径计算过程和结果实例化,并在W ebGIS环境下实现了城市任意两点之间最短路径的快速计算和响应。 相似文献
13.
最短路径算法是GIS空间分析研究的热点问题。本文将最短路径的实时计算转换为预计算,利用关系数据库将最短路径计算过程和结果实例化,并在WebGIS环境下实现了城市任意两点之间最短路径的快速计算和响应。 相似文献
14.
VC环境下最短路径算法的实现 总被引:1,自引:0,他引:1
设计了一种方便查找及显示最短路径的数据结构,对仅研究计算一条最短路径的Dijkstra算法加以了改进,并在VC下实现一个顶点到另一个顶点的所有最短路径的查找。 相似文献
15.
最短路径算法:分类体系与研究进展 总被引:76,自引:3,他引:76
最短路径算法是计算机科学与地理信息科学等领域的研究热点。本文首先讨论了平面图的搜索策略,然后从问题类型、网络类型和实现方法3方面对最短路径算法进行了系统的分类,从理论上比较了近年来所提出的各具有较高效率的串行最短路径算法的时间复杂度,并对国内外一些相关研究进行了综合评述,结合城市交通网络的实验结果,作者对几种应用最为广泛的串行最短路径算法的运行效率进行了分析和评价,最后对最短路径算法在实时化和并行化方面的发展进行了讨论。 相似文献
16.
17.
在最短路径操作算法的基础上 ,给出了最短路径操作不确定性的算法及流程图。实例演算了不确定性的传播模型。研究结果表明 ,最短路径操作结果的绝对不确定性 :(1)与最短路径操作经过的点数成正向关系 ,更进一步 ,最短路径的几何路径曲率越大 ,最短路径操作带来的不确定性越大。 (2 )与最短路径经过的各相邻顶点间的距离长短没有直接关系 ;(3)与经过的各顶点的误差成正向关系。GIS中进行最短路径操作时减小操作结果不确定性的方法是 :(1)提高最短路径经过顶点的点位精度 ;(2 )减少最短路径经过顶点数目 相似文献
18.
在最短路径操作算法的基础上 ,给出了最短路径操作不确定性的算法及流程图。实例演算了不确定性的传播模型。研究结果表明 ,最短路径操作结果的绝对不确定性 :(1)与最短路径操作经过的点数成正向关系 ,更进一步 ,最短路径的几何路径曲率越大 ,最短路径操作带来的不确定性越大。 (2 )与最短路径经过的各相邻顶点间的距离长短没有直接关系 ;(3)与经过的各顶点的误差成正向关系。GIS中进行最短路径操作时减小操作结果不确定性的方法是 :(1)提高最短路径经过顶点的点位精度 ;(2 )减少最短路径经过顶点数目 相似文献
19.
20.
pgRouting作为开源PostGIS空间数据库扩展路径规划项目,是对开源WebGIS中路径规划的创新.本文提出了如何在开源平台,将Dijkstra算法应用到WebGIS最短路径查询的方法.利用PostGIS开源项目pgRouting,结合Openlayers调用和Geoserver发布地图,利用OSM数据实现起始点定位查询最短路径的方法策略,并给出相关流程和配置安装的步骤.最后以昆明市道路数据验证了WebGIS中最短路径的方法. 相似文献