本文觀點(diǎn)翻譯至Ron Gutman和Andrew V.Goldberg的兩篇論文。經(jīng)過(guò)實(shí)際中國(guó)地圖測(cè)試，對(duì)于dijkstra和A*算法均能大大的減少edge探索數(shù)目(探索范圍沒(méi)有明顯減少，但稀疏度大大提高)，能相對(duì)與不使用Reach-V剔除90%以上的節(jié)點(diǎn)。

定義： 

定義頂點(diǎn)reach值：一條通過(guò)該頂點(diǎn)的最短路徑中的被該點(diǎn)分割的較短那部分路徑的長(zhǎng)度。

定義頂點(diǎn)reach估計(jì)值(reach-v)：所有通過(guò)該點(diǎn)的最短路徑中的reach值的最大值。

舉例：

對(duì)于如圖所示的雙向圖reach-v(B) = 12,其余各個(gè)頂點(diǎn)的reach-v全為0。

算法中的用法：
以dijkstra為例，假設(shè)當(dāng)前算路的起點(diǎn)終點(diǎn)分別為S，T。當(dāng)前探索點(diǎn)為V，記m(p)為從S到V的最短路徑長(zhǎng)度，記d(V,T)為從V到T的歐幾里得距離。
如果reach-v(V) < m(p) && reach-v(V) < d(V,T)則排除掉V點(diǎn)(不探索)。
對(duì)于A*算法同理，m(p)對(duì)應(yīng)于A*中的G，d(V,T)對(duì)應(yīng)于A*的H。

Reach-V值的計(jì)算:
由于對(duì)所有節(jié)點(diǎn)都做全圖的dijkstra規(guī)模過(guò)于龐大，對(duì)于幾千萬(wàn)上億個(gè)節(jié)點(diǎn)的地圖運(yùn)算時(shí)間會(huì)達(dá)到幾年，所以實(shí)際中一般都是選取一個(gè)合適的Reach-V值上界，以在預(yù)處理時(shí)間和時(shí)間剔除效果間做一個(gè)平衡。
以下將著重介紹一種P-Tree思想來(lái)對(duì)每個(gè)節(jié)點(diǎn)做dijkstra。P-Tree顧名思義就是對(duì)每個(gè)節(jié)點(diǎn)不做全圖的dijkstra，而是設(shè)定一個(gè)停止條件以產(chǎn)生一棵局部最短路徑樹(shù)。(待續(xù))