python 如何实现贝尔曼算法
时间: 2024-01-30 17:03:17 浏览: 23
贝尔曼算法也称为动态规划算法,可以用于解决最短路径问题。下面是一个简单的Python实现:
```
def bellman_ford(graph, source):
# 初始化距离为无穷大
distance = {vertex: float('infinity') for vertex in graph}
# 源节点距离设为0
distance[source] = 0
for _ in range(len(graph) - 1):
for vertex in graph:
for neighbor in graph[vertex]:
# 计算新的距离
new_distance = distance[vertex] + graph[vertex][neighbor]
# 更新距离
if new_distance < distance[neighbor]:
distance[neighbor] = new_distance
# 检查负权回路
for vertex in graph:
for neighbor in graph[vertex]:
if distance[vertex] + graph[vertex][neighbor] < distance[neighbor]:
raise ValueError("图中存在负权回路")
return distance
```
其中,`graph`是一个字典,表示图中的邻接关系;`source`是源节点。首先初始化所有节点的距离为无穷大,源节点的距离为0。然后进行n-1次循环,每次循环更新每个节点的距离。最后再检查是否存在负权回路,如果存在则抛出异常,否则返回距离字典。