如果說手繪圖本身是面子，讓人對地圖有第一印象和直觀感受，那么實(shí)時(shí)導(dǎo)航功能則是地圖的靈魂和里子。沒有實(shí)時(shí)定位和動(dòng)態(tài)路徑規(guī)劃導(dǎo)航功能的地圖，只是一個(gè)可觀而不可用的花瓶，沒有使用價(jià)值。沒有準(zhǔn)確的而高效的實(shí)時(shí)導(dǎo)航算法，就不能把地圖價(jià)值在游客手里發(fā)揮到最大。

一、實(shí)時(shí)導(dǎo)航的最短路徑算法

bellman-ford：可以用于邊權(quán)為負(fù)的圖，圖中如果有負(fù)環(huán)，算法會檢測出負(fù)環(huán)。時(shí)間復(fù)雜度O（VE）。

spfa：bellman-ford的優(yōu)化算法，本質(zhì)是bellman-ford，所以適用性和bellman-ford一樣。時(shí)間復(fù)雜度O（KE）。

dijkstra：只能用于邊權(quán)都為正的圖中。時(shí)間復(fù)雜度O（n2）。

floyd：也可以用于有負(fù)權(quán)的圖中，即使有負(fù)環(huán)，算法也可以檢測出來。可以求任意點(diǎn)的最短路徑，有向圖和無向圖的最小環(huán)和最大環(huán)。時(shí)間復(fù)雜度O（n3）。

二、實(shí)時(shí)導(dǎo)航的方向指引

實(shí)現(xiàn)了方向的指引，則手繪地圖導(dǎo)航功能的基礎(chǔ)已經(jīng)具備。

三、實(shí)時(shí)導(dǎo)航的路徑信息

類似于地圖APP的導(dǎo)航功能，直行、轉(zhuǎn)向等方向提示可以極大的增加導(dǎo)航的使用體驗(yàn)和實(shí)用效果。對于這一點(diǎn)，也可以通過設(shè)計(jì)算法實(shí)現(xiàn)。簡單來說，可以通過用戶前進(jìn)的方向，結(jié)合規(guī)劃的路徑，來判斷前方應(yīng)當(dāng)如何轉(zhuǎn)向。當(dāng)然，這里的細(xì)節(jié)比較復(fù)雜，就不展開贅述。而還需要注意的一點(diǎn)就是，判斷用戶是否已經(jīng)偏移路線。

四、實(shí)時(shí)導(dǎo)航的智能糾偏

當(dāng)然，對于確實(shí)偏移過大的情況，也不能強(qiáng)行糾偏。因?yàn)檫@種情況，我們其實(shí)是不知道到底是用戶確實(shí)已經(jīng)偏離太大，還是手機(jī)定位出現(xiàn)的較大誤差。這時(shí)可以根據(jù)實(shí)際情況提示用戶已經(jīng)偏移路線，或者待手機(jī)定位自動(dòng)恢復(fù)正常。

五、演示案例

視頻展示一個(gè)示例。