最短路径查询是图论研究中的热点问题之一,最短路径查询在很多领域中扮演着最基本也最重要的角色,包括城市交通网络、社交网络、生物信息网络等。目前最短路径查询算法主要有两类,一类是精确最短路径查询,一类是近似最短路径查询,本文主要研究精确最短路径查询问题。具体研究内容如下。首先,通过对现有算法进行分析,发现现有算法存在构建索引时间长和索引规模庞大所导致的低效性和扩展性问题。其次,在索引构建方面,提出了三种索引构建策略。对度数为1的顶点,构建顶点关联索引;对单枝路径上的顶点,构建路径关联索引;对其他顶点,提出了基于部分顶点进行遍历来构建2-hop标签索引的方法,通过减少冗余数据存储和图的遍历次数,降低了索引规模,减少了构建索引时间。再次,在最短路径查询方面,针对不同的索引构建策略,提出相应的查询策略。对顶点关联索引,利用顶点关联关系和2-hop标签来回答最短路径查询;对路径关联索引,利用路径关联关系和2-hop标签来回答最短路径查询;对部分2-hop标签索引,利用2-hop标签结合图遍历的方式来回答最短路径查询。最后,基于15个真实的数据集进行测试,实验结果从构建索引时间、索引规模大小、查询响应时间等方面验证了本文方法相对于现有方法的高效性。