SPFA算法（Bellman_ford 队列优化算法）

94. 城市间货物运输 I

题目描述

某国为促进城市间经济交流，决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市，通过道路网络连接，网络中的道路仅允许从某个城市单向通行到另一个城市，不能反向通行。

网络中的道路都有各自的运输成本和政府补贴，道路的权值计算方式为：运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用；权值为负则表示政府的补贴超过了支出的运输成本，实际表现为运输过程中还能赚取一定的收益。

请找出从城市 1 到城市 n 的所有可能路径中，综合政府补贴后的最低运输成本。如果最低运输成本是一个负数，它表示在遵循最优路径的情况下，运输过程中反而能够实现盈利。

城市 1 到城市 n 之间可能会出现没有路径的情况，同时保证道路网络中不存在任何负权回路。

输入描述

第一行包含两个正整数，第一个正整数 n 表示该国一共有 n 个城市，第二个整数 m 表示这些城市中共有 m 条道路。

接下来为 m 行，每行包括三个整数，s、t 和 v，表示 s 号城市运输货物到达 t 号城市，道路权值为 v （单向图）。

输出描述

如果能够从城市 1 到连通到城市 n，请输出一个整数，表示运输成本。如果该整数是负数，则表示实现了盈利。如果从城市 1 没有路径可达城市 n，请输出 "unconnected"。

输入示例

输出示例

提示信息

示例中最佳路径是从 1 -> 2 -> 5 -> 6，路上的权值分别为 1 2 -2，最终的最低运输成本为 1 + 2 + (-2) = 1。

示例 2：

4 2
1 2 -1
3 4 -1

在此示例中，无法找到一条路径从 1 通往 4，所以此时应该输出 "unconnected"。

数据范围：

1 <= n <= 1000；
1 <= m <= 10000;

-100 <= v <= 100;

SPFA算法

与Bellman的主要区别就是加入了一个队列，只有上次更新过的下次才需要更新，优化了很多不必要的判断，实现用的是邻接表。

import collections
if __name__ == '__main__':n, m = map(int, input().split())edges = collections.defaultdict(list)for _ in range(m):s, t, v = map(int, input().split())edges[s].append([t, v])minDistance = [float('inf')] * (n + 1)que= collections.deque()isInQue = [False] * (n + 1)minDistance[1] = 0que.append(1)isInQue[1] = Truewhile que:cur = que.popleft()isInQue[cur] = Falsefor t, v in edges[cur]:if minDistance[cur] + v < minDistance[t]:minDistance[t] = minDistance[cur] + vif not isInQue[t]:que.append(t)isInQue[t] = Trueif minDistance[n] == float('inf'):print('unconnected')else:print(minDistance[n])

这段代码实现了 SPFA（Shortest Path Faster Algorithm）算法，用于求解单源最短路径问题。SPFA 是 Bellman-Ford 算法的优化版本，通过队列动态更新最短路径，适用于稀疏图。以下是算法的详细总结：

算法核心思想

目标：
求解从起点（默认是节点 1）到其他所有节点的最短路径。
数据结构：
- edges：邻接表，存储图的边信息。edges[s] 是一个列表，存储从节点 s 出发的所有边，每条边包含目标节点 t 和边权重 v。
- minDistance：数组，存储从起点到每个节点的当前最短路径长度，初始值为 inf（无穷大）。
- que：队列，用于存储待处理的节点。
- isInQue：数组，标记节点是否在队列中，避免重复入队。
算法流程：
- 初始化：将起点 1 的最短路径设为 0，并将其加入队列。
- 循环处理队列中的节点：
  - 取出队首节点 cur，标记为不在队列中。
  - 遍历 cur 的所有邻接节点 t，尝试通过 cur 更新 t 的最短路径。
  - 如果更新成功且 t 不在队列中，则将 t 加入队列。
- 最终检查目标节点 n 的最短路径，若为 inf 则输出 unconnected，否则输出最短路径值。

代码逐行解析

输入处理：
- 读取节点数 n 和边数 m。
- 使用 collections.defaultdict(list) 构建邻接表 edges，存储图的边信息。
初始化：
- minDistance：初始化为 inf，表示所有节点到起点的距离未知。
- que：队列，初始包含起点 1。
- isInQue：标记数组，初始标记起点 1 在队列中。
主循环：
- 从队列中取出节点 cur，标记为不在队列中。
- 遍历 cur 的所有邻接节点 t：
  - 如果通过 cur 可以缩短 t 的最短路径（minDistance[cur] + v < minDistance[t]），则更新 minDistance[t]。
  - 如果 t 不在队列中，则将其加入队列。
输出结果：
- 检查 minDistance[n] 是否为 inf，若是则输出 unconnected，否则输出最短路径值。

算法特点

优点：
- 适用于稀疏图，时间复杂度通常为 O(k⋅m)O(k⋅m)，其中 kk 是常数。
- 动态更新路径，避免了对所有边的重复遍历（如 Bellman-Ford 算法）。
- 支持负权边（但不能有负权环）。
缺点：
- 最坏情况下时间复杂度退化为 O(n⋅m)O(n⋅m)（如存在负权环时）。
- 需要额外的队列和标记数组，空间复杂度为 O(n+m)O(n+m)。

示例运行

输入：

复制

执行过程：

初始化：
- minDistance = [inf, 0, inf, inf, inf]
- que = [1]
- isInQue = [False, True, False, False, False]
处理节点 1：
- 更新 minDistance[2] = 2，将 2 加入队列。
- 更新 minDistance[4] = 10，将 4 加入队列。
处理节点 2：
- 更新 minDistance[3] = 5，将 3 加入队列。
处理节点 4：
- 无更新。
处理节点 3：
- 更新 minDistance[4] = 9，将 4 加入队列。
处理节点 4：
- 无更新。
最终结果：
- minDistance = [inf, 0, 2, 5, 9]
- 输出 9。

适用场景

稀疏图（边数远小于 n2n2）。
需要处理负权边（但不能有负权环）。
单源最短路径问题。

我这套代码不知道为什么不行

这套代码用列表 edges 存储所有边，每次遍历时需要检查所有边，不知道为什么会报错潜在的数组或指针越界，请哪位大佬帮我看看。

class Edge:def __init__(self, left, right, value):self.left = leftself.right = rightself.value = valueimport collections
if __name__ == '__main__':n, m = map(int, input().split())edges = []for _ in range(m):s, t, v = map(int, input().split())edges.append(Edge(s, t, v))minDistance = [float('inf')] * (n + 1)que= collections.deque()isInQue = [False] * (n + 1)minDistance[1] = 0que.append(1)isInQue[1] = Truewhile que:for i in range(len(que)):cur = que.popleft()isInQue[cur] = Falsefor edge in edges:if edge.left == cur and minDistance[edge.left] + edge.value < minDistance[edge.right]:minDistance[edge.right] = minDistance[edge.left] + edge.valueif not isInQue[edge.right]:que.append(edge.right)isInQue[edge.right] = Trueif minDistance[n] == float('inf'):print('unconnected')else:print(minDistance[n])