DSA 迪杰斯特拉算法
迪杰斯特拉的单源最短路径算法由荷兰计算机科学家 Edsger W. Dijkstra 于 1956 年发明，当时他正在阿姆斯特丹和他的未婚妻一起购物，在咖啡休息的 20 分钟内完成。
发明该算法的原因是为了测试一台名为 ARMAC 的新计算机。
迪杰斯特拉算法
迪杰斯特拉算法找到从一个顶点到所有其他顶点的最短路径。
它通过反复选择最近的未访问顶点，并计算到所有未访问邻居顶点的距离来实现。
迪杰斯特拉算法通常被认为是解决最短路径问题最直观的算法。
迪杰斯特拉算法用于解决有向或无向图的单源最短路径问题。单源意味着选择一个顶点作为起点，算法将找出从该顶点到所有其他顶点的最短路径。
迪杰斯特拉算法不适用于带有负权边的图。对于带有负权边的图，可以使用下一页描述的 Bellman-Ford 算法代替。
为了找到最短路径，迪杰斯特拉算法需要知道哪个顶点是源点，需要一种方法来标记已访问的顶点，并且需要了解它在图中工作过程中到每个顶点的当前最短距离，并在找到更短的距离时更新这些距离。
工作原理
- 设置所有顶点的初始距离：源顶点的距离为 0，其他所有顶点的距离为无穷大。
- 选择到起点距离最短的未访问顶点作为当前顶点。因此，算法总是以源顶点作为当前顶点开始。
- 对于当前顶点的每个未访问邻居顶点，计算到源顶点的距离，并在计算出的新距离更低时更新距离。
- 我们现在完成了对当前顶点的处理，因此将其标记为已访问。已访问的顶点不会再次被检查。
- 返回步骤 2 以选择新的当前顶点，并重复这些步骤，直到所有顶点都已访问。
- 最后，我们得到了从源顶点到图中每个其他顶点的最短路径。
在上面的动画中，当一个顶点被标记为已访问时，该顶点及其边会变淡，以表明迪杰斯特拉算法已完成对该顶点的处理，并且不会再次访问它。
注意： 此基本版本的迪杰斯特拉算法提供了到每个顶点的最短路径成本值，但没有提供实际路径。因此，例如，在上面的动画中，我们得到到顶点 F 的最短路径成本值为 10，但算法并没有告诉我们哪些顶点（D->E->C->D->F）构成了这条最短路径。我们将在页面下方添加此功能。
迪杰斯特拉算法的详细模拟
运行下面的模拟，以更详细地了解迪杰斯特拉算法如何在特定图上运行，找出从顶点 D 到所有其他顶点的最短距离。
此模拟显示了如何通过始终选择离起点最近的未访问顶点来计算从顶点 D 到所有其他顶点的距离。
请按照下面的分步说明，了解迪杰斯特拉算法计算最短距离的所有详细信息。
手动演练
考虑以下图。
我们要查找从源顶点 D 到所有其他顶点的最短路径，例如到 C 的最短路径是 D->E->C，路径权重为 2+4=6。
为了找到最短路径，迪杰斯特拉算法使用一个包含到所有其他顶点距离的数组，并初始将这些距离设置为无穷大或一个非常大的数字。我们开始的顶点（源顶点）的距离设置为 0。
distances = [inf, inf, inf, 0, inf, inf, inf]
#vertices [ A , B , C , D, E , F , G ]
下图显示了从起始顶点 D 到其他顶点的初始无穷大距离。顶点 D 的距离值为 0，因为它是起点。
然后，迪杰斯特拉算法将顶点 D 设置为当前顶点，并查看到相邻顶点的距离。由于到顶点 A 和 E 的初始距离是无穷大，因此到它们的距离被更新为边权重。所以顶点 A 的距离从 inf 变为 4，顶点 E 的距离变为 2。正如前一页所述，以这种方式更新距离值称为“松弛”。
在松弛顶点 A 和 E 后，顶点 D 被视为已访问，并且不会再次访问。
下一个将被选为当前顶点的必须是到源顶点（顶点 D）距离最短的、之前未访问过的顶点。因此，在顶点 D 之后，顶点 E 被选为当前顶点。
现在必须计算从 E 到所有相邻且未访问过的顶点的距离，并在需要时进行更新。
通过 E 到顶点 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，因为它在剩余未访问顶点中到 D 的距离最低。
顶点 F 已经有距离 11。这比从 G 计算出的距离 7+5=12 更低，因此到 F 的距离未更新。
顶点 G 被标记为已访问，B 成为当前顶点，因为它在剩余未访问顶点中到 D 的距离最低。
通过 B 到 F 的新距离是 8+2=10，因为它比 F 的现有距离 11 更低。
顶点 B 被标记为已访问，最后一个未访问的顶点 F 没有什么需要检查的了，因此迪杰斯特拉算法完成。
每个顶点只被访问一次，结果是从源顶点 D 到图中每个其他顶点的最低距离。
迪杰斯特拉算法的实现
为了实现迪杰斯特拉算法，我们创建了一个 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 方法用于向顶点 v 添加从顶点 u 发出的边，边权重为 weight。
第 12-14 行：add_vertex_data 方法用于向图中添加一个顶点。vertex 参数给出顶点应属于的索引，而 data 是顶点的名称。
该 Graph 类还包含运行迪杰斯特拉算法的方法。
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 类后，必须定义顶点和边来初始化特定的图，此迪杰斯特拉算法示例的完整代码如下所示：
示例
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}")迪杰斯特拉算法在有向图上的应用
要在有向图上运行迪杰斯特拉算法，只需要进行很少的更改。
与我们在 有向图的循环检测 中所需的更改类似，我们只需删除一行代码，即可使邻接矩阵不再是对称的。
让我们来实现这个有向图并从顶点 D 运行迪杰斯特拉算法。
这是迪杰斯特拉算法在有向图上的实现，以 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}")
下图显示了迪杰斯特拉算法计算出的从顶点 D 到各顶点的最短距离。
此结果与之前在无向图上使用迪杰斯特拉算法的示例类似。但是，有一个关键区别：在这种情况下，顶点 B 无法从 D 访问，这意味着到 F 的最短路径现在是 11，而不是 10，因为路径无法再通过顶点 B。
返回迪杰斯特拉算法的路径
通过一些调整，迪杰斯特拉算法除了返回最短路径值外，还可以返回实际的最短路径。因此，例如，算法不仅返回从顶点 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 数组，并返回一个字符串，其中包含从起始顶点到结束顶点的最短路径。
迪杰斯特拉算法与单个目标顶点
假设我们只对查找两个顶点之间的最短路径感兴趣，例如在下面的图中查找顶点 D 和顶点 F 之间的最短距离。
迪杰斯特拉算法通常用于查找从一个源顶点到图中所有其他顶点的最短路径，但也可以对其进行修改，使其仅查找从源顶点到单个目标顶点的最短路径，只需在到达（访问）目标时停止算法即可。
这意味着对于上图中所示的特定图，迪杰斯特拉算法将在访问 F（目标顶点）后停止，而在访问顶点 H、I 和 J 之前停止，因为它们距离 D 比 F 更远。
下面可以看到迪杰斯特拉算法找到从 D 到 F 的最短距离并停止运行时计算出的距离状态。
在上图中，顶点 F 刚刚通过顶点 B 更新了距离 10。由于 F 是到 D 的距离最短的未访问顶点，因此它通常会成为下一个当前顶点，但由于它是目标，因此算法停止。如果算法不停止，J 将是下一个获得更新距离 11+2=13（来自顶点 I）的顶点。
下面的代码是实现迪杰斯特拉算法以查找到单个目标顶点的最短路径。
示例
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 行：如果我们即将选择目标顶点作为当前顶点并将其标记为已访问，这意味着我们已经计算出了到目标顶点的最短距离，并且在这种单个目标情况下，迪杰斯特拉算法可以停止。
迪杰斯特拉算法的时间复杂度
设 \(V\) 为图中顶点的数量，则迪杰斯特拉算法的时间复杂度为
\[ O( V^2 ) \]
我们获得此时间复杂度的原因是，必须搜索距离最低的顶点以选择下一个当前顶点，这需要 \(O(V)\) 时间。由于必须对连接到源的每个顶点执行此操作，因此我们需要考虑这一点，因此我们得到迪杰斯特拉算法的时间复杂度为 \(O(V^2)\)。
通过使用最小堆或斐波那契堆数据结构来代替距离（本教程尚未解释），搜索最小距离顶点所需的时间从 \(O(V)\) 减少到 \(O(\log{V})\)，从而提高了迪杰斯特拉算法的时间复杂度
\[ O( V \cdot \log{V} + E ) \]
其中 \(V\) 是图中的顶点数，\(E\) 是图中的边数。
使用最小堆数据结构改进迪杰斯特拉算法的时间复杂度对于拥有大型稀疏图（即顶点数量多但边数量不多）尤其有利。
使用斐波那契堆数据结构的迪杰斯特拉算法实现更适合稠密图，其中每个顶点都与几乎所有其他顶点相连。
