论文部分内容阅读
最短路径算法是人工智能、通信、交通及规划等领域经常使用的算法,利用它可以快速地寻找起始点到目标点之间的最短路径,从而节省时间,为工业生产及人类的生活提供便利。由于路径分析在许多方面具有非常广泛的应用,因此对最短路径算法的研究一直在不断的进行。随着计算机技术的发展与完善,出现了许多新的最短路径算法,和原始的最短路径算法相比,这些新算法复杂度小,更加容易实现性而且应用范围较广。
随着GIS的发展路径分析也得到了更为广泛的应用。近年来,随着网络地理信息系统的普及和发展,最短路径分析逐渐扩展到WebGIS领域,目前国内外的GIS软件均已实现最短路径分析功能。
目前多数GIS系统解决最短路径问题时均采用Dijkstra算法,该算法的优点是程序设计比较简单、应用范围广,缺点是使用该算法寻求最短路径时不是专门针对特定的两点。而在GIS系统中,最短路径的寻找往往是针对特定两个点之间的最短路径,因而此算法在在GIS系统中效率较低。由此可见,针对GIS中路径分析的实际情况有必要对原始的Dijkstra最短路径算法进行相关的改进。
已有的GIS系统对Dijkstra算法采用了很多不同的方法进行改进,本文比较了目前较典型的两种优化方法,快速搜索优化和距离优化,由于快速搜索优化在大数据量的情况下优化效果较好,而且目前出现了多种对快速排序进行优化的方法,因此本实验采用了对快速搜索优化中的快速排序进行改性的方法对原始的Dijkstra算法进行进一步的优化,最后在综合风险空间数据发布系统中对该算法进行了编程,实现了WebGIS系统中的最短路径分析。