### Python 实现 Bellman-Ford 算法用于 0-1 邻接矩阵 Bellman-Ford 算法是一种能够处理带负权边的单源最短路径算法。对于给定的图 \( G(V, E) \)，其中邻接矩阵表示节点之间的连接关系，可以通过该算法计算从指定起点到其他所有节点的最短距离。 以下是基于 0-1 邻接矩阵实现 Bellman-Ford 算法的 Python 示例代码： ```python import math def bellman_ford(adj_matrix, source): """ 使用 Bellman-Ford 算法计算从起始节点到其余节点的最短路径。 :param adj_matrix: 图的邻接矩阵 (二维列表), 表示权重关系 :param source: 起始节点索引 :return: 返回两个列表 distance 和 predecessor distance[i] 是从 source 到 i 的最短距离, predecessor[i] 记录到达 i 的前驱节点 """ n = len(adj_matrix) inf = math.inf # 初始化距离数组和前驱数组 distance = [inf] * n predecessor = [-1] * n distance[source] = 0 # 源点到自身的距离为 0 # 对每条边执行最多 V-1 次松弛操作 for _ in range(n - 1): # 松弛操作次数不超过顶点数减一[^1] for u in range(n): for v in range(n): weight = adj_matrix[u][v] if weight != 0 and distance[u] + weight < distance[v]: distance[v] = distance[u] + weight predecessor[v] = u # 检查是否存在负权环 for u in range(n): for v in range(n): weight = adj_matrix[u][v] if weight != 0 and distance[u] + weight < distance[v]: raise ValueError("Graph contains a negative-weight cycle") # 存在负权环[^4] return distance, predecessor # 测试用例：定义一个简单的 0-1 邻接矩阵 if __name__ == "__main__": graph = [ [0, 1, 0, 0], # 从节点 0 出发 [0, 0, 1, 0], # 从节点 1 出发 [0, 0, 0, 1], # 从节点 2 出发 [0, 0, 0, 0] # 从节点 3 出发 ] start_node = 0 distances, predecessors = bellman_ford(graph, start_node) print(f"Distances from node {start_node}: {distances}") print(f"Predecessors array: {predecessors}") ``` #### 解析 1. **初始化阶段**: 创建 `distance` 数组并将所有值设为正无穷大 (\(+\infty\))，除了起点外。创建 `predecessor` 数组记录每个节点的前驱节点以便后续重建路径[^1]。 2. **松弛操作**: 外层循环运行 \(n-1\) 次（\(n\) 为节点数量），每次遍历所有的边并尝试更新目标节点的距离。如果找到更优解，则更新对应的 `distance` 和 `predecessor` 值[^1]。 3. **检测负权环**: 如果经过 \(n-1\) 次迭代后仍然可以进一步减少某些节点的距离，则说明存在负权环，抛出异常提示用户[^4]。 --- ###