### 使用 Python 实现基于 0-1 关系矩阵的 Bellman-Ford 算法 以下是使用 Python 编写的基于 0-1 邻接矩阵实现 Bellman-Ford 算法的代码示例。该算法能够处理含有负权重边的情况，并检测是否存在负权环。 #### 代码实现 ```python import math def bellman_ford_with_adjacency_matrix(matrix, source): """ 基于邻接矩阵实现 Bellman-Ford 算法。 :param matrix: 图的邻接矩阵，其中 inf 表示无连接 :param source: 起始节点索引 :return: 返回最短路径距离数组和前驱节点数组 """ n = len(matrix) distances = [math.inf] * n predecessors = [-1] * n # 初始化起始节点的距离为 0 distances[source] = 0 # 对每条边执行最多 n-1 次松弛操作 for _ in range(n - 1): for u in range(n): for v in range(n): weight = matrix[u][v] if weight != float('inf') and distances[u] + weight < distances[v]: distances[v] = distances[u] + weight predecessors[v] = u # 检测是否有负权环 for u in range(n): for v in range(n): weight = matrix[u][v] if weight != float('inf') and distances[u] + weight < distances[v]: raise ValueError("Graph contains a negative-weight cycle") return distances, predecessors # 测试用例 if __name__ == "__main__": INF = float('inf') graph = [ [0, 1, INF, INF], [INF, 0, 1, INF], [INF, INF, 0, 1], [1, INF, INF, 0] ] start_node = 0 try: dist, pred = bellman_ford_with_adjacency_matrix(graph, start_node) print(f"Distances from node {start_node}: {dist}") print(f"Predecessors array: {pred}") except ValueError as e: print(e) ``` --- #### 解释与分析 1. **初始化阶段**: 创建两个列表 `distances` 和 `predecessors`，分别用于存储从源节点到其他各节点的当前最短距离以及记录每个节点的前驱节点。初始状态下，除了源节点外，其余节点的距离均设为正无穷大[^4]。 2. **松弛操作**: 在每次迭代中遍历所有的边 `(u, v)` 并尝试更新目标节点 `v` 的距离值。如果通过当前节点 `u` 可以找到更短的路径到达 `v`，则更新 `distances[v]` 和对应的前驱节点 `predecessors[v]`[^1]。 3. **负权环检测**: 完成所有可能的松弛操作后，再次扫描整个图中的所有边。如果有任意一条边仍然满足进一步缩短条件，则表明存在负权环[^4]。 4. **时间复杂度**: 如果采用邻接矩阵作为输入结构，由于需要逐一访问每一个单元格，因此总的时间复杂度为 \( O(V^2) \)，其中 \( V \) 是顶点的数量[^4]。 --- #### 输出示例 对于给定测试用例： ```plaintext Distances from node 0: [0, 1, 2, 3] Predecessors array: [-1, 0, 1, 2] ``` 这表示从节点 0 出发到各个节点的最短路径分别为 `[0, 1, 2, 3]`，而前驱节点依次为 `[-1, 0, 1, 2]`。 --- ###