DSA Bellman-Ford 算法
Bellman-Ford 算法
Bellman-Ford 算法最适合用于查找有向图中，从源顶点到所有其他顶点的最短路径，该图有一个或多个负边权重。
它通过重复检查图中所有边是否存在更短的路径来实现这一点，检查的次数等于图中的顶点数（减 1）。
Bellman-Ford 算法也可用于具有正边（有向和无向）的图，就像 Dijkstra 算法一样，但在这种情况下，Dijkstra 算法是首选，因为它更快。
在具有负环的图上使用 Bellman-Ford 算法将无法产生最短路径结果，因为在负环中，我们可以总能多绕一圈并获得更短的路径。
负环是我们可以围绕它走的路径，其中边权重的总和为负。
幸运的是，Bellman-Ford 算法可以实现为安全地检测和报告负环的存在。
工作原理
- 将源顶点的初始距离设置为零，将所有其他顶点的初始距离设置为无穷大。
- 对于每条边，检查是否可以计算出更短的距离，如果计算出的距离更短，则更新距离。
- 检查所有边（步骤 2） \(V-1\) 次。这是图中顶点数 (\(V\)) 减去一的次数。
- 可选：检查负环。稍后将更详细地解释这一点。
上面 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 出发的边 B->C。这会导致从顶点 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 行：双重 for 循环会检查邻接矩阵中的所有边。对于每个顶点 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 算法的结果。
但是，通过在放松每条边时记录每个顶点的 predecessor，我们可以在后续代码中使用它来打印结果，包括实际的最短路径。这意味着我们可以提供更多信息，除了路径权重之外还有实际路径：“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 数组保存了最短路径中每个顶点的 predecessor 顶点。
第 28 行：每次放松边时，predecessors 数组都会用新的 predecessor 顶点进行更新。
第 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 算法无法做到。
