至今，我偶爾會遇到一些尋路的尋求，雖然是偶爾，但時間久了，也就多了。

我對尋路是沒有太多研究的，所以就去B站搜了一下，搜到一個很棒的dikjstra教程。

我照著這個教程，用ts寫了一下這個邏輯，分享給大家。

整體代碼如下：

最終，console.log(optimal) 輸出的結(jié)果就是：[4, 5, 6, 7, 0]

這與dikjstra教程里的結(jié)果是一致的。

根據(jù)這個教程內(nèi)容，做個筆記。

已知：

• 節(jié)點關(guān)系map，即每個節(jié)點的鄰點

• 節(jié)點距離segmentLengthMap，存在聯(lián)系的兩個節(jié)點間的距離

• 起點start為0

• 終點end為4

注：上圖的節(jié)點距離并非通過兩點間的距離公式算出來的，所以我們不能通過線段長度來區(qū)分距離的大小。

求：起點到終點的最短路徑

解：

1.對起點做標(biāo)記，將起點添加到標(biāo)記點集合mark中。

起點的路徑距離默認(rèn)為0，路徑距離就是節(jié)點到起點的路徑距離，所以起點到起點的默認(rèn)距離為0。

起點的前面點默認(rèn)為undefined，因為起點就是最源頭的點，沒有前面點。

2.讓未標(biāo)記點集合unmark等于map中除start之外的所有點。

3.遍歷當(dāng)前標(biāo)記點(第一個標(biāo)記點就是起點)的鄰點。

若鄰點在標(biāo)記點集合mark中，跳過此點；

否則，若當(dāng)前鄰點過當(dāng)前標(biāo)記點的路徑距離小于當(dāng)前節(jié)點的已記錄過的路徑距離，則：

• 更新當(dāng)前鄰點的路徑距離為當(dāng)前鄰點過當(dāng)前標(biāo)記點的路徑距離。

• 更新當(dāng)前鄰點的前面點為當(dāng)前標(biāo)記點。

4.遍歷未標(biāo)記點集合unmark，從中找出路徑最短的點nearest。

對nearest點做標(biāo)記，將其添加到mark中，并從unmark中刪除。

5.若unmark不為空，以nearest點為標(biāo)記點，重復(fù)3,4,5步驟。

當(dāng)unmark為空的時候，所有的節(jié)點就都完成了標(biāo)記。

6.對終點進(jìn)行回溯，尋找其前面點的前面點的前面點的前面點……，直到找到其源頭的點-起點。

把上面的一堆前面點按序連在一起，就是最短路徑了。

參考鏈接：https://www.bilibili.com/video/BV1zz4y1m7Nq/?spm_id_from=333.337.search-card.all.click&;vd_source=fc98bc82ca25234b3a3030baea035443