Dijkstra算法

1. 简介

Dijkstra是一位荷兰的计算机科学家和数学家，他被认为是计算机科学领域的先驱之一。他于1930年5月11日出生于荷兰的鹿特丹，于2002年8月6日去世于荷兰的努南。Dijkstra最为人们所熟知的是他在算法问题解决和编程语言方面的贡献。

Dijkstra最重要的贡献之一就是他开发了最短路径算法，通常被称为Dijkstra算法。这个算法被用来找到图中两个节点之间的最短路径，被广泛应用于计算机网络、交通规划等领域。

Dijkstra也是结构化程序设计的倡导者，这种方法强调使用清晰、简单和模块化的代码。他开发了一种形式化的方法叫做“守卫命令”，以确保程序的正确性。

Dijkstra于1972年获得了图灵奖，这被认为是计算机科学领域的最高荣誉。他被誉为20世纪最具影响力的计算机科学家之一。

2.作用

Dijkstra算法被广泛应用于计算机科学和工程领域，主要用于寻找图中两个节点之间的最短路径。它适用于带权重的有向和无向图，可以用于计算机网络路由、交通规划、物流路径规划等领域。

Dijkstra算法从起点开始，逐步寻找到每个节点的最短路径，并标记已经计算出最短路径的节点，最终找到终点的最短路径。它采用贪心策略，每次选择当前距离起点最近的节点作为下一个节点，并更新从起点到其他节点的距离和路径。

Dijkstra算法的优点在于它能够找到最短路径，并且对于权重非负的图，它能够保证结果的正确性。它的时间复杂度为O(N^2)，其中N是图中节点的数量，但是可以使用优先队列等数据结构来提高算法的效率，使其时间复杂度降至O(E log N)，其中E是图中边的数量。因此，在实际应用中，Dijkstra算法是一种高效的解决最短路径问题的算法。

3.实现过程

Dijkstra算法的实现过程可以概括为以下几个步骤：

1.初始化：将起点的距离设为0，其他节点的距离设为无穷大。

2.选择节点：从未标记过的节点中选择距离起点最近的节点作为当前节点。

3.标记节点：标记当前节点为已经计算出最短路径的节点。

4.更新距离：遍历当前节点的邻居节点，对于邻居节点，更新从起点到邻居节点的距离，并记录路径。

5.重复步骤2-4，直到终点被标记为已经计算出最短路径的节点。

6.返回路径：根据记录的路径信息，可以得到从起点到终点的最短路径。

具体来说，可以使用一个优先队列来维护所有未被标记的节点，并以距离起点的距离作为优先级，每次选择优先级最高的节点作为当前节点。在遍历当前节点的邻居节点时，可以计算从起点到邻居节点的距离，并更新距离和路径信息。如果发现新的路径比之前记录的路径更短，则更新路径信息。

在算法执行过程中，可以使用一个数组来记录每个节点的距离和路径信息，以及一个数组来记录每个节点是否被标记为已经计算出最短路径的节点。

需要注意的是，在使用Dijkstra算法时，需要保证图中的权重非负，否则算法可能会出现错误结果。此外，对于大规模图的计算，可以使用优化技巧，如分布式计算、多线程计算等，来提高算法的效率。

4.Dijkstra 算法的基础知识

Dijkstra 算法从指定的节点（源节点）出发，寻找它与图中所有其它节点之间的最短路径。 Dijkstra
算法会记录当前已知的最短路径，并在寻找到更短的路径时更新。
一旦找到源节点与其他节点之间的最短路径，那个节点会被标记为“已访问”并添加到路径中。
重复寻找过程，直到图中所有节点都已经添加到路径中。这样，就可以得到从源节点出发访问所有其他节点的最短路径方案。

必要条件
Dijkstra只能用在权重为正的图中，因为计算过程中需要将边的权重相加来寻找最短路径。

如果图中有负权重的边，这个算法就无法正常工作。一旦一个节点被标记为“已访问”，当前访问它的路径就被标记为访问它的最短路径。如果存在负权重，则可能在之后的计算中得到总权重更小的路径，从而影响之前的结果（译注：即可能出现多绕路反而路线更短的情况，不合实际）。

5.Dijkstra 算法示例

理解了算法概念之后，通过逐步的示例来了解一下它背后的工作原理。
假设有下面这个图：

Dijkstra 算法将会寻找出图中节点 0 到所有其他节点的最短路径。
💡 提示： 在这个图中，我们假定两个节点之间的权重表示它们之间的距离。

我们将会得到节点 0 到节点 1、节点 0 到节点 2、节点 0 到节点 3……（以此类推）的最短路径。

初始的距离列表如下：

源节点到它自身的距离为 0。示例中的源节点定为节点 0，不过你也可以选择任意其它节点作为源节点。
源节点到其它节点的距离还没有确定，所以先标记为无穷大。

还有一个列表用来记录哪些节点未被访问（即尚未被包含在路径中）：

💡 提示： 记住，当所有节点都被添加到路径中时，算法的计算过程就完成了。

我们选择了从节点 0 出发，可以直接将它标记为“已访问”，同样的，在未访问节点列表中把它划掉，并在图中给它加上红色的边框：

现在需要检查节点 0 到相邻节点的距离，两个相邻节点分别是节点 1 和节点 2（注意看红色的边）：

💡 提示：这并不是说立即把这两个相邻节点加入到最短路径中。在把一个节点加入到最短路径之前，需要确认是否已经寻找到了访问它的最短路径。现在只是在对可选方案做初步检查。
更新节点 0 到节点 1、节点 0 到节点 2 的距离为它们之间的边的权重，分别为 2 和 6：

更新了到相邻节点的距离之后：

根据已知的距离列表选择距离源节点最近的节点。
将它标记为“已访问”。
将它添加到路径中。

查看距离列表，发现节点 1到源节点的距离是最短的（距离为 2），所以把它加入到路径中。

在图中，以红色边来表示：

在距离列表中用红色方块标记这个节点，表明它是“已访问”的、已经寻找到了访问这个节点的最短路径：

在未访问节点列表中将它划掉：

现在分析新的相邻节点，寻找访问它们的最短路径。只需要分析已经在最短路径（标记为红色边）中的节点的相邻节点。

节点 2 和节点 3 都是最短路径包含的节点的相邻节点，因为它们分别与节点 0 和节点 1 直接相连，如下图所示。下一步将要分析这两个节点。

之前已经计算过源节点到节点 2 的距离，并记录在了列表中，所以不用更新。这次只需要更新源节点到新的相邻节点（节点 3）的距离：

这个距离是 7，来看看为什么。

为了计算源节点到另一个节点（这里指节点 3）的距离，需要把访问该节点的最短路径的所有边权重相加：

对于节点 3：将构成路径 0 -> 1 -> 3 的所有边权重相加，得到总距离为 7（0 -> 1 距离为 2，1 -> 3 距离为 5）。

现在得到了到相邻节点的距离，需要选择一个节点添加到路径中。我们必须选择一个已知到源节点距离最短的未访问节点。

从距离列表中可以看出，距离为 6 的节点 2 就是我们的选择：

在图中为它加上红色边框，并将路径上的边标记为红色：

在距离列表中用红色方块把它标记为“已访问”，在“未访问”节点列表中把它划掉：

重复前面的步骤，寻找源节点到新的相邻节点节点 3 的最短路径。

可以看到，有两种可选的路径：0 -> 1 -> 3 或 0 -> 2 -> 3。一起看看我们是如何确定最短路径的。

节点 3 在之前已经有了一个距离记录（距离为 7，参阅下表），这个距离是之前步骤中由路径 0 -> 1 -> 3 的两个边权重（分别为 5 和 2）相加得到的。

不过现在有了一个新的可选路径：0 -> 2 -> 3，它途经权重分别为 6 和 8 的两条边 0 -> 2 和 2 -> 3，总距离为 14。

显然，第一个路径的距离更短（7 vs. 14），所以选择第一个路径 0 -> 1 -> 3。只有在新的路径距离更短的情况下，才会更新距离列表。

因此，使用第一种方案 0 -> 1 -> 3，将节点添加到路径中。

把这个节点标记为“已访问”，在“未访问”节点列表中把它划掉：

重复前面的过程。

检查尚未访问的相邻节点：节点 4 和节点 5，因为它们是节点 3 的相邻节点。

更新它们到源节点的距离，尝试寻找更短的路径：

对于节点 4：路径是 0 -> 1 -> 3 -> 4，距离为 17。
对于节点 5：路径是 0 -> 1 -> 3 -> 5，距离为22。

💡 提示： 注意我们只能从最短路径（红色边）上进行扩展，而不能途经未被包含在最短路径中的边（例如，不能构造经过边 2 -> 3 的路径）。

现在需要选择将哪个未访问节点标记为“已访问”，这里选择节点 4，因为在距离列表中它的距离最短。在图中做标记：

在距离列表中用红色方块将它标记为“已访问”：

在“未访问”节点列表中把它划掉：

再次重复前面的过程。检查相邻节点：节点 5 和节点 6。分析每一种从已访问节点到它们之间的可能路径方案。

对于节点 5：