最短路径问题（1）——Dijkstra算法
说到游戏编程，寻路算法是许多RPG游戏无法避免的一个关键点，所以这一系列的文章就从本科最熟悉的Dijkstra算法开始讲起一步步到游戏中常用的A*算法。做一个简单的算法演示。
一、算法简介
Dijkstra算法是用来解决单源最短路径的算法，即在一个图中找出一个点N，找出以该点为起点到其他所有点的最短路径。但是如果想找到两个顶点A和C之间的最短路径时，Dijkstra算法可能同时找到到达其它顶点（例如顶点B）的最短路径，这一点将在算法演示的时候详细解释。同时Dijkstra算法无法适用于含有负权重的图。
算法的步骤如下：
1、维护一个数组N，两个集合P,Q，数组N用来储存起点到各个顶点的最短距离，集合P用来存储未遍历的点，集合Q存储已遍历的点。
2、选择起点，将起点添加到Q集合中，并从P集合中删除。将与起点相邻的点的距离添加到数组中，到不相邻点的距离用无穷大表示。
3、选择距离Q集合最近的一个点M（即与所有已遍历点相连的未遍历点中，边的权值最小的点）。将该点加入Q集合,并从P集合中删除。
4、找到与M相邻的点C，计算数组N中存储的到达C点的距离是否小于起点经过M到达C点的距离，若是，则更新N，否则继续寻找下一个与M相邻的点，重复步骤4直到遍历完M的所有邻点。
5、重复步骤3，4直至遍历集合P为空。
文字版看不明白没关系，接下来将有图示，可以直接看图示。
二、算法演示
下面将以点A使用Dijkstra算法：
| 假设以A为起点寻找最短路径，则维护一个数组N[5]={∞，∞，∞，∞，∞}，存储A到点A,B,C,D,E的距离，同时维护集合P={A,B,C,D,E},集合Q={} |
| 首先将点A加入集合Q，并从集合P中删除，更新数组N。因为与A相邻的点为B,C,D，所以此次循环更新到B,C,D的最短距离。 |
| 找到距离集合Q最近的点C，将其加入集合Q，并从集合P中删除，遍历与C相邻的点。由数组N我们可知A->C=3，所以A->C + C->B = 5，小于原数组中A->B的距离10，所以更新N。同样的A->C+C->E=18，小于无穷大，所以更新数组N。 |
| 找到距离集合Q最近的点B，将其加入集合Q中，并从P中删除，遍历与B相邻的点。由数组N可知A->B=5，B->D=5，所以A->B+B->D = 10,小于原本A->D的距离20，所以更新数组N。 |
| 找到距离集合Q最近的D，并将其加入集合Q中，并从P中删除，遍历与D相邻的点。我们发现A->D+D->E=21,大于原本A->E的距离18，所以不做处理。 |
| 找到距离集合Q最近的E，将其加入集合Q中，并从P中删除，遍历与E相邻的点。我们发现不存在与E相邻并可以到达的点，所以不做处理。至此最短路径便全部获得。 |
总结：我们可以发现，Dijkstra算法发现最短路径的方式并不是目的明确的，在上述例子中，我们发现最短路径的发现顺序依次是C,B,E,D 。所以当我们需要寻找点D的最短路径时会先找到起点到其他所有点的最短路径。与之相对应的A*算法寻找目标点则十分明确，关于A*我们将在往后的文章中提到。
三、局限性
Dijkstra算法是无法用于负权重的图的，这里只需要对上述例子修改一下，然后使用Dijkstra算法自行推算一遍就可以明白，当做一个简单的思考，下一篇讲Bellman-Ford算法的时候我会详细解释该图。
四、在游戏开发中的运用
很明显Dijkstra算法是不可能用于类似dota或者网页上常见的是兄弟就来砍我这些游戏的寻路，因为在找到对应目标前需要遍历其他不必要的点实在太多，这是一种浪费效率的做法，大多数这类游戏采用的都是A*算法。
Dijkstra算法适用的场景是类似于文明6这种战棋游戏（当然我也只是说适用，天知道文明6用的是哪种算法）。因为战棋游戏每一个棋子移动到某个网格的消耗都必须在玩家选中该棋子时实时呈现给玩家，所以遍历棋子周围的网格是一种很有必要的做法，因为电脑并不清楚玩家到底会选择向哪个方向移动。如下图，我们显然可以发现一个棋子移动前，所有可到达地点都已经被标记好了，很明显这是一种遍历后才能出现的结果。
两者的区别就这样体现出来了：前者的移动是先输入具体位置，然后由计算机计算该怎么移动。而后者是先告诉玩家可移动范围，再由玩家输入具体要去的位置。