分布式環(huán)境下基于路徑阻斷的APSP算法研究.pdf

1、隨著大數(shù)據(jù)時(shí)代的到來，數(shù)據(jù)成爆炸式增長，隨之出現(xiàn)的網(wǎng)絡(luò)規(guī)模越來越大，網(wǎng)絡(luò)結(jié)構(gòu)也越來越復(fù)雜。在大規(guī)模復(fù)雜關(guān)系網(wǎng)絡(luò)中蘊(yùn)含著巨大的研究價(jià)值，其中求解全源最短路徑(All Pairs Shortest Paths，APSP)是研究大規(guī)模復(fù)雜網(wǎng)絡(luò)的一個(gè)基本問題。傳統(tǒng)的求解APSP的算法在大規(guī)模復(fù)雜網(wǎng)絡(luò)下效率不高，而引入路徑阻斷的算法相對于傳統(tǒng)的算法在復(fù)雜網(wǎng)絡(luò)下表現(xiàn)出較好的性能。由于大規(guī)模復(fù)雜網(wǎng)絡(luò)中，數(shù)據(jù)量較大，在單機(jī)下計(jì)算速度較慢，因此，本文提出

2、分布式環(huán)境下引入路徑阻斷的BFS算法來解決大規(guī)模復(fù)雜網(wǎng)絡(luò)下求解APSP的問題。
　　首先本課題在志愿計(jì)算框架下對引入路徑阻斷的算法進(jìn)行闡述，并通過實(shí)驗(yàn)證明，在大規(guī)模復(fù)雜網(wǎng)絡(luò)下，引入路徑阻斷的算法比傳統(tǒng)的算法效率要高。
　　其次，通過對引入路徑阻斷的算法進(jìn)行分析，提出三種優(yōu)化策略，即基于層數(shù)，基于入隊(duì)個(gè)數(shù)，以及基于層數(shù)和入隊(duì)個(gè)數(shù)。這三種優(yōu)化策略通過嚴(yán)格阻斷點(diǎn)條件，阻止不適合的阻斷點(diǎn)進(jìn)入阻斷過程，從而提高算法效率。
　　最