最短路徑查詢(xún)方法研究.pdf

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

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