dikjstra寻路算法

至今，我偶尔会遇到一些寻路的寻求，虽然是偶尔，但时间久了，也就多了。

我对寻路是没有太多研究的，所以就去B站搜了一下，搜到一个很棒的dikjstra教程。

我照着这个教程，用ts写了一下这个逻辑，分享给大家。

整体代码如下：

最终，console.log(optimal) 输出的结果就是：[4, 5, 6, 7, 0]

这与dikjstra教程里的结果是一致的。

根据这个教程内容，做个笔记。

已知：

• 节点关系map，即每个节点的邻点

• 节点距离segmentLengthMap，存在联系的两个节点间的距离

• 起点start为0

• 终点end为4

注：上图的节点距离并非通过两点间的距离公式算出来的，所以我们不能通过线段长度来区分距离的大小。

求：起点到终点的最短路径

解：

1.对起点做标记，将起点添加到标记点集合mark中。

起点的路径距离默认为0，路径距离就是节点到起点的路径距离，所以起点到起点的默认距离为0。

起点的前面点默认为undefined，因为起点就是最源头的点，没有前面点。

2.让未标记点集合unmark等于map中除start之外的所有点。

3.遍历当前标记点(第一个标记点就是起点)的邻点。

若邻点在标记点集合mark中，跳过此点；

否则，若当前邻点过当前标记点的路径距离小于当前节点的已记录过的路径距离，则：

• 更新当前邻点的路径距离为当前邻点过当前标记点的路径距离。

• 更新当前邻点的前面点为当前标记点。

4.遍历未标记点集合unmark，从中找出路径最短的点nearest。

对nearest点做标记，将其添加到mark中，并从unmark中删除。

5.若unmark不为空，以nearest点为标记点，重复3,4,5步骤。

当unmark为空的时候，所有的节点就都完成了标记。

6.对终点进行回溯，寻找其前面点的前面点的前面点的前面点……，直到找到其源头的点-起点。

把上面的一堆前面点按序连在一起，就是最短路径了。

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