Dijkstra 算法

以下教程将教我们 Dijkstra 最短路径算法。我们将通过逐步的图形化解释来理解 Dijkstra 算法的工作原理。

我们将涵盖以下内容：

• 图基本概念的简要概述
• 理解 Dijkstra 算法的用途
• 通过逐步示例理解算法的工作原理

那么，让我们开始吧。

图的简要介绍

图是非线性数据结构，表示元素之间的“连接”。这些元素称为顶点，连接图中任意两个顶点的线或弧称为边。更正式地讲，图由一组顶点 (V) 和一组边 (E) 组成。图表示为 G(V, E)。

图的组成部分

1. 顶点：顶点是图的基本单位，用于表示现实生活中的对象、人物或实体。有时，顶点也称为节点。
2. 边：边用于连接图的两个顶点。有时，边也称为弧。

下图显示了图的图形表示

图 1：图的图形表示

在上图中，顶点/节点用彩色圆圈表示，边用连接节点的线表示。

图的应用

图用于解决许多现实生活中的问题。图用于表示网络。这些网络可能包括电话或电路网络，或城市中的路径。

例如，我们可以使用图来设计交通网络模型，其中顶点显示发送或接收产品的设施，边表示连接它们的道路或路径。以下是相同的图形表示

图 2：交通网络的图形表示

图也用于不同的社交媒体平台，如 LinkedIn、Facebook、Twitter 等。例如，Facebook 等平台使用图来存储用户数据，其中每个人都用一个顶点表示，每个人都是一个包含个人 ID、姓名、性别、地址等信息的结构。

图的类型

图可以分为两种类型

1. 无向图
2. 有向图

无向图：边没有方向的图称为无向图。该图的边表示双向关系，其中每条边都可以双向遍历。下图显示了一个简单的无向图，它有四个节点和五条边。

图 3：一个简单的无向图

有向图：边有方向的图称为有向图。该图的边表示单向关系，其中每条边只能单向遍历。下图显示了一个简单的有向图，它有四个节点和五条边。

图 4：一个简单的有向图

图中边的绝对长度、位置或方向通常没有意义。换句话说，我们可以通过重新排列顶点或扭曲边来以不同的方式可视化同一图，只要图的底层结构不变。

什么是加权图？

如果每条边都分配了一个“权重”，则称图是加权的。边的权重可以表示距离、时间或任何能模拟它连接的两个顶点之间“连接”的事物。

例如，在下面的加权图图中，我们可以观察到每条边旁边都有一个蓝色数字。这个数字用于表示相应边的权重。

图 5：加权图示例

Dijkstra 算法简介

现在我们已经了解了一些基本的图概念，让我们深入理解 Dijkstra 算法的概念。

有没有想过 Google 地图是如何找到两个地点之间最短最快路径的？

答案是 Dijkstra 算法。Dijkstra 算法是一种图算法，用于查找从源顶点到图中所有其他顶点的最短路径（单源最短路径）。它是一种贪婪算法，仅适用于具有正权重的加权图。使用图的邻接矩阵表示，Dijkstra 算法的时间复杂度为 O(V²)。使用图的邻接列表表示，时间复杂度可以降低到 O((V + E) log V)，其中 V 是顶点数，E 是图中的边数。

Dijkstra 算法的历史

Dijkstra 算法由荷兰计算机科学家、软件工程师、程序员、科学散文家和系统科学家 Edsger W. Dijkstra 博士设计并发表。

在 2001 年接受 Philip L. Frana 为《ACM 通讯》杂志采访时，Edsger W. Dijkstra 博士透露：

“从鹿特丹到格罗宁根，一般来说，从一个给定的城市到另一个给定的城市，最短的路线是什么？这就是最短路径算法，我大约花了二十分钟设计出来。一天早上，我和我年轻的未婚妻在阿姆斯特丹购物，我们累了，坐在咖啡馆露台上喝咖啡，我当时只是在想我是否能做到这一点，然后我就设计了最短路径算法。就像我说的，那是二十分钟的发明。事实上，它在 59 年，三年后出版。这篇出版物仍然可读，事实上，它相当不错。它如此不错的原因之一是我没有用铅笔和纸设计它。后来我才知道，不用铅笔和纸设计的好处之一是，你几乎被迫避免所有可避免的复杂性。最终，那个算法令我大为惊讶，成为了我声誉的基石之一。”

1956 年，Dijkstra 在阿姆斯特丹数学中心担任程序员时，为了说明一台名为 ARMAC 的新计算机的功能，他思考了最短路径问题。他的目标是选择一个问题和一个（由计算机生成的）解决方案，让没有计算机背景的人也能理解。他开发了最短路径算法，后来在 ARMAC 上执行，用于荷兰 64 个城市（64 个城市，因此 6 位足以编码城市编号）的模糊缩短的交通地图。一年后，他遇到了该研究所下一台计算机的硬件工程师提出的另一个问题：最小化连接机器背板引脚所需的电线量。作为解决方案，他重新发现了名为 Prim 的最小生成树算法，并于 1959 年发表。

Dijkstra 算法的基本原理

以下是 Dijkstra 算法的基本概念

1. Dijkstra 算法从我们选择的节点（源节点）开始，它检查图以找到该节点与图中所有其他节点之间的最短路径。
2. 算法会记录目前已知的从每个节点到源节点的最短距离，如果找到任何更短的路径，它会更新这些值。
3. 一旦算法检索到源节点和另一个节点之间的最短路径，该节点将被标记为“已访问”并包含在路径中。
4. 该过程继续进行，直到图中的所有节点都包含在路径中。通过这种方式，我们有一条连接源节点到所有其他节点的路径，遵循最短的可能路径到达每个节点。

理解 Dijkstra 算法的工作原理

Dijkstra 算法需要图和源顶点。该算法建立在贪婪方法之上，因此在算法的每个步骤中都会找到局部最优选择（本例中的局部最小值）。

此算法中的每个顶点都将具有两个属性：

1. 访问属性
2. 路径属性

让我们简要了解这些属性。

访问属性

1. “visited”属性表示节点是否已被访问。
2. 我们使用此属性是为了不再访问任何节点。
3. 仅当找到最短路径时才将节点标记为已访问。

路径属性

1. “path”属性存储节点当前最短路径的值。
2. 当前最短路径表示到目前为止我们到达此节点的最短方式。
3. 当节点的任何邻居被访问时，此属性会更新。
4. 此属性很重要，因为它将存储每个节点的最终答案。

最初，我们将所有顶点或节点标记为未访问，因为它们尚未被访问。除了源节点，所有节点的路径也设置为无穷大。此外，源节点的路径设置为零 (0)。

然后我们选择源节点并将其标记为已访问。之后，我们访问源节点的所有邻居节点并对每个节点执行松弛操作。松弛是借助另一个节点降低到达节点成本的过程。

在松弛过程中，每个节点的路径都会更新为该节点的当前路径、到前一个节点的路径之和以及从前一个节点到当前节点的路径中的最小值。

假设 p[n] 是节点 n 的当前路径值，p[m] 是到前一个访问节点 m 的路径值，w 是当前节点与前一个访问节点之间的边的权重（n 和 m 之间的边权重）。

在数学意义上，松弛可以表示为

p[n] = minimum(p[n], p[m] + w)

然后，我们在后续的每一步中，将路径最短的未访问节点标记为已访问，并更新其邻居的路径。

我们重复此过程，直到图中所有节点都标记为已访问。

每当我们向已访问集合添加一个节点时，它所有相邻节点的路径也会相应地改变。

如果任何节点无法到达（不连通组件），其路径将保持为“无穷大”。如果源本身是一个单独的组件，那么到所有其他节点的路径将保持为“无穷大”。

通过示例理解 Dijkstra 算法

以下是我们实现 Dijkstra 算法将遵循的步骤

步骤 1： 首先，我们将源节点标记为当前距离为 0，并将其余节点设置为无穷大。

步骤 2： 然后，我们将当前距离最小的未访问节点设置为当前节点，假设为 X。

步骤 3： 对于当前节点 X 的每个邻居 N：我们将 X 的当前距离与连接 X-N 的边的权重相加。如果它小于 N 的当前距离，则将其设置为 N 的新当前距离。

步骤 4： 然后，我们将当前节点 X 标记为已访问。

步骤 5： 如果图中还有未访问的节点，我们将从“步骤 2”重复该过程。

现在让我们借助一个示例来理解算法的实现

图 6：给定图

1. 我们将使用上面的图作为输入，节点 A 作为源节点。
2. 首先，我们将所有节点标记为未访问。
3. 我们将节点 A 的路径设置为 0，所有其他节点的路径设置为 无穷大。
4. 我们现在将源节点 A 标记为已访问并访问其相邻节点。
   注意：我们只访问了相邻节点，而不是访问了它们。
5. 我们将借助松弛更新到节点 B 的路径为 4，因为到节点 A 的路径为 0，从节点 A 到 B 的路径为 4，并且 minimum((0 + 4), INFINITY) 是 4。
6. 我们还将借助松弛更新到节点 C 的路径为 5，因为到节点 A 的路径为 0，从节点 A 到 C 的路径为 5，并且 minimum((0 + 5), INFINITY) 是 5。节点 A 的两个邻居现在都已松弛；因此，我们可以继续前进。
7. 现在我们将选择路径最短的下一个未访问节点并访问它。因此，我们将访问节点 B 并对其未访问的邻居进行松弛。执行松弛后，到节点 C 的路径将保持 5，而到节点 E 的路径将变为 11，到节点 D 的路径将变为 13。
8. 现在我们将访问节点 E 并对其相邻节点 B、D 和 F 执行松弛。由于只有节点 F 未被访问，它将被松弛。因此，到节点 B 的路径将保持不变，即 4，到节点 D 的路径也将保持 13，到节点 F 的路径将变为 14 (8 + 6)。
9. 现在我们将访问节点 D，并且只有节点 F 将被松弛。然而，到节点 F 的路径将保持不变，即 14。
10. 由于只剩下节点 F，我们将访问它，但不执行任何松弛，因为它的所有相邻节点都已被访问。
11. 一旦图中的所有节点都被访问，程序将结束。

因此，我们得出的最终路径是

Dijkstra 算法的伪代码

现在我们将理解 Dijkstra 算法的伪代码。

• 我们必须记录每个节点的路径距离。因此，我们可以将每个节点的路径距离存储在一个大小为 n 的数组中，其中 n 是节点的总数。
• 此外，我们希望检索最短路径及其长度。为了克服这个问题，我们将每个节点映射到最后更新其路径长度的节点。
• 算法完成后，我们可以回溯目标节点到源节点以检索路径。
• 我们可以使用最小优先队列以高效的方式检索路径距离最短的节点。

现在让我们实现上述插图的伪代码

伪代码

说明

在上面的伪代码中，我们定义了一个接受多个参数的函数——由节点组成的图和源节点。在此函数中，我们遍历了图中的每个节点，将其初始距离设置为 INFINITY，并将前一个节点值设置为 NULL。我们还检查了任何选定节点是否不是源节点，并将其添加到优先队列中。此外，我们将源节点的距离设置为 0。然后，我们遍历优先队列中的节点，选择距离最小的节点，并将其标记为已访问。然后，我们遍历所选节点的未访问相邻节点，并相应地执行松弛操作。最后，我们比较了源节点和目标节点之间的两个距离（原始距离和临时距离），用最小值和前一个节点信息更新了结果距离，并返回了包含其前一个节点信息的最终距离列表。

Dijkstra 算法在不同编程语言中的实现

现在我们已经成功理解了 Dijkstra 算法的伪代码，是时候看看它在 C、C++、Java 和 Python 等不同编程语言中的实现了。

C 语言中 Dijkstra 算法的代码

以下是 Dijkstra 算法在 C 编程语言中的实现

文件：DijkstraAlgorithm.c

输出

Distance from the Source Node to 1: 4
Distance from the Source Node to 2: 12
Distance from the Source Node to 3: 19
Distance from the Source Node to 4: 12
Distance from the Source Node to 5: 8
Distance from the Source Node to 6: 10

说明

在上面的代码片段中，我们包含了 stdio.h 头文件，定义了两个常量值：INF = 9999 和 MAX = 10。我们声明了函数的原型，然后将 Dijkstra 算法的函数定义为 DijkstraAlgorithm，它接受三个参数——由节点组成的图、图中节点的数量和源节点。在此函数中，我们定义了一些数据结构，例如将作为算法的优先队列的 2D 矩阵、用于维护节点之间距离的数组、用于维护前一个节点记录的数组、用于存储已访问节点信息的数组，以及一些整数变量用于存储最小距离值、计数器、下一个节点值等。然后我们使用嵌套 for 循环遍历图中的节点并相应地将它们添加到优先队列中。我们再次使用for 循环从源节点开始遍历优先队列中的元素并更新它们的距离。在循环之外，我们将源节点的距离设置为 0 并在 visited_nodes[] 数组中将其标记为已访问。然后我们将计数器值设置为 1，并使用 while 循环遍历节点数。在此循环中，我们将 minimum_distance 的值设置为 INF，并使用 for 循环用 distance[] 数组中的最小值更新 minimum_distance 变量的值。然后我们使用 for 循环遍历所选节点的未访问相邻节点并执行松弛。然后我们打印了使用 Dijkstra 算法计算的距离的结果数据。

在 main 函数中，我们定义并声明了表示图、节点数量和源节点的变量。最后，我们通过传递所需的参数调用了 DijkstraAlgorithm() 函数。

因此，为用户打印了从源节点到每个节点的所需最短路径。

C++ 中 Dijkstra 算法的代码

以下是 Dijkstra 算法在 C++ 编程语言中的实现

文件：DijkstraAlgorithm.cpp

输出

Distance from start: 4
F G D A

说明

在上面的代码片段中，我们包含了 'iostream' 和 'vector' 头文件，并定义了一个常量值 MAX_INT = 10000000。然后我们使用了标准命名空间并原型化了 DijkstraAlgorithm() 函数。然后我们定义了程序的 main 函数，并在其中调用了 DijkstraAlgorithm() 函数。之后，我们声明了一些类来创建顶点和边。我们还原型化了更多函数来查找从源顶点到目标顶点的最短路径，并实例化了 Vertex 和 Edge 类。然后我们定义了这两个类来创建图的顶点和边。然后我们定义了 DijkstraAlgorithm() 函数来创建图并执行不同的操作。在这个函数中，我们声明了一些顶点和边。然后我们设置了图的源顶点，并调用 Dijkstra() 函数来查找最短距离，并调用 Print_Shortest_Route_To() 函数来打印从源顶点到顶点 'F' 的最短距离。然后我们定义了 Dijkstra() 函数来计算从源顶点到所有顶点的最短距离。我们还定义了一些其他函数来查找距离最短的顶点，以返回剩余顶点所有相邻的顶点，以返回两个连接的顶点之间的距离，以检查所选顶点是否存在于图中，并打印从源顶点到目标顶点的最短路径。

因此，为用户打印了从源节点到顶点 'F' 的所需最短路径。

Java 中 Dijkstra 算法的代码

以下是 Dijkstra 算法在 Java 编程语言中的实现

文件：DijkstraAlgorithm.java

输出

Distance from Vertex 0 to Vertex 0 is 0
Distance from Vertex 0 to Vertex 1 is 1
Distance from Vertex 0 to Vertex 2 is 1
Distance from Vertex 0 to Vertex 3 is 2
Distance from Vertex 0 to Vertex 4 is 4
Distance from Vertex 0 to Vertex 5 is 4
Distance from Vertex 0 to Vertex 6 is 3

说明

在上面的代码片段中，我们定义了一个公共类 DijkstraAlgorithm()。在此类中，我们定义了一个公共方法 dijkstraAlgorithm() 来查找从源顶点到目标顶点的最短距离。在此方法中，我们定义了一个变量来存储节点数。然后我们定义了一个布尔数组来存储有关已访问顶点的信息，以及一个整数数组来存储它们各自的距离。最初，我们将两个数组中的值分别声明为 False 和 MAX_VALUE。我们还将源顶点的距离设置为零，并使用 for 循环更新源顶点和目标顶点之间与最小距离的距离。然后我们通过执行松弛操作更新了所选顶点的相邻顶点的距离，并打印了每个顶点的最短距离。然后我们定义了一个方法来查找从源顶点到目标顶点的最小距离。然后我们定义了主函数，在其中声明了图的顶点并实例化了 DijkstraAlgorithm() 类。最后，我们调用了 dijkstraAlgorithm() 方法来查找源顶点和目标顶点之间的最短距离。

因此，为用户打印了从源节点到每个节点的所需最短路径。

Python 中 Dijkstra 算法的代码

以下是 Dijkstra 算法在 Python 编程语言中的实现

文件：DikstraAlgorithm.py

输出

Distance of A from source node: 0
Distance of B from source node: 3
Distance of C from source node: 1
Distance of D from source node: 2
Distance of E from source node: 2
Distance of F from source node: 4
Distance of G from source node: 3

说明

在上面的代码片段中，我们导入了 sys 模块，并声明了由节点和边的值组成的列表。然后我们定义了一个函数 toBeVisited() 来查找下一个要访问的节点。然后我们找到了图中节点的总数，并设置了每个节点的初始距离。然后我们计算了从源节点到目标节点的最小距离，对相邻节点执行了松弛操作，并更新了列表中的距离。然后我们将这些距离从列表中打印给用户。

因此，为用户打印了从源节点到每个节点的所需最短路径。

Dijkstra 算法的时间和空间复杂度

• Dijkstra 算法的时间复杂度为 O(E log V)，其中 E 是边数，V 是顶点数。
• Dijkstra 算法的空间复杂度为 O(V)，其中 V 是顶点数。

Dijkstra 算法的优缺点

让我们讨论一下 Dijkstra 算法的一些优点

1. 使用 Dijkstra 算法的一个主要优点是它具有近乎线性的时间和空间复杂度。
2. 我们可以使用此算法计算从单个顶点到所有其他顶点的最短路径，以及从单个源顶点到单个目标顶点的最短路径，只需在获得目标顶点的最短距离后停止算法即可。
3. 该算法仅适用于有向加权图，且该图的所有边都应为非负。

尽管 Dijkstra 算法具有多项优点，但它也有一些缺点，例如

1. Dijkstra 算法执行隐蔽探索，在此过程中需要大量时间。
2. 该算法无法处理负边。
3. 由于该算法指向无环图，因此无法计算精确的最短路径。
4. 它还需要维护以记录已访问的顶点。

Dijkstra 算法的一些应用

Dijkstra 算法有各种实际应用，其中一些如下所述

1. Google 地图中的数字地图服务： 我们曾多次尝试在 Google 地图中查找距离，无论是从我们当前位置到最近的首选位置，还是从一个城市到另一个城市，其中包含多个连接它们的路线/路径；但是，应用程序必须显示最小距离。这只有通过 Dijkstra 算法才能实现，该算法帮助应用程序找到两个给定位置之间以及路径上的最短距离。让我们将美国视为一个图，其中城市/地点表示为顶点，两个城市/地点之间的路线表示为边。然后借助 Dijkstra 算法，我们可以计算任何两个城市/地点之间的最短路线。
2. 社交网络应用：在 Facebook、Twitter、Instagram 等许多应用中，我们中的许多人可能都观察到这些应用会推荐特定用户可能认识的朋友列表。许多社交媒体公司如何以高效有效的方式实现这种功能，特别是在系统拥有超过十亿用户的情况下？这个问题的答案是 Dijkstra 算法。标准的 Dijkstra 算法通常用于估算用户之间的最短距离，该距离是通过他们之间的连接或共同性来衡量的。当社交网络非常小的时候，它使用标准的 Dijkstra 算法以及一些其他功能来确定最短路径。但是，当图大得多时，标准算法需要几秒钟才能计数，因此，一些高级算法被用作替代方案。
3. 电话网络： 我们中的一些人可能知道，在电话网络中，每条传输线都有一个带宽“b”。带宽是传输线可以支持的最高频率。通常，如果特定线路中的信号频率较高，则该线路会衰减信号。带宽表示线路可以传输的信息量。让我们将一个城市视为一个图，其中交换站用顶点表示，传输线用边表示，带宽“b”用边的权重表示。因此，正如我们所观察到的，电话网络也可以归入最短距离问题，并且可以使用 Dijkstra 算法解决。
4. 航班程序：假设某人需要软件来为客户准备航班议程。代理可以访问包含所有航班和机场的数据库。除了航班号、出发机场和目的地之外，航班还有出发和到达时间。因此，为了确定从原始机场和给定起始时间到选定目的地的最早到达时间，代理使用 Dijkstra 算法。
5. IP 路由以查找开放最短路径优先：开放最短路径优先（缩写为 OSPF）是一种链路状态路由协议，用于借助其自身的开放最短路径优先来查找源路由器和目标路由器之间的最佳路径。Dijkstra 算法广泛用于路由器更新其转发表所需的路由协议。该算法提供了从源路由器到网络中其他路由器的最短成本路径。
6. 机器人路径：如今，无人机和机器人已经出现，有些是手动操作的，有些是自动操作的。自动操作并用于将包裹运送到给定位置或用于任何特定任务的无人机和机器人都配置了 Dijkstra 算法模块，以便在知道源和目的地时，无人机和机器人将按照指定方向移动，遵循最短路径，同时将交付包裹所需的时间降至最低。
7. 指定文件服务器：Dijkstra 算法还用于在局域网 (LAN) 中指定文件服务器。假设文件从一台计算机传输到另一台计算机需要无限长的时间。因此，为了最小化从文件服务器到网络上所有其他计算机的“跳数”，我们将使用 Dijkstra 算法。该算法将返回网络之间的最短路径，从而实现最小跳数。

结论

• 在上述教程中，我们首先理解了图的基本概念及其类型和应用。
• 然后我们学习了 Dijkstra 算法及其历史。
• 我们还通过一个例子理解了 Dijkstra 算法的基本工作原理。
• 之后，我们学习了如何借助伪代码编写 Dijkstra 算法的代码。
• 我们观察了它在 C、C++、Java 和 Python 等编程语言中的实现，并附有适当的输出和解释。
• 我们还理解了 Dijkstra 算法的时间和空间复杂度。
• 最后，我们讨论了 Dijkstra 算法的优缺点以及它的一些实际应用。