Bellman-Ford算法能够找到图中的负环。负环是指一条的权值之和为负数的环路。如果在n次迭代后仍然存在松弛操作,那么说明图中存在负环。我们可以在遍历图的过程中记录每个节点到源节点的最短路径长度,如果在第n次松弛操作后仍然存在更新,那么说明图中存在负环。代码示例如下:
def bellman_ford(graph, start):
dist = {node: float('inf') for node in graph}
dist[start] = 0
for _ in range(len(graph) - 1):
for node in graph:
for neighbor in graph[node]:
distance = dist[node] + graph[node][neighbor]
if distance < dist[neighbor]:
dist[neighbor] = distance
for node in graph:
for neighbor in graph[node]:
if dist[node] + graph[node][neighbor] < dist[neighbor]:
return True
return False
当执行bellman_ford(graph, start)
时,如果返回True,说明图中存在负环;如果返回False,则说明图中不存在负环。