Bellman-Ford算法是一种用于求解单源最短路径问题的算法,可以处理有负权边的情况。然而,当存在负权环时,Bellman-Ford算法会陷入无限循环,导致无法得到正确的最短路径结果。
为了检测负权环,我们可以在Bellman-Ford算法中添加一个判断循环的步骤。具体步骤如下:
下面是使用邻接矩阵实现的Bellman-Ford算法,包含判断负权环的代码示例:
def bellman_ford(graph, source):
# Step 1: 初始化距离数组
dist = [float('inf')] * len(graph)
dist[source] = 0
# Step 2: 进行n-1轮松弛操作
for _ in range(len(graph) - 1):
for u in range(len(graph)):
for v in range(len(graph)):
if graph[u][v] != 0 and dist[u] + graph[u][v] < dist[v]:
dist[v] = dist[u] + graph[u][v]
# Step 3: 判断负权环
for u in range(len(graph)):
for v in range(len(graph)):
if graph[u][v] != 0 and dist[u] + graph[u][v] < dist[v]:
return True
return False
使用示例:
# 定义一个邻接矩阵表示的图
graph = [
[0, 6, 0, 0, 0],
[0, 0, -2, 0, 0],
[0, 0, 0, 1, 0],
[0, 0, 0, 0, -1],
[2, 0, 0, 0, 0]
]
# 检测是否存在负权环
has_negative_cycle = bellman_ford(graph, 0)
print(has_negative_cycle) # 输出: True
上述代码中,图的邻接矩阵表示存储在graph
变量中,其中0
表示两个节点之间没有边,负数表示有向边的权重。在示例中,存在一个负权环,因此最终输出为True
。