python实现bellman-ford算法
时间: 2024-09-24 21:10:18 浏览: 18
贝尔曼-福特算法(Bellman-Ford Algorithm)是一种用于求解带权重有向图中单源最短路径问题的动态规划方法。在Python中,你可以按照以下步骤实现:
```python
def bellman_ford(graph, src):
# 初始化距离数组和前驱节点数组
V = len(graph)
dist = [float('inf')] * V
pred = [-1] * V
dist[src] = 0
# 进行V-1次迭代,每次更新所有边的距离
for _ in range(V - 1):
for u in range(V):
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
pred[v] = u
# 检查是否存在负权环
for u in range(V):
for v, w in graph[u]:
if dist[u] + w < dist[v]: # 如果存在,说明有负权环
return "Graph contains a negative weight cycle"
return dist, pred # 返回源点到所有顶点的最短距离及前驱节点
# 示例:
graph = {
0: [(1, 2), (2, 3)],
1: [(2, -1)],
2: [],
}
src = 0
dist, pred = bellman_ford(graph, src)
# 打印结果
for i in range(len(dist)):
print(f"Node {i}: Distance from source {src} is {dist[i]}, Predecessor is {pred[i]}")