Dijsktra 算法： C++, Python 代码示例
陈莎拉
最短路径或最短距离是多少？
从源点到目标点，成本最低的路径是最短路径或最短距离。在图论中，从源点到目标点可能有多条路线。在这些路线中，如果有一条路线成本最低，我们可以称之为最短路径算法。
这里的“Cost”是指路径中的节点数或每条路径上成本的总和。一条路径可以有一条或多条边。两个顶点之间的连接称为“边”。最短路径算法有很多种，例如 Dijkstra 算法、Bellman-Ford 算法等。
在这里，我们讨论 Dijkstra 算法
我们来看看下面的加权图：
- “加权”一词表示将成本从一个节点移动到另一个节点。例如，从节点 1 移动到节点 2，成本或权重为 1。
- 节点 1 到节点 2 之间的路径称为边。
- “无向”意味着你可以将一个节点移动到另一个节点，然后再返回到上一个节点。因此，如果我们尝试找到从节点 1 到节点 7 的所有路由，那么它将是：
| 路线或路径 | 费用 |
|---|---|
| 1-2-6-7 | （1+3+3）=7 |
| 1-2-3-7 | （1+9+1）=11 |
| 1-3-7 | （7 + 1）= 8 |
| 1-4-5-7 | （6+2+5）=13 |
在这四条路线中，我们可以看到第一条路线将花费我们 7。因此，从成本角度来看它是最短路径。
Dijkstra 算法的工作原理
Dijkstra 算法可以在有向和无向加权图中找到最短距离。该算法是贪婪的，因为它总是选择距离原点最短或最近的节点。术语“贪婪”意味着在一组结果中，算法将选择其中最好的一个。
在这里，我们试图在所有其他路线中找到最短路径。因此，Dijkstra 算法会找到从单个目标节点出发的所有最短路径。因此，它的行为就像 贪心算法.
在下面的“示例”部分中，您将看到分步方法。其工作原理如下：
步骤1） 将起始节点初始化为 0 成本，将节点的其余部分初始化为无限成本。
步骤2） 维护一个数组或列表来跟踪访问过的节点
步骤3） 用最小成本更新节点成本。可以通过将当前成本与路径成本进行比较来完成。（示例部分显示了演示）
步骤4） 继续步骤3，直到所有节点都被访问。
完成所有这些步骤后，我们将找到从源到目的地成本最低的路径。
Dijkstra 与 BFS、DFS 之间的区别
Dijkstra 和 BFS-DFS 的主要区别在于 Dijkstra 是最短路径搜索算法，而 BFS、DFS 是路径搜索算法。一般情况下，BFS 和 DFS 在寻找路径时不考虑代价。所以，这些算法不能保证最短路径。
二维网格演示 BFS 的工作原理
此演示表明 BFS 仅查找路径。但是，它并不关心路径的权重。BFS (广度优先搜索) 假设从一个节点到另一个节点的旅行仅花费 1。
我们来看一个示例图：
在这里，它在第 2 层找到一条路径。BFS 按层顺序遍历图。因此，它的行进方式如下：
步骤1） 从节点“1”开始，访问所有相邻节点2,3,4
步骤2） 将节点 2,3,4 标记为级别 1，并访问其相邻节点。它将继续探索所有相邻节点，直到到达目标节点。
从DFS的角度来说，它将遍历从1到7的路径，如下所示：
- 1→2→3→7（原始成本10，DFS成本3）
- 1→2→6→7（原始成本7，DFS成本3）
- 1→3→7 (原始成本8，DFS成本2)
- 1→4→5→7（原始成本13，DFS成本3）
如我们所见，DFS 使用深度或边的数量来计算其路径成本。
DFS 执行以下操作：
- DFS 可以找到从源（起始顶点）到目的地的路径。
- 它不能保证从源节点到目的地发现的路径是否是最短路径。
然而，就 Dijkstra 算法而言，它将根据成本来选择边。作为贪婪算法，它将选择最佳或最低成本的路径。
Dijkstra 算法的示例
Dijkstra 算法使用成本或权重来计算路径的总成本。
Dijkstra 算法的目标是最小化这个总成本或权重。在上面的例子中，我们找到从节点 1 到节点 7 的最佳路径，然后计算所有成本。
在 Dijkstra 算法中，它会通过计算权重来找到最短路径。它不会搜索所有可能的路径。让我们用一个例子来演示 Dijkstra 算法。例如，你被要求找到从节点 1 到 7 的最短路径。
对于此过程，步骤如下：
步骤1） 将起始节点成本初始化为 0。
其余节点，分配 “无所不知”。 这意味着起始顶点（源）和节点之间不存在路径，或者该路径尚未被访问。
步骤2） 当你选择节点 1 时，它将被标记为已访问。然后更新节点 1 的所有相邻邻居。2,3,4、1、XNUMX 是节点 XNUMX 的邻居节点。
在更新成本时，我们需要遵循以下步骤：
我们可以使用上述公式更新每个节点的成本。例如，我们在节点 1，我们需要更新其相邻节点 2,3,4、XNUMX、XNUMX 的成本。
更新后，成本或重量将如下所示：
步骤3）对于节点“2”， 邻居是 6 和 3。我们通过比较无穷大（当前值）来更新“6”处的成本。节点 2 的成本 + 从 2 到 6 的路径成本。简单地说，节点“6”的成本将是 1+3 或 4。
节点 3 是节点 2 的邻居。但是，我们在上一步中计算了它的成本，即 7。现在，如果我们的路径是 1-2-3，则节点 3 的成本将为 10。路径 1-2-3 将花费 10，而 1 到 3 将花费 7。
步骤4）对于节点3， 邻居节点为 7。因此，将节点 7 的当前值与路径成本 (7+1) 或 8 进行比较，我们将更新节点 7 的成本。即 8。
因此，我们找到一条从节点 1 到节点 7 的路径，即 1→3→7。成本为 8。
步骤5）对于节点4， 我们将相应地更新其相邻节点成本。因此，节点“5”的成本将更新为 8。在步骤 4,5 之后，它将如下所示：
现在，路径 1-3-7 的成本为 8（之前）。节点“7”未标记为已访问，因为我们可以从节点“7”到达节点“6”。路径“1-2-6”的成本为 4。因此路径 1-2-6-7 的成本为 7。
因为 7 < 8，所以从源顶点“1”到目标顶点“7”的最短路径将是 1-2-6-7，成本为 7。之前是 1-3-7，成本为 8。
因此，最终的图表将如下所示：
用黑线标记的边是我们从 1 到 7 的最短路径，它将花费我们 7。
伪代码 Dijkstra 算法
这是 Dijkstra 算法的伪代码
Dijkstra(G, S):
for each vertex V in G
distance[V] & lt; - Infinity
previous[V] & lt; - NULL
if V does not equal S, then,
(priority queue) Q.push(V)
distance[S] = 0
While Q is not empty
U & lt; - Extract the MIN from Q
For each unvisited adjacent V of U
TotalDistance & lt; - distance[U] + edge_cost(U, V)
if TotalDistance is less than distance[V], then
distance[V] & lt; - TotalDistance
previous[V] & lt; - u
return distance, previous
C++ 实现 Dijkstra 算法
使用以下方法实现 Dijkstra 算法 C++，代码如下：
#include <bits/stdc++.h>
using namespace std;
#define size 7
int minimumDistance(int distance[], bool visited[]) {
int min = INT_MAX;
int min_index = INT_MAX;
for (int i = 0; i < size; i++) {
if (!visited[i] & amp; & distance[i] <= min) {
min = distance[i];
min_index = i;
}
}
return min_index;
}
void printParentPath(int parent[], int i) {
if (parent[i] == -1) {
return;
}
printParentPath(parent, parent[i]);
cout << i + 1 << " ";
}
void dijkstra(int graph[size][size], int source) {
int distance[size];
bool visited[size];
int parent[size];
for (int i = 0; i < size; i++) {
parent[0] = -1;
distance[i] = INT_MAX;
visited[i] = false;
}
distance[source] = 0;
for (int i = 0; i < size - 1; i++) {
int U = minimumDistance(distance, visited);
visited[U] = true;
for (int j = 0; j < size; j++) {
int curr_distance = distance[U] + graph[U][j];
if (!visited[j] & amp; & graph[U][j] & amp; &
curr_distance < distance[j]) {
parent[j] = U;
distance[j] = curr_distance;
}
}
}
cout << "Vertex\t\tDistance\tPath" << endl;
for (int i = 1; i < size; i++) {
cout << source + 1 << "->" << i + 1 << "\t\t" << distance[i] << "\t\t"
<< source + 1 << " ";
printParentPath(parent, i);
cout << endl;
}
}
int main() {
int graph[size][size] = {{0, 1, 7, 6, 0, 0, 0}, {1, 0, 9, 0, 0, 3, 0},
{7, 9, 0, 0, 0, 0, 1}, {6, 0, 0, 0, 2, 0, 0},
{0, 0, 0, 2, 0, 0, 0}, {0, 3, 0, 0, 0, 0, 3},
{0, 0, 0, 0, 5, 3, 0}};
dijkstra(graph, 0);
}
输出：
Vertex Distance Path 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
Python 实现 Dijkstra 算法
使用以下方法实现 Dijkstra 算法 蟒蛇，代码如下：
num_of_vertex = 7
def minimumDistance(distance, visited):
_min = 1e11
min_index = 1e11
for i in range(num_of_vertex):
if not visited[i] and distance[i] & lt; = _min:
_min = distance[i]
min_index = i
return min_index
def printParentNode(parent, i):
if parent[i] == -1:
return
printParentNode(parent, parent[i])
print("{} ".format(i + 1), end = "")
def dijkstra(graph, src):
distance = list()
visited = list()
parent = list()
for i in range(num_of_vertex):
parent.append(-1)
distance.append(1e11)
visited.append(False)
distance[src] = 0
for i in range(num_of_vertex - 1):
U = minimumDistance(distance, visited)
visited[U] = True
for j in range(num_of_vertex):
curr_distance = distance[U] + graph[U][j]
if not visited[j] and graph[U][j] and curr_distance & lt;
distance[j]: parent[j] = U
distance[j] = curr_distance
print("Vertex\t\tDistance\tPath")
for i in range(num_of_vertex):
print("{}->{}\t\t{}\t\t{}
".format(src + 1, i + 1, distance[i], src + 1), end = "")
printParentNode(parent, i)
print("")
graph = [
[0, 1, 7, 6, 0, 0, 0],
[1, 0, 9, 0, 0, 3, 0],
[7, 9, 0, 0, 0, 0, 1],
[6, 0, 0, 0, 2, 0, 0],
[0, 0, 0, 2, 0, 0, 0],
[0, 3, 0, 0, 0, 0, 3],
[0, 0, 0, 0, 5, 3, 0]
]
dijkstra(graph, 0)
输出：
Vertex Distance Path 1->1 0 1 1->2 1 1 2 1->3 7 1 3 1->4 6 1 4 1->5 8 1 4 5 1->6 4 1 2 6 1->7 7 1 2 6 7
我们可以看到该算法计算了距离源节点的最短距离。
Dijkstra 算法的应用
Dijkstra 算法用途广泛。其中，它在网络领域应用广泛。以下是 Dijkstra 算法的一些实际用途：
Dijkstra 在 Google 地图上的表现： 基本上，这个算法是寻找最短路径的支柱。正如我们从上面的代码片段输出中看到的那样。
Google 不使用简单的 Dijkstra 算法。相反，它使用了一个修改版本。当你选择一个目的地时，它会在 Google 地图上显示多条路径。在这些路径中，一些路径是为用户整理出来的。这些路径的选择是基于“时间”的。所以，“时间”是最短路径的边成本。
IP路由中的Dijkstra： IP路由 是一个网络术语。它表示您的数据包如何通过不同的路径发送到接收方。这些路径包括路由器、服务器等。在 IP 路由中，有不同类型的协议。
这些协议帮助路由器找到发送数据的最短路径。其中一个协议名称是“OSPF（开放最短路径优先）”。OSPF 使用 Dijkstra 算法。路由器维护一个路由表。每个路由器都与邻居路由器共享其路由表。收到更新后的路由表后，它们必须重新计算所有路径。那时，路由器使用 Dijkstra 算法。
Dijkstra 算法的局限性
Dijkstra 算法不能保证负边图中的最短路径。Dijkstra 算法遵循以下方法：
- 从一个节点到另一个节点将采用一条最短路径。
- 两个节点之间的最短路径一旦选定，就不会再次计算。
这里，请注意两个具有负边缘的例子。
在左图中， 有三个顶点。Dijkstra 将在 Graph 上运行，如下所示：
步骤1） 起始顶点“1”将被初始化为零。其他节点将为无穷大。
步骤2） 将节点“1”标记为已访问并将其包含在最短路径中。
步骤3） 由于最短路径尚未计算，因此源节点 1 到节点“2”和“3”的距离设置为无穷大。因此，任何成本小于无穷大的路径都将添加到最短路径（贪婪方法）。
步骤4） 将源顶点或源节点的距离从“1”更新为“2”。当前权重将为 5（5
步骤5） 现在，如果我们检查从节点“1”开始的最短距离，我们会发现 5 是边 1–> 2 的最短距离。因此，节点“2”将被标记为已访问。
类似地，节点“3”也将被标记为已访问，因为最短距离是 3。
然而，如果我们观察，就会发现有一条路径 1-3-2 的成本仅为 2。但 Dijkstra 表明从节点“1”到节点“2”，最短距离为 5。因此，Dijkstra 无法正确计算最短距离。发生这种情况的原因是，Dijkstra 是一种贪婪算法。因此，一旦将节点标记为已访问，就不会再考虑它，尽管可能有更短的路径可用。只有当边具有负成本或负权重边时，才会出现此问题
在这种情况下，Dijkstra 无法计算两个节点之间的最短路径。因此，该算法存在一些缺点。为了解决这个负边问题，使用了另一种称为“Bellman-Ford 算法”的算法。该算法可以处理负边。
Dijkstra 算法的复杂性
上面的实现使用了两个“for”循环。这些循环针对顶点数运行。因此，时间复杂度为 （V2)。这里的“0”是指对Dijkstra算法给出假设的符号。
我们可以使用“优先级队列”来存储图形。优先级队列是一种二进制堆数据结构。它比二维矩阵更高效。成本最低的边将具有较高的优先级。
那么时间复杂度将是 O(E log(V))。其中，E为边数，V为顶点数。
空间复杂度为 （V2)，因为我们使用邻接矩阵（二维阵列）。可以使用邻接表或队列数据结构来优化空间复杂度。
