本系列为笔者初学c/c++和游戏AI开发的学习过程，算法为主，不涉及到具体的游戏开发软件学习(如unity，虚幻4等),若有错误请在评论区留下批评意见。     

• 语言：c/c++ (11及以上)

• 平台：macOS mojave

• 编辑器/编译器：vs Code / g++

图与路径查找

五、Dijkstra算法

5.1 介绍

  迪杰斯特拉算法（音译）是荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。

  该算法使用盲目搜索方法和贪心思想来解决赋权图的单源最短路径问题。

  简单来讲可以概括为，从A点到B点，每次从当前点周围未访问过的节点中选取路径最短的那个点，加入路径。

  可以将其视作是BFS算法的一个改良，在盲目搜索的基础上，增加了一个距离计算来减少搜索的计算量。

  笔者这里就不多啰嗦的介绍该算法的证明过程，感兴趣的读者可以直接阅读论文或者到维基百科上去查阅。

http://www-m3.ma.tum.de/foswiki/pub/MN0506/WebHome/dijkstra.pdf        论文地址

5.2 算法描述

  初始时，原点s的路径权重被赋为 0 （d[s]=0, 即原点的实际最短路径=0)。同时把所有其他顶点的路径长度设为无穷大，即表示我们不知道任何通向这些顶点的路径 。

  算法维护两个顶点集合S和Q，集合S保留所有已知实际最短路径值的顶点（已访问过），而集合Q则保留其他所有未访问过的顶点。

  集合S初始状态为空，之后每一步，从Q中选取一个顶点u放入S，该顶点u是d[u]最小的点（从起始点s到顶点u的最短距离）；然后，对u的每条外接边w(u, v)进行松弛操作(即u的邻接顶点v，w是u到v的距离)。

  松弛操作：如果存在一条从u到v的边，且 d[u] + w(u, v) < d[v]，则令 d[v] = d[u] + w(u, v)。

  当算法结束时，d[v] 中存储的是从s到v的最短路径，如果路径不存在的话是无穷大。

5.3 伪代码

5.3 Dijkstra算法 与 A*算法

  如果读者有心的话，可以发现，A*算法其实也是Dijkstra算法的进一步改良。

  A*算法在判断前向最短距离的同时，也判断到目标节点的最短距离，同时计算两个方向的最短路径，这样可以排除掉大量不符合条件的节点。

  在启发函数 F = G + H中，如果令H=0，即只求G值，那A*算法将转化为单源最短路径问题，即Dijkstra算法。

  我们用实验来观察这个现象：

  从上图可以很明显的看出，同样的从A点到B点，A*算法的搜索路径要小的非常多（绿色部分），并且也能找到一条短路径。

  在图上，水平或垂直移动一格距离为10，斜角距离为14，所以：

A*Path = 14 + 10 + 10 + 14 = 48

DijkstraPath = 10 + 10 +14 +14 = 48

  可见，虽然最终的查找路径不同，但均是一个最短路径解，且前者的计算量要远少得多。

5.4 Dijkstra算法代码实现

  代码实现其实只要在BFS的基础上加入松弛操作就可以。

  但有个地方需要特别注意，由于笔者使用智能指针来保存查找路径，且在getSurroundPoints方法中每次都是返回新建的指针，因此若一个节点存在需要多次更新d[v]的情况，则会发生数组中存在多个该节点的指针版本的情况。

  这种情况下，虽然还是能的到准确的最短路径长度，但当我们需要返回这个节点指针来渲染到地图上的时候，这些节点还是会指向旧指针，而不会更新。

  所以我们需要额外判断该节点是否已经有旧指针存在，若有的话直接在这个旧指针上进行更新。

 参考 

• 维基百科

• 相关代码下载    https://github.com/linpeijie/GameToy