### 单源最短路径算法（支持负权重边）的Python实现 对于处理带有负权重边的图，贝尔曼-福特算法是一个适用的选择。该算法通过逐步松弛所有的边来找到从单一源节点到其他所有节点之间的最短路径[^2]。 #### 贝尔曼-福特算法的核心逻辑如下： 1. 初始化距离数组 `dist` 和前驱节点数组 `prev`。 2. 对于每一轮迭代，遍历所有边并尝试更新到达相邻顶点的距离。 3. 如果经过 |V|−1 次迭代后仍然可以进一步减少某些顶点的距离，则说明存在负权环路。 下面给出一个简单的 Python 实现示例： ```python def bellman_ford(graph, start_vertex): # 图形表示形式为字典 {node: [(neighbor_node, weight)]} dist = {} # 存储起点到各点最小距离 prev = {} # 记录上一步来自哪个结点 # 初始状态设置 for vertex in graph: dist[vertex] = float('inf') prev[vertex] = None dist[start_vertex] = 0 vertices_count = len(graph) # 进行最多 n-1 次循环 for _ in range(vertices_count - 1): relaxed_any_edge = False for u in graph: current_distance_to_u = dist[u] for v, w in graph[u]: new_dist_through_u = current_distance_to_u + w if new_dist_through_u < dist[v]: dist[v] = new_dist_through_u prev[v] = u relaxed_any_edge = True if not relaxed_any_edge: break # 检查是否存在负权回路 for u in graph: for v, w in graph[u]: if dist[u] != float("Inf") and dist[u] + w < dist[v]: raise ValueError("Graph contains a negative-weight cycle") return dist, prev ``` 此函数接收两个参数：一个是描述加权有向图的数据结构——邻接表；另一个是指定起始顶点的名字。返回的结果包含了两部分信息：一是从给定源头出发至各个目标位置所需的最少成本；二是重建这些最优路线所需的信息链。