動(dòng)態(tài)路網(wǎng)上最短路徑算法研究.pdf

1、在道路網(wǎng)上精確計(jì)算點(diǎn)對(duì)點(diǎn)最短路徑是圖論算法的眾多實(shí)際應(yīng)用之一。經(jīng)典的Dijkstra算法及其變種雙向Dijkstra搜索算法在大規(guī)模道路網(wǎng)上過(guò)于緩慢，早已力不從心。有幸的是在過(guò)去十年間，這個(gè)經(jīng)典問(wèn)題受到大量關(guān)注，尤其在大規(guī)模道路網(wǎng)上取得了極其重要的突破，目前很多算法的運(yùn)行效率比Dijkstra算法快了好幾個(gè)數(shù)量級(jí)。目標(biāo)向?qū)Х椒ê蛯哟位椒ㄊ莾深愖罹叽硇缘姆椒?，它們各自?jīng)歷過(guò)一段快速發(fā)展時(shí)期。此外，將兩類方法巧妙地結(jié)合起來(lái)能夠在各方面都

2、取得最佳效果。盡管實(shí)驗(yàn)表明這些算法性能良好，卻缺乏理論分析的支撐。這是因?yàn)?，道路網(wǎng)雖有一些性質(zhì)，卻無(wú)法嚴(yán)格地對(duì)它下定義。這些性質(zhì)包括稀疏性、近乎可平面性以及層次化特性。
　　然而，現(xiàn)有的算法大都只適應(yīng)處理靜態(tài)網(wǎng)絡(luò)，它們需要較長(zhǎng)的時(shí)間進(jìn)行預(yù)處理，以產(chǎn)生足夠的輔助數(shù)據(jù)來(lái)加速最短路徑查詢。因此，這些加速技術(shù)難以應(yīng)付邊權(quán)重經(jīng)常變化的動(dòng)態(tài)路網(wǎng)，諸如交通堵塞或者檢修路況等，即使權(quán)重變化的邊集只占整個(gè)路網(wǎng)的一小部分。鑒于現(xiàn)有的最快算法Trans