贝尔曼-福特算法是一种用于解决单源最短路径问题的算法。它通过对图中的所有边进行松弛操作,以逐步减小源节点到其他节点的距离估计值,直到得到最短路径。
下面是一个使用贝尔曼-福特算法求解最短路径的示例代码:
# 用于表示图中的边的类
class Edge:
def __init__(self, src, dest, weight):
self.src = src
self.dest = dest
self.weight = weight
# 计算最短路径的函数
def bellman_ford(graph, src):
# 初始化距离数组
dist = [float('inf')] * len(graph)
dist[src] = 0
# 对所有边进行松弛操作
for _ in range(len(graph) - 1):
for edge in graph:
u = edge.src
v = edge.dest
w = edge.weight
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# 检测是否存在负权回路
for edge in graph:
u = edge.src
v = edge.dest
w = edge.weight
if dist[u] != float('inf') and dist[u] + w < dist[v]:
print("图中存在负权回路")
return
# 打印最短路径
print("节点\t最短距离")
for i in range(len(dist)):
print(f"{i}\t{dist[i]}")
# 示例图
graph = [
Edge(0, 1, 4),
Edge(0, 2, 5),
Edge(1, 2, -3),
Edge(1, 3, 2),
Edge(3, 1, 1),
Edge(1, 4, 4),
Edge(4, 3, -1),
Edge(2, 4, 3),
]
# 指定源节点为0
bellman_ford(graph, 0)
以上代码通过创建一个Edge
类来表示图中的边,然后使用bellman_ford
函数来计算最短路径。该函数首先初始化距离数组,然后对所有边进行松弛操作,最后检测是否存在负权回路,并打印最短路径。示例图中的结果为:
节点 最短距离
0 0
1 4
2 1
3 3
4 3
同时松弛是指在每次松弛操作时,同时更新所有目标节点的距离估计值,而不是依次更新每个目标节点的距离估计值。在贝尔曼-福特算法中,我们使用两层循环来实现同时松弛的操作。
上一篇:贝尔曼-福特算法的短前导数组