DSA Dijkstra 算法
Dijkstra 最短路径算法由荷兰计算机科学家 Edsger W. Dijkstra 在 1956 年发明，当时他与未婚妻在阿姆斯特丹购物，在 20 分钟的休息时间里发明的。
发明该算法的目的是测试一台名为 ARMAC 的新型计算机。
Dijkstra 算法
Dijkstra 算法用于查找从一个顶点到所有其他顶点的最短路径。
它通过重复选择最近的未访问顶点并计算到所有未访问相邻顶点的距离来实现这一点。
Dijkstra 算法通常被认为是解决最短路径问题的最直接的算法。
Dijkstra 算法用于解决有向或无向路径的单源最短路径问题。单源意味着选择一个顶点作为起点，算法将找到从该顶点到所有其他顶点的最短路径。
Dijkstra 算法不适用于包含负权边的图。对于包含负权边的图，可以使用下一页介绍的 Bellman-Ford 算法。
为了找到最短路径，Dijkstra 算法需要知道哪个顶点是源点，它需要一种方法来标记已访问的顶点，并且需要在遍历图时概述到每个顶点的当前最短距离，并在找到更短的距离时更新这些距离。
工作原理
- 设置所有顶点的初始距离：源顶点为 0，所有其他顶点为无穷大。
- 选择与起点距离最短的未访问顶点作为当前顶点。因此，该算法将始终从源点开始作为当前顶点。
- 对于当前顶点的每个未访问的相邻顶点，计算从源点的距离，如果新的计算距离更低，则更新距离。
- 现在我们完成了当前顶点，所以将其标记为已访问。已访问的顶点不会再次检查。
- 返回步骤 2 选择一个新的当前顶点，并不断重复这些步骤，直到所有顶点都被访问。
- 最后，我们得到了从源顶点到图中所有其他顶点的最短路径。
在上图动画中，当一个顶点被标记为已访问时，该顶点及其边会变淡，表示 Dijkstra 算法已完成对该顶点的处理，不会再访问它。
注意：这个 Dijkstra 算法的基本版本可以给出到每个顶点的最短路径成本值，但不能给出实际的路径。例如，在上图动画中，我们得到了到顶点 F 的最短路径成本值 10，但算法没有给出组成这条最短路径的顶点（D->E->C->D->F）。我们将在本页面的下方添加此功能。
Dijkstra 模拟详细说明
运行下面的模拟，以更详细地了解 Dijkstra 算法如何在特定图上运行，找到从顶点 D 到所有其他顶点的最短距离。
此模拟显示了如何通过始终选择与起点最近的未访问顶点作为下一个顶点来计算从顶点 D 到所有其他顶点的距离。
请遵循下面的逐步说明，了解 Dijkstra 算法如何计算最短距离的详细信息。
手动运行
考虑下图。
我们想要找到从源顶点 D 到所有其他顶点的最短路径，例如，到 C 的最短路径是 D->E->C，路径权重为 2+4=6。
为了找到最短路径，Dijkstra 算法使用一个数组来存储到所有其他顶点的距离，并最初将这些距离设置为无穷大或一个非常大的数字。而到我们开始的顶点（源点）的距离设置为 0。
distances = [inf, inf, inf, 0, inf, inf, inf]
#vertices [ A , B , C , D, E , F , G ]
下图显示了从起点 D 到其他顶点的初始无穷大距离。顶点 D 的距离值为 0，因为它是起点。
然后，Dijkstra 算法将顶点 D 设置为当前顶点，并查看到相邻顶点的距离。由于到顶点 A 和 E 的初始距离为无穷大，因此将它们的新距离更新为边权重。因此，顶点 A 的距离从 inf 变为 4，顶点 E 的距离从 inf 变为 2。如前一页所述，以这种方式更新距离值称为“松弛”。
松弛顶点 A 和 E 后，顶点 D 被认为是已访问的，不会再被访问。
下一个要选择作为当前顶点的顶点必须是所有先前未访问的顶点中，与源顶点（顶点 D）距离最短的顶点。因此，顶点 E 在顶点 D 之后被选为当前顶点。
现在必须计算到顶点 E 的所有相邻且之前未访问的顶点的距离，并在需要时更新这些距离。
通过 E 计算从 D 到顶点 A 的距离为 2+4=6。但是，当前到顶点 A 的距离已经为 4，更低，因此不会更新到顶点 A 的距离。
到顶点 C 的距离计算为 2+4=6，小于无穷大，因此更新到顶点 C 的距离。
类似地，计算并更新到节点 G 的距离，使其为 2+5=7。
下一个要访问的顶点是顶点 A，因为它在所有未访问的顶点中与 D 的距离最短。
通过 A 计算到顶点 C 的距离为 4+3=7，高于已设置的到顶点 C 的距离，因此不会更新到顶点 C 的距离。
顶点 A 现在被标记为已访问，下一个当前顶点是顶点 C，因为它在所有剩余未访问的顶点中与 D 的距离最低。
顶点 F 的更新距离为 6+5=11，顶点 B 的更新距离为 6+2=8。
通过顶点 C 计算到顶点 G 的距离为 6+5=11，高于已设置的距离 7，因此不会更新到顶点 G 的距离。
顶点 C 被标记为已访问，下一个要访问的顶点是 G，因为它在所有剩余未访问的顶点中距离最低。
顶点 F 已经有一个距离 11。这低于通过 G 计算的距离，即 7+5=12，因此不会更新到顶点 F 的距离。
顶点 G 被标记为已访问，B 成为当前顶点，因为它在所有剩余未访问的顶点中距离最低。
通过 B 计算到 F 的新距离为 8+2=10，因为它低于 F 的现有距离 11。
顶点 B 被标记为已访问，并且最后一个未访问的顶点 F 没有需要检查的内容，因此 Dijkstra 算法结束。
每个顶点只访问一次，结果是从源顶点 D 到图中所有其他顶点的最低距离。
Dijkstra 算法的实现
为了实现 Dijkstra 算法，我们创建了一个 Graph 类。该 Graph 类表示图及其顶点和边
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data第 3 行：我们创建了 adj_matrix 来保存所有边及其权重。初始值设置为 0。
第 4 行：size 是图中顶点的数量。
第 5 行：vertex_data 保存所有顶点的名称。
第 7-10 行：add_edge 方法用于添加从顶点 u 到顶点 v 的边，边权重为 weight。
第 12-14 行：add_vertex_data 方法用于向图中添加顶点。顶点应该所在的索引由 vertex 参数给出，data 是顶点的名称。
Graph 类还包含运行 Dijkstra 算法的方法。
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances第 18-19 行：初始距离在 distances 数组中对所有顶点都设置为无穷大，除了起点，其距离为 0。
第 20 行：所有顶点最初都设置为 False，以在 visited 数组中标记它们为未访问。
第 23-28 行：找到下一个当前顶点。将检查从该顶点发出的边，以查看是否可以找到更短的距离。它是未访问的顶点，与起点的距离最小。
第 30-31 行：如果未找到下一个当前顶点，则算法完成。这意味着已访问了从源头可达的所有顶点。
第 33 行：在松弛相邻顶点之前，将当前顶点设置为已访问。这样做效率更高，因为我们避免了检查与当前顶点本身的距离。
第 35-39 行：计算未访问的相邻顶点的距离，并在新的计算距离更低时进行更新。
定义完 Graph 类后，必须定义顶点和边来初始化特定的图，此 Dijkstra 算法示例的完整代码如下所示
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
self.adj_matrix[v][u] = weight # For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0, 4) # D - A, weight 5
g.add_edge(3, 4, 2) # D - E, weight 2
g.add_edge(0, 2, 3) # A - C, weight 3
g.add_edge(0, 4, 4) # A - E, weight 4
g.add_edge(4, 2, 4) # E - C, weight 4
g.add_edge(4, 6, 5) # E - G, weight 5
g.add_edge(2, 5, 5) # C - F, weight 5
g.add_edge(2, 1, 2) # C - B, weight 2
g.add_edge(1, 5, 2) # B - F, weight 2
g.add_edge(6, 5, 5) # G - F, weight 5
# Dijkstra's algorithm from D to all vertices
print("\nDijkstra's Algorithm starting from vertex D:")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
print(f"Distance from D to {g.vertex_data[i]}: {d}")有向图上的 Dijkstra 算法
要在有向图上运行 Dijkstra 算法，只需要做很少的更改。
与我们为 有向图的循环检测 所需的更改类似，我们只需要删除一行代码，这样邻接矩阵就不再是对称的了。
让我们实现此有向图并从顶点 D 运行 Dijkstra 算法。
以下是 Dijkstra 算法在有向图上的实现，其中 D 是源顶点
示例
Python
class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
self.size = size
self.vertex_data = [''] * size
def add_edge(self, u, v, weight):
if 0 <= u < self.size and 0 <= v < self.size:
self.adj_matrix[u][v] = weight
#self.adj_matrix[v][u] = weight For undirected graph
def add_vertex_data(self, vertex, data):
if 0 <= vertex < self.size:
self.vertex_data[vertex] = data
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
return distances
g = Graph(7)
g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')
g.add_edge(3, 0, 4) # D -> A, weight 5
g.add_edge(3, 4, 2) # D -> E, weight 2
g.add_edge(0, 2, 3) # A -> C, weight 3
g.add_edge(0, 4, 4) # A -> E, weight 4
g.add_edge(4, 2, 4) # E -> C, weight 4
g.add_edge(4, 6, 5) # E -> G, weight 5
g.add_edge(2, 5, 5) # C -> F, weight 5
g.add_edge(1, 2, 2) # B -> C, weight 2
g.add_edge(1, 5, 2) # B -> F, weight 2
g.add_edge(6, 5, 5) # G -> F, weight 5
# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances = g.dijkstra('D')
for i, d in enumerate(distances):
print(f"Shortest distance from D to {g.vertex_data[i]}: {d}")
下图显示了 Dijkstra 算法计算得出的从顶点 D 到其他顶点的最短距离。
此结果与之前在无向图上使用 Dijkstra 算法的示例类似。但是，有一个关键的区别：在这种情况下，无法从 D 访问顶点 B，这意味着从 D 到 F 的最短距离现在是 11，而不是 10，因为路径不再能经过顶点 B。
返回 Dijkstra 算法中的路径
通过一些调整，Dijkstra 算法除了返回最短路径值外，还可以返回实际的最短路径。例如，它不仅返回从顶点 D 到 F 的最短路径值为 10，还可以返回最短路径为“D->E->C->B->F”。
为了返回路径，我们创建了一个 predecessors 数组来保存每个顶点在最短路径中的前一个顶点。可以使用 predecessors 数组回溯，以找到每个顶点的最短路径。
示例
Python
class Graph:
# ... (rest of the Graph class)
def dijkstra(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None:
break
visited[u] = True
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
predecessors[v] = u
return distances, predecessors
def get_path(self, predecessors, start_vertex, end_vertex):
path = []
current = self.vertex_data.index(end_vertex)
while current is not None:
path.insert(0, self.vertex_data[current])
current = predecessors[current]
if current == self.vertex_data.index(start_vertex):
path.insert(0, start_vertex)
break
return '->'.join(path) # Join the vertices with '->'
g = Graph(7)
# ... (rest of the graph setup)
# Dijkstra's algorithm from D to all vertices
print("Dijkstra's Algorithm starting from vertex D:\n")
distances, predecessors = g.dijkstra('D')
for i, d in enumerate(distances):
path = g.get_path(predecessors, 'D', g.vertex_data[i])
print(f"{path}, Distance: {d}")
第 7 行和第 29 行：predecessors 数组首先用 None 值初始化，然后在更新最短路径值时，用每个顶点的正确前驱进行更新。
第 33-42 行：get_path 方法使用 predecessors 数组，并返回一个字符串，其中包含从起点到终点的最短路径。
具有单个目标顶点的 Dijkstra 算法
假设我们只对查找两个顶点之间的最短路径感兴趣，例如查找下图中顶点 D 和顶点 F 之间的最短距离。
Dijkstra 算法通常用于查找图中从一个源顶点到所有其他顶点的最短路径，但也可以对其进行修改，以便仅查找从源头到单个目标顶点的最短路径，只需在到达（访问）目标时停止算法即可。
这意味着对于上图中的特定图，Dijkstra 算法将在访问 F（目标顶点）后停止，而不会访问顶点 H、I 和 J，因为它们距离 D 比 F 更远。
以下显示了当 Dijkstra 算法找到从 D 到 F 的最短距离并停止运行时，计算出的距离的状态。
在上图中，顶点 F 刚刚从顶点 B 更新了距离 10。由于 F 是未访问的顶点，并且与 D 的距离最小，因此它通常是下一个当前顶点，但由于它是目标，因此算法停止。如果算法没有停止，则 J 将是下一个获得更新距离 11+2=13 的顶点，来自顶点 I。
以下代码是实现的 Dijkstra 算法，用于找到到单个目标顶点的最短路径
示例
Python
class Graph:
# ... (existing methods)
def dijkstra(self, start_vertex_data, end_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
end_vertex = self.vertex_data.index(end_vertex_data)
distances = [float('inf')] * self.size
predecessors = [None] * self.size
distances[start_vertex] = 0
visited = [False] * self.size
for _ in range(self.size):
min_distance = float('inf')
u = None
for i in range(self.size):
if not visited[i] and distances[i] < min_distance:
min_distance = distances[i]
u = i
if u is None or u == end_vertex:
print(f"Breaking out of loop. Current vertex: {self.vertex_data[u]}")
print(f"Distances: {distances}")
break
visited[u] = True
print(f"Visited vertex: {self.vertex_data[u]}")
for v in range(self.size):
if self.adj_matrix[u][v] != 0 and not visited[v]:
alt = distances[u] + self.adj_matrix[u][v]
if alt < distances[v]:
distances[v] = alt
predecessors[v] = u
return distances[end_vertex], self.get_path(predecessors, start_vertex_data, end_vertex_data)
# Example usage
g = Graph(7)
# ... (rest of the graph setup)
distance, path = g.dijkstra('D', 'F')
print(f"Path: {path}, Distance: {distance}")
第 20-23 行：如果我们即将选择目标顶点作为当前顶点并将其标记为已访问，则意味着我们已经计算出了到目标顶点的最短距离，并且可以在这种单个目标情况下停止 Dijkstra 算法。
Dijkstra 算法的时间复杂度
设 \(V\) 是图中顶点的数量，Dijkstra 算法的时间复杂度为
\[ O( V^2 ) \]
之所以得到这种时间复杂度，是因为必须搜索距离最小的顶点来选择下一个当前顶点，这需要 \(O(V)\) 时间。由于必须对与源头连接的每个顶点执行此操作，因此需要将其考虑在内，因此 Dijkstra 算法的时间复杂度为 \(O(V^2)\)。
通过使用最小堆或斐波那契堆数据结构来代替距离（本教程尚未解释），搜索最小距离顶点所需的时间从 \(O(V)\) 减少到 \(O( \log{V})\)，这将导致 Dijkstra 算法的时间复杂度得到改进
\[ O( V \cdot \log{V} + E ) \]
其中 \(V\) 是图中顶点的数量，\(E\) 是边的数量。
如果我们有一个大型稀疏图，即顶点数很多但边数不多的图，则使用最小堆数据结构来实现 Dijkstra 算法带来的改进尤其明显。
对于密集图，即每个顶点几乎都与其他每个顶点有边的图，使用斐波那契堆数据结构实现 Dijkstra 算法更好。
