DSA Bellman-Ford 算法
Bellman-Ford 算法
Bellman-Ford 算法最适合用于在有向图中查找最短路径，其中一个或多个边权重为负，从源顶点到所有其他顶点。
它通过反复检查图中所有边以查找更短的路径来做到这一点，检查次数等于图中顶点的数量（减 1）。
Bellman-Ford 算法也可以用于具有正边权重的图（有向和无向），就像我们使用 Dijkstra 算法一样，但在这种情况下，Dijkstra 算法是首选，因为它更快。
在具有负环的图上使用 Bellman-Ford 算法不会产生最短路径的结果，因为在负环中，我们总是可以多走一圈以获得更短的路径。
负环是指我们可以循环遍历的路径，其中边权重的总和为负。
幸运的是，Bellman-Ford 算法可以实现为安全地检测和报告负环的存在。
工作原理
- 将源顶点的初始距离设置为零，并将所有其他顶点的初始距离设置为无穷大。
- 对于每条边，检查是否可以计算更短的距离，如果计算出的距离更短，则更新距离。
- 检查所有边（步骤 2）\(V-1\) 次。此次数等于图中顶点的数量 (\(V\)) 减 1。
- 可选：检查负环。这将在稍后详细解释。
上面的 Bellman-Ford 算法动画只显示了当检查边会导致更新距离时的情况，而没有显示所有没有导致更新距离的其他边检查。
手动运行
Bellman-Ford 算法实际上非常简单，因为它使用邻接矩阵检查所有边。每次检查都是为了查看是否可以通过从边一侧的顶点通过边到边另一侧的顶点来获得更短的距离。
此检查所有边操作将执行 \(V - 1\) 次，其中 \(V\) 是图中顶点的数量。
这就是 Bellman-Ford 算法在我们的图中检查邻接矩阵中的所有边 5-1=4 次的方式
已检查所有边 0 次。
我们图中检查的前四条边是 A->C、A->E、B->C 和 C->A。这前四条边检查没有导致任何最短距离更新，因为所有这些边的起点（顶点）的距离都是无穷大。
在检查完顶点 A、B 和 C 的边后，检查顶点 D 的边。由于起点（顶点 D）的距离为 0，因此顶点 A、B 和 C 的更新距离是从顶点 D 出发的边权重。
接下来要检查的边是从顶点 E 出发的边，这会导致顶点 B 和 C 的更新距离。
Bellman-Ford 算法现在已经检查了所有边 1 次。算法将在完成之前再检查所有边 3 次，因为 Bellman-Ford 将检查所有边与图中顶点数量相同的次数，减 1。
算法开始第二次检查所有边，从检查顶点 A 出发的边开始。检查边 A->C 和 A->E 没有导致更新距离。
接下来要检查的边是 B->C，从顶点 B 出发。这导致从顶点 D 到 C 的更新距离为 5-4=1。
检查下一条边 C->A，导致顶点 A 的更新距离为 1-3=-2。
在 Bellman-Ford 算法的第二轮中检查边 C->A 实际上是导致此特定图的距离更新的最后一次检查。算法将继续检查所有边另外 2 次，而不会更新任何距离。
在 Bellman-Ford 算法中检查所有边 \(V-1\) 次可能看起来很多，但这样做是为了确保始终找到最短距离。
Bellman-Ford 算法的实现
实现 Bellman-Ford 算法与 我们如何实现 Dijkstra 算法 非常相似。
我们首先创建 Graph 类，其中方法 __init__、add_edge 和 add_vertex 将用于创建我们想要运行 Bellman-Ford 算法以查找最短路径的特定图。
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] = databellman_ford 方法也放置在 Graph 类中。正是此方法运行 Bellman-Ford 算法。
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
return distances第 18-19 行： 在开头，所有顶点都设置为与起点具有无限长的距离，除了起点本身，其距离设置为 0。
第 21 行： 所有边都检查 \(V-1\) 次。
第 22-23 行： 双重循环检查邻接矩阵中的所有边。对于每个顶点 u，检查指向顶点 v 的边。
第 24-26 行： 如果边存在，并且如果计算出的距离比现有距离更短，则将距离更新为该顶点 v。
完整的代码，包括我们特定图的初始化和运行 Bellman-Ford 算法的代码，如下所示
示例
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 bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}-{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
return distances
g = Graph(5)
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_edge(3, 0, 4) # D -> A, weight 4
g.add_edge(3, 2, 7) # D -> C, weight 7
g.add_edge(3, 4, 3) # D -> E, weight 3
g.add_edge(0, 2, 4) # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5) # A -> E, weight 5
g.add_edge(4, 2, 3) # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2) # E -> B, weight 2
# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
distances = g.bellman_ford('D')
for i, d in enumerate(distances):
print(f"Distance from D to {g.vertex_data[i]}: {d}")Bellman-Ford 算法中的负边
说 Bellman-Ford 算法找到“最短路径”并不直观，因为我们如何绘制或想象负距离？因此，为了便于理解，我们可以说它找到的是 Bellman-Ford 算法找到的“最便宜 的路径”。
在实践中，Bellman-Ford 算法可以帮助我们找到送货路线，其中边权重表示燃料和其他物品的成本，减去在两个顶点之间行驶该边的收益。
考虑到这种解释，边 C->A 上的 -3 权重可能意味着从 C 到 A 行驶的燃料成本为 5 美元，而我们从 C 取货并在 A 送货获得的报酬为 8 美元。因此，我们最终赚到的钱比花掉的钱多 3 美元。因此，在上面的图中，通过行驶送货路线 D->E->B->C->A，总共可以赚取 2 美元。
Bellman-Ford 算法中的负环
如果我们可以在图中循环，并且该环中的边权重之和为负，那么我们就有一个负环。
通过将边 C->A 的权重从 -3 更改为 -9，我们得到了两个负环：A->C->A 和 A->E->C->A。并且每次我们使用 Bellman-Ford 算法检查这些边时，我们计算和更新的距离会越来越低。
负环的问题在于最短路径不存在，因为我们总是可以再走一圈以获得更短的路径。
这就是为什么在 Bellman-Ford 算法中实现负环检测非常有用的原因。
Bellman-Ford 算法中负环的检测
在运行 Bellman-Ford 算法之后，检查图中所有边 \(V-1\) 次后，将找到所有最短距离。
但是，如果图包含负环，并且我们再走一圈检查所有边，那么我们将在最后一轮中找到至少一个更短的距离，对吗？
因此，为了在 Bellman-Ford 算法中检测负环，在检查所有边 \(V-1\) 次之后，我们只需要再检查所有边一次，如果在最后一次检查中发现更短的距离，我们就可以断定存在负环。
下面是 bellman_ford 方法，包含负环检测，在上面具有负环的图上运行，由于 C->A 边的权重为 -9
示例
Python
def bellman_ford(self, start_vertex_data):
start_vertex = self.vertex_data.index(start_vertex_data)
distances = [float('inf')] * self.size
distances[start_vertex] = 0
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
# Negative cycle detection
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
return (True, None) # Indicate a negative cycle was found
return (False, distances) # Indicate no negative cycle and return distances第 30-33 行：再次检查所有边，以查看是否存在负环。
第 34 行：返回 True 表示存在负环，并且返回 None 而不是最短距离，因为在具有负环的图中查找最短距离没有意义（因为可以通过再次检查所有边来始终找到更短的距离）。
第 36 行：返回 False 表示不存在负环，并且可以返回 distances。
从 Bellman-Ford 算法返回路径
我们目前正在寻找最短路径的总权重，因此例如“从 D 到 A 的距离：-2”是运行 Bellman-Ford 算法的结果。
但是，通过在每次放松边时记录每个顶点的祖先，我们可以在代码中稍后使用它来打印结果，包括实际的最短路径。这意味着我们可以在结果中提供更多信息，包括实际路径以及路径权重：“D->E->B->C->A，距离：-2”。
最后一个代码示例是 Bellman-Ford 算法的完整代码，包含了我们迄今为止讨论的所有内容：查找最短路径的权重、检测负环以及查找实际的最短路径
示例
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 bellman_ford(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
for i in range(self.size - 1):
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
distances[v] = distances[u] + self.adj_matrix[u][v]
predecessors[v] = u
print(f"Relaxing edge {self.vertex_data[u]}->{self.vertex_data[v]}, Updated distance to {self.vertex_data[v]}: {distances[v]}")
# Negative cycle detection
for u in range(self.size):
for v in range(self.size):
if self.adj_matrix[u][v] != 0:
if distances[u] + self.adj_matrix[u][v] < distances[v]:
return (True, None, None) # Indicate a negative cycle was found
return (False, distances, predecessors) # Indicate no negative cycle and return distances
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)
g = Graph(5)
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_edge(3, 0, 4) # D -> A, weight 4
g.add_edge(3, 2, 7) # D -> C, weight 7
g.add_edge(3, 4, 3) # D -> E, weight 3
g.add_edge(0, 2, 4) # A -> C, weight 4
g.add_edge(2, 0, -3) # C -> A, weight -3
g.add_edge(0, 4, 5) # A -> E, weight 5
g.add_edge(4, 2, 3) # E -> C, weight 3
g.add_edge(1, 2, -4) # B -> C, weight -4
g.add_edge(4, 1, 2) # E -> B, weight 2
# Running the Bellman-Ford algorithm from D to all vertices
print("\nThe Bellman-Ford Algorithm starting from vertex D:")
negative_cycle, distances, predecessors = g.bellman_ford('D')
if not negative_cycle:
for i, d in enumerate(distances):
if d != float('inf'):
path = g.get_path(predecessors, 'D', g.vertex_data[i])
print(f"{path}, Distance: {d}")
else:
print(f"No path from D to {g.vertex_data[i]}, Distance: Infinity")
else:
print("Negative weight cycle detected. Cannot compute shortest paths.")第 19 行：predecessors 数组保存最短路径中每个顶点的祖先顶点。
第 28 行：每次放松边时，predecessors 数组都会更新为新的祖先顶点。
第 40-49 行：get_path 方法使用 predecessors 数组为每个顶点生成最短路径字符串。
Bellman-Ford 算法的时间复杂度
Bellman-Ford 算法的时间复杂度主要取决于嵌套循环。
外部 for 循环运行 \(V-1\) 次，或者在存在负环检测的情况下运行 \(V\) 次。对于具有许多顶点的图，检查比顶点数少一次的所有边差别很小，因此可以说外部循环对时间复杂度的贡献为 \(O(V)\)。
两个内部 for 循环检查图中的所有边。如果我们假设时间复杂度的最坏情况，那么我们有一个非常密集的图，其中每个顶点都与其他每个顶点都有边，因此对于所有顶点 \(V\)，必须检查到所有其他顶点 \(V\) 的边，这会对时间复杂度贡献 \(O(V^2)\)。
所以总的来说，我们得到 Bellman-Ford 算法的时间复杂度
\[ O(V^3) \]
然而，在实际情况中，尤其是对于稀疏图，这意味着每个顶点只与一小部分其他顶点有边，检查所有边的两个内部 for 循环的时间复杂度可以从 \(O(V^2)\) 近似为 \(O(E)\)，我们得到 Bellman-Ford 的总时间复杂度
\[ O(V \cdot E) \]
Bellman-Ford 算法的时间复杂度比 Dijkstra 算法慢，但 Bellman-Ford 可以在具有负边的图中找到最短路径，并且可以检测负环，而 Dijkstra 算法无法做到这一点。
