最短路径查询用于返回图中两点之间的最短路径,是图数据管理中的核心操作之一,一直以来都是研究者关注的热点问题。最短路径查询广泛应用在各种道路交通网络、社会网络、生物信息网络中对数据进行分析。随着实际中数据图规模的不断增大和应用领域的不断扩张,最短路径查询处理效率的进一步提升是亟待解决的关键问题。本文针对无向无权图的最短路径查询问题进行研究,具体研究如下:首先,针对实际中数据图比较稀疏且服从幂律分布的特点,提出对原始图进行分割,分别处理的策略。该策略首先从原始图中删除单枝路径来得到一个规模缩减的图。对单枝路径,利用顶点在路径中的相对位置对顶点进行编码,快速计算路径内顶点间的最短距离。对简化图,构建基于简化图的地标标签索引,用于快速求解简化图上顶点对的最短路径。其次,基于单枝路径索引和简化图索引,提出一种高效的最短路径求解方法。该方法的基本思想是:给定两个查询点,如果这两个点同时位于单枝路径或简化图中,则用相应的单枝路径索引或地标标签索引进行快速求解;否则,先查找两个顶点在简化图上的基点,通过计算基点之间的最短路径,以及基点和查询点的最短路径来得到最终的查询回答结果。最后,利用现实当中的数据集进行检验和验证,从构建标签索引时间和规模,以及查询的响应时间等方面与现有方法做对比,来分析验证本文提出方法的高效性。