随着人口往城市的快速迁移,全球道路网的规模在不断地扩大,高效、快速的从庞大的道路网数据中计算两点之间的最短路径,成为了学术界和工业界众多研发人员的研究课题。经过多年的研究,学者们已经提出了诸多相关算法,例如Dijkstra算法、CH算法(Construction Hierarchies Algorithm)、Arc-Flag算法、Highway Hierarchies算法,以及一些结合智能算法的最短路径算法。但是如何通过减少数据搜索空间,从而达到有效降低查询时间这一问题仍然未能得到良好的解决。本文针对从大规模道路网数据中查询两点之间最短路径存在时间消耗较大的问题,分析研究了实际道路之间的限制关系,提出了一种基于节点度的大规模道路网数据划分方法,在此基础上,给出有效可行的解决方案,同时也保证了算法的性能。论文的主要工作如下:(1)提出了一种基于节点度的道路划分算法,以解决划分道路网数据时容易将节点分布密集的区域划分在不同的子网内的问题。首先,该算法根据实际道路之间的限制关系处理并存储道路网数据;其次,设置划分后的子网内最大节点数量,然后利用Kd-tree划分道路网数据,并标记划分后的子网的最大节点度;最后,比较子网内的最大节点的度与边界节点的度,若边界节点的度与最大节点的度相等,则说明该边界节点位于节点分布密集的区域,进行相邻节点的合并。实验结果表明,该算法在一定程度上提高了划分后的子网的独立性。(2)优化了基于划分的最短路径查询算法的查询效率,以解决大规模道路网中查询最短路径时空间消耗巨大,以及起始节点和目标节点相距较近时查询效率低的问题。首先,根据道路的特性将道路网数据分层划分;其次,设定子网内节点数量为层次收缩最短路径算法能够处理的最大节点数量,并使用基于节点度的道路划分算法划分道路网数据;然后,获取道路网数据划分后的边界节点集合并建立边界节点最短路径查询表;最后,通过判断输入的起始节点和目标节点是否属于同一子网,选择不同的最短路径搜索策略。若两节点在同一子网内,则根据子网内的节点的重要性双向搜索最短路径。(3)针对本文提出的最短路径查询算法,使用了大量的实验进行验证。实验结果表明,与经典的基于道路网划分的最短路径算法相比,本文算法减少了空间消耗,同时缩短了查询时间。(4)基于C#和OpenStreetMap,开发了最短路径查询的动态链接库,实现了建立有转向限制的道路网数据库和道路网数据的划分功能,并对最短路径查询功能进行封装,通过调用示例证明动态链接库的可靠性。