Dijkstra算法概述
1. 简介
很多时候，在编写软件时，我们需要能够找到图中两点之间的最佳路径。这在电脑游戏中非常常用，但也用于谷歌地图等地图软件，也可以在许多其他类型的软件中找到用途。
Dijkstra算法是一种非常流行的路径查找算法，用于查找同一图中两点之间的最短路径。
2. 什么是寻路？
路径查找是一种用于图遍历的算法，其中我们有一个开始和结束节点，需要确定两者之间的最佳路由。这既涉及路线上的步数，也涉及每个步骤的成本。
这个成本取决于我们正在处理的图表类型——真实世界的地图可能以米为单位，而像《文明》这样的电脑游戏可能会基于移动的单位类型和它正在移动的地形类型。
甚至还有遍历状态机的路径查找应用，其中图中的每个节点对应于一个状态，每个边对应于一个转换。然后，这可用于查找两个状态之间最有效的转换集，例如在求解魔方时。
3. Dijkstra 算法
Dijkstra 算法是一种路径查找算法，它通过图生成每条路线，然后选择总体成本最低的路线。
这通过迭代计算图形中每个节点的距离来工作，从开始节点开始，一直持续到我们到达结束节点。在每次迭代中，我们都有一个“当前节点”，并且我们为可以从中达到的每个节点计算一个新的最佳分数。
3.1. 流程图
3.2. 伪代码
现在我们知道算法将如何工作，它是什么样子的？让我们更详细地探讨一些描述算法的伪代码。
该算法的核心是一个迭代过程，每次都查看当前的最佳节点，直到我们达到目标。
作为其中的一部分，我们需要能够找到当前的最佳节点。这是到目前为止我们计算的分数最低的节点，我们还没有访问过。
接下来，我们需要计算节点的新分数。这是我们来自的节点的当前分数，添加到从它到达新节点的边缘成本中。
最后，一旦我们达到目标，我们就需要实际建立我们的路线。这是我们必须从头到尾遍历的节点列表。通过在每个节点上记录最好的前一个节点，我们有效地构建了这个列表，所以我们只需要把它放在一起。
发布评论