数字高程模型(Digital Elevation Model,DEM)已成为空间地形分析中的主要数据模型,基于DEM地形数据的路径规划问题也成为研究的热点。最短路径问题是图论中经典问题,已被广泛应用于机器人路径规划,旅行商问题(Traveling Salesman Problem,TSP),电子地图导航等方面。作为求解单源点问题的经典算法,Dijkstra算法可有效、准确地求解出图结构中单点源的全局最优路径。经典Dijkstra算法的时间复杂度为O(n2),使用最小堆存储结构可使其时间复杂度降为O(nlogn)。但对于求解地形数据的最短路径问题,随着节点数或边数增加,算法时间将会呈指数级增长,其效率也随之降低。面对大规模三维地形数据,Dijkstra算法却难以胜任。因此,如何使Dijkstra算法更好地求解大范围高精度的栅格DEM地形数据的最短路径成为重要的研究问题之一。本文主要工作如下:1)提出了一种快速的转化地形数据的最短路径方法。根据地形格网邻域模型,本文将离散地形数据转化为图数据,利用DEM相关地形信息,通过剪枝删除不符合条件的节点之间的边,以减少图数据量。同时,数据转化过程可通过并行化方法来实现,从而提高路径算法的效率。在转换为图数据之后,Dijkstra算法用于求解基于图数据的最短路径。实验结果表明,本文提出的地形最短路径求解大大提高了算法的效率,并保证了结果的准确性。2)提出了一种基于MapReduce的Dijkstra并行化算法的网络优化方法。依据串行Dijkstra算法数据并行化特点,本文基于MapReduce并行计算框架,根据广度优先算法思想,实现了基于MapReduce的Dijkstra算法并行化方法。本文通过在Shuffle阶段合并关键字方法来减少网络通信开销,优化了算法并行化处理的效率。实验结果表明,该方法大大提高了基于大规模地形数据时求解最短路径的效率。3)提出了一种基于瓦片金字塔模型的最短路径加速方法。依据瓦片金字塔模型,本文采用同一区域范围不同分辨率DEM地形数据表示方法,利用层次空间关系将低分辨率地形数据映射到相应的高分辨率地形数据上。本文依据低分辨地形数据进行路径求解可有效地缩小高分辨率地形数据上的求解范围,从而提高算法求解效率。实验结果表明,该方法有效抑制搜索区域中节点数增加,大大提高算法的效率。