论文部分内容阅读
随着计算机的普及以及地理信息科学的发展,GIS因其强大的功能得到日益广泛和深入的应用。GIS网络分析是GIS的研究热点和难点,而最短路径问题是GIS网络分析中最基本和最关键的问题,在许多方面具有直接的应用价值,人们对最短径算法的深入研究也从未间断过。经典的图论与不断发展完善的计算机数据结构及算法的有效结合使得新的最短路径算法不断涌现。它们在空间复杂度、时间复杂度、易实现性及应用范围等方面各具特色。Dijkstra算法是目前多数系统解决最短路径问题的理论基础。Dijkstra算法的优点是程序设计简单、通用性强。缺点是该算法不是专门针对特定两点的,而在GIS的最短路径寻找中,往往是寻找两个特定点之间的最短或近似最短路径,因而此算法在这方面效率较低;另外,传统的Dijkstra算法采用邻接矩阵数据结构,占用空间十分巨大,严重浪费计算机的资源,很不适合GIS中结点量巨大的实际情况。因此,在GIS的实际应用中,针对GIS应用的实际情况对基于Dijkstra的最短路径算法进行改进是完全有必要的。基于Dijkstra算法的理论基础并针对GIS路径分析的特点,已有的应用系统对Dijkstra算法采用了很多不同的改进方法。鉴于GIS的广泛应用和Dijkstra算法在该应用中的运行效率的重要性,本文通过对Dijkstra最短路径算法的分析,充分利用GIS中空间分布特征,针对GIS中搜索两个特定点的最短路径的应用,从数据结构、搜索技术及算法本身对Dijkstra最短路径搜索算法提出了优化和改进,使之更加适合于在GIS两个特定点之间的最短路径查找。本文主要研究工作包括:①研究了经典Dijkstra算法的主要思想及其实现;讨论了平面图搜索策略,从问题类型、网络类型和实现方法三个方面对最短路径算法进行系统分类;②研究了GIS中的数据结构;分析了各种最短路径算法思想及其应用的数据结构以及各种数据结构的特性;③对最短路径算法在实时化和并行化方面的发展进行了讨论;④研究了GIS空间分布特征;结合GIS公路交通中查找最短路径的具体情况,分析了传统最短路径算法在这种特定应用中的不足,提出了一个充分利用GIS中空间分布特征的改进算法,对传统Dijkstra算法的路径搜索提出了一种新的搜索思想,即方向优先搜索。最后编程实现了该改进算法,通过实验验证了该算法的有效性。