Bellman-Ford 算法代码
时间: 2024-01-16 21:05:34 浏览: 24
以下是 Bellman-Ford 算法的 Python 代码实现:
```python
# Bellman-Ford 算法
# 输入: 图 graph, 起点 source
# 输出: 距离列表 dist 和前驱节点列表 prev
INF = float('inf')
def bellman_ford(graph, source):
dist = {node: INF for node in graph} # 初始化距离为无穷大
prev = {node: None for node in graph} # 初始化前驱节点为 None
dist[source] = 0 # 起点距离为 0
# 进行 |V| - 1 次松弛操作
for _ in range(len(graph) - 1):
for node in graph:
for neighbor in graph[node]:
# 如果能够松弛当前节点,则更新距离和前驱节点
if dist[node] + graph[node][neighbor] < dist[neighbor]:
dist[neighbor] = dist[node] + graph[node][neighbor]
prev[neighbor] = node
# 检查是否存在负权环
for node in graph:
for neighbor in graph[node]:
if dist[node] + graph[node][neighbor] < dist[neighbor]:
raise ValueError('图中存在负权环')
return dist, prev
```
其中,`graph` 是以邻接表形式表示的图,`source` 是起点。函数返回两个字典,分别为距离列表 `dist` 和前驱节点列表 `prev`。如果图中存在负权环,则抛出 `ValueError` 异常。