### Python 实现 Bellman-Ford 算法 Bellman-Ford 算法是一种用于计算带权重图中最短路径的经典算法，能够处理负权边的情况[^2]。以下是基于 Python 的实现： #### 输入描述 - 图表示为邻接表形式 `graph`，其中键是节点编号，值是一个列表，每个元素由 `(邻居节点, 边权重)` 组成。 - 起始节点 `source`。 #### 输出描述 - 返回一个字典 `distance` 表示从起始节点到其他所有节点的最短距离。 - 如果存在负环，则返回错误提示。 ```python def bellman_ford(graph, source): # 初始化距离数组 distance = {node: float('inf') for node in graph} distance[source] = 0 # 进行 |V| - 1 次松弛操作 for _ in range(len(graph) - 1): for node in graph: for neighbor, weight in graph[node]: if distance[node] != float('inf') and distance[node] + weight < distance[neighbor]: distance[neighbor] = distance[node] + weight # 检查是否存在负权回路 for node in graph: for neighbor, weight in graph[node]: if distance[node] != float('inf') and distance[node] + weight < distance[neighbor]: raise ValueError("Graph contains a negative-weight cycle") return distance # 示例输入 if __name__ == "__main__": # 定义二元关系图（邻接表） graph = { 'A': [('B', -1), ('C', 4)], 'B': [('C', 3), ('D', 2), ('E', 2)], 'C': [], 'D': [('B', 1), ('C', 5)], 'E': [('D', -3)] } # 计算从源节点'A'出发的最短路径 try: result = bellman_ford(graph, 'A') print(result) except ValueError as e: print(e) ``` #### 解释 1. **初始化阶段**: 将所有节点的距离设置为无穷大 (`float('inf`)），除了起点外设为零。 2. **松弛操作**: 对每条边执行最多 \( V-1 \) 次松弛操作，更新可能更短的距离。 3. **检测负环**: 额外遍历一次图，如果还能找到可以进一步缩短的距离，则说明存在负权循环[^3]。 --- ###