1、最短路徑查詢是圖論研究中的熱點問題之一，最短路徑查詢在很多領(lǐng)域中扮演著最基本也最重要的角色，包括城市交通網(wǎng)絡(luò)、社交網(wǎng)絡(luò)、生物信息網(wǎng)絡(luò)等。目前最短路徑查詢算法主要有兩類，一類是精確最短路徑查詢，一類是近似最短路徑查詢，本文主要研究精確最短路徑查詢問題。具體研究內(nèi)容如下。
　　首先，通過對現(xiàn)有算法進行分析，發(fā)現(xiàn)現(xiàn)有算法存在構(gòu)建索引時間長和索引規(guī)模龐大所導(dǎo)致的低效性和擴展性問題。
　　其次，在索引構(gòu)建方面，提出了三種索引構(gòu)建策略。

2、對度數(shù)為1的頂點，構(gòu)建頂點關(guān)聯(lián)索引；對單枝路徑上的頂點，構(gòu)建路徑關(guān)聯(lián)索引；對其他頂點，提出了基于部分頂點進行遍歷來構(gòu)建2-hop標簽索引的方法，通過減少冗余數(shù)據(jù)存儲和圖的遍歷次數(shù)，降低了索引規(guī)模，減少了構(gòu)建索引時間。
　　再次，在最短路徑查詢方面，針對不同的索引構(gòu)建策略，提出相應(yīng)的查詢策略。對頂點關(guān)聯(lián)索引，利用頂點關(guān)聯(lián)關(guān)系和2-hop標簽來回答最短路徑查詢；對路徑關(guān)聯(lián)索引，利用路徑關(guān)聯(lián)關(guān)系和2-hop標簽來回答最短路徑查詢；對部分