全屋定制怎么样做网站,嘉兴网站快速排名优化,想自己做网站流程,网站的性能需求Bellman_ford 队列优化算法#xff08;又名SPFA#xff09;
卡码网#xff1a;94. 城市间货物运输 I
题目描述
某国为促进城市间经济交流#xff0c;决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市#xff0c;通过道路网络连接#xff0c;网络中的道路仅允许从…Bellman_ford 队列优化算法又名SPFA
卡码网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。输入示例6 7
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5思路
背景
本题我们来系统讲解 Bellman_ford 队列优化算法 也叫SPFA算法Shortest Path Faster Algorithm。SPFA的称呼来自 1994年西南交通大学段凡丁的论文其实Bellman_ford 提出后不久 20世纪50年代末期 就有队列优化的版本国际上不承认这个算法是是国内提出的。 所以国际上一般称呼 该算法为 Bellman_ford 队列优化算法Queue improved Bellman-Ford大家知道以上来历知道 SPFA 和 Bellman_ford 队列优化算法 指的都是一个算法就好。如果大家还不够了解 Bellman_ford 算法强烈建议按照《代码随想录》的顺序学习否则可能看不懂下面的讲解。Bellman_ford 算法每次松弛 都是对所有边进行松弛。但真正有效的松弛是基于已经计算过的节点再做的松弛。给大家举一个例子本图中对所有边进行松弛真正有效的松弛只有松弛 边节点1-节点2 和 边节点1-节点3 。而松弛 边节点4-节点6 边节点5-节点3等等 都是无效的操作因为 节点4 和 节点 5 都是没有被计算过的节点。所以 Bellman_ford 算法 每次都是对所有边进行松弛其实是多做了一些无用功。只需要对 上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。基于以上思路如何记录 上次松弛的时候更新过的节点呢用队列来记录。其实用栈也行对元素顺序没有要求
模拟过程 接下来来举例这个队列是如何工作的。以示例给出的所有边为例5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5我们依然使用minDist数组来表达 起点到各个节点的最短距离例如minDist[3] 5 表示起点到达节点3 的最小距离为5初始化起点为节点1 起点到起点的最短距离为0所以minDist[1] 为 0。 将节点1 加入队列 下次松弛从节点1开始从队列里取出节点1松弛节点1 作为出发点连接的边节点1 - 节点2和边节点1 - 节点3边节点1 - 节点2权值为1 minDist[2] minDist[1] 1 更新 minDist[2] minDist[1] 1 0 1 1 。边节点1 - 节点3权值为5 minDist[3] minDist[1] 5更新 minDist[3] minDist[1] 5 0 5 5。将节点2、节点3 加入队列如图从队列里取出节点2松弛节点2 作为出发点连接的边节点2 - 节点4和边节点2 - 节点5边节点2 - 节点4权值为1 minDist[4] minDist[2] (-3) 更新 minDist[4] minDist[2] (-3) 1 (-3) -2 。边节点2 - 节点5权值为2 minDist[5] minDist[2] 2 更新 minDist[5] minDist[2] 2 1 2 3 。将节点4节点5 加入队列如图从队列里出去节点3松弛节点3 作为出发点连接的边。因为没有从节点3作为出发点的边所以这里就从队列里取出节点3就好不用做其他操作如图从队列中取出节点4松弛节点4作为出发点连接的边节点4 - 节点6边节点4 - 节点6权值为4 minDist[6] minDist[4] 4更新 minDist[6] minDist[4] 4 -2 4 2 。将节点6加入队列从队列中取出节点5松弛节点5作为出发点连接的边节点5 - 节点3边节点5 - 节点6边节点5 - 节点3权值为1 minDist[3] minDist[5] 1 更新 minDist[3] minDist[5] 1 3 1 4边节点5 - 节点6权值为-2 minDist[6] minDist[5] (-2) 更新 minDist[6] minDist[5] (-2) 3 - 2 1因为节点3 和 节点6 都曾经加入过队列不用重复加入避免重复计算。在代码中我们可以用一个数组 visited 来记录入过队列的元素加入过队列的元素不再重复入队列。从队列中取出节点6松弛节点6 作为出发点连接的边。节点6作为终点没有可以出发的边。所以直接从队列中取出如图这样我们就完成了基于队列优化的bellman_ford的算法模拟过程。大家可以发现 基于队列优化的算法要比bellman_ford 算法 减少很多无用的松弛情况特别是对于边数众多的大图 优化效果明显。了解了大体流程我们再看代码应该怎么写。在上面模拟过程中我们每次都要知道 一个节点作为出发点连接了哪些节点。如果想方便知道这些数据就需要使用邻接表来存储这个图如果对于邻接表不了解的话可以看 kama0047.参会dijkstra堆 中 图的存储 部分。整体代码如下code c 1
#include iostream
#include vector
#include queue
#include list
#include climits
using namespace std;struct Edge { //邻接表int to; // 链接的节点int val; // 边的权重Edge(int t, int w): to(t), val(w) {} // 构造函数
};int main() {int n, m, p1, p2, val;cin n m;vectorlistEdge grid(n 1); // 邻接表// 将所有边保存起来for(int i 0; i m; i){cin p1 p2 val;// p1 指向 p2权值为 valgrid[p1].push_back(Edge(p2, val));}int start 1; // 起点int end n; // 终点vectorint minDist(n 1 , INT_MAX);minDist[start] 0;queueint que;que.push(start); // 队列里放入起点while (!que.empty()) {int node que.front(); que.pop(); // 先取出元素再删除元素for (Edge edge : grid[node]) {int from node;int to edge.to;int value edge.val;if (minDist[to] minDist[from] value) { // 开始松弛minDist[to] minDist[from] value;que.push(to); // 松弛过的元素加入队列}}}if (minDist[end] INT_MAX) cout unconnected endl; // 不能到达终点else cout minDist[end] endl; // 到达终点最短路径
}效率分析
队列优化版Bellman_ford 的时间复杂度 并不稳定效率高低依赖于图的结构。例如 如果是一个双向图且每一个节点和所有其他节点都相连的话那么该算法的时间复杂度就接近于 Bellman_ford 的 O(N * E) N 为节点数量E为边的数量。在这种图中每一个节点都会重复加入队列 n - 1次因为 这种图中 每个节点 都有 n-1 条指向该节点的边每条边指向该节点就需要加入一次队列。如果这里看不懂可以在重温一下代码逻辑至于为什么 双向图且每一个节点和所有其他节点都相连的话每个节点 都有 n-1 条指向该节点的边 我再来举个例子如图1--------2
^ ^
| |
| |
| |
| |
v v
3--------4图中 每个节点都与其他所有节点相连节点数n 为 4每个节点都有3条指向该节点的边即入度为3。n为其他数值的时候也是一样的。当然这种图是比较极端的情况也是最稠密的图。所以如果图越稠密则 SPFA的效率越接近与 Bellman_ford。反之图越稀疏SPFA的效率就越高。一般来说SPFA 的时间复杂度为 O(K * N) K 为不定值因为 节点需要计入几次队列取决于 图的稠密度。如果图是一条线形图且单向的话每个节点的入度为1那么只需要加入一次队列这样时间复杂度就是 O(N)。所以 SPFA 在最坏的情况下是 O(N * E)但 一般情况下 时间复杂度为 O(K * N)。尽管如此以上分析都是 理论上的时间复杂度分析。并没有计算 出队列 和 入队列的时间消耗。 因为这个在不同语言上 时间消耗也是不一定的。以C为例以下两段代码理论上时间复杂度都是 O(n) for (long long i 0; i n; i) {k;
}for (long long i 0; i n; i) {que.push(i);que.front();que.pop();
}在 MacBook Pro (13-inch, M1, 2020) 机器上分别测试这两段代码的时间消耗情况n 10^4第一段代码的时间消耗1ms第二段代码的时间消耗 4 ms
n 10^5第一段代码的时间消耗1ms第二段代码的时间消耗 13 ms
n 10^6第一段代码的时间消耗4ms第二段代码的时间消耗 59 ms
n 10^7第一段代码的时间消耗: 24ms第二段代码的时间消耗 463 ms
n 10^8第一段代码的时间消耗: 135ms第二段代码的时间消耗 4268 ms
在这里就可以看出 出队列和入队列 其实也是十分耗时的。SPFA队列优化版Bellman_ford 在理论上 时间复杂度更胜一筹但实际上也要看图的稠密程度如果 图很大且非常稠密的情况下虽然 SPFA的时间复杂度接近Bellman_ford但实际时间消耗 可能是 SPFA耗时更多。针对这种情况我在后面题目讲解中会特别加入稠密图的测试用例来给大家讲解。拓展
这里可能有录友疑惑while (!que.empty()) 队里里 会不会造成死循环 例如 图中有环这样一直有元素加入到队列里其实有环的情况要看它是 正权回路 还是 负权回路。题目描述中已经说了本题没有 负权回路 。如图正权回路 就是有环但环的总权值为正数。在有环且只有正权回路的情况下即使元素重复加入队列最后也会因为 所有边都松弛后节点数值minDist数组不在发生变化了 而终止。而且有重复元素加入队列是正常的多条路径到达同一个节点节点必要要选择一个最短的路径而这个节点就会重复加入队列进行判断选一个最短的在0094.城市间货物运输I 中我们讲过对所有边 最多松弛 n -1 次就一定可以求出所有起点到所有节点的最小距离即 minDist数组。即使再松弛n次以上 所有起点到所有节点的最小距离minDist数组 不会再变了。 这里如果不理解建议认真看0094.城市间货物运输I讲解所以本题我们使用队列优化有元素重复加入队列也会因为最后 minDist数组 不会在发生变化而终止。节点再加入队列需要有松弛的行为 而 每个节点已经都计算出来 起点到该节点的最短路径那么就不会有 执行这个判断条件if (minDist[to] minDist[from] value)从而不会有新的节点加入到队列。但如果本题有 负权回路那情况就不一样了我在下一题目讲解中会重点讲解 负权回路 带来的变化。
python code1
from collections import deque
def main1():# n, m 6, 5# edges [[5, 6, 1],[4, 5, 1],[3, 4, 1],[2, 3, 1],[1, 2, 1]]n, m 6, 7edges [[5, 6, -2],[1, 2, 1],[5, 3, 1],[2, 5, 2],[2, 4, -3],[4, 6, 4],[1, 3, 5]]grid [[] for _ in range(n1)]for edge in edges:grid[edge[0]].append(edge[1:])start 1 # 起点end n # 终点minDist [float(Inf) for _ in range(n1)]minDist[start] 0que deque()que.append(start) # 队列里放入起点while que:node que.popleft()for edge in grid[node]:s, t, val node, edge[0], edge[1]if minDist[t] minDist[s] val: # 开始松弛minDist[t] minDist[s] valque.append(t) # 松弛过的元素加入队列print(开始松弛)print(minDist)if minDist[end] float(Inf):print(unconnected) # 不能到达终点else: print(minDist[end]) # 到达终点最短路径
code python 打印记录结果 n, m 6, 5
edges [[5, 6, 1],[4, 5, 1],[3, 4, 1],[2, 3, 1],[1, 2, 1]]
开始松弛
[inf, 0, 1, inf, inf, inf, inf]
开始松弛
[inf, 0, 1, 2, inf, inf, inf]
开始松弛
[inf, 0, 1, 2, 3, inf, inf]
开始松弛
[inf, 0, 1, 2, 3, 4, inf]
开始松弛
[inf, 0, 1, 2, 3, 4, 5]
5n, m 6, 7
edges [[5, 6, -2],[1, 2, 1],[5, 3, 1],[2, 5, 2],[2, 4, -3],[4, 6, 4],[1, 3, 5]]开始松弛
[inf, 0, 1, inf, inf, inf, inf]
开始松弛
[inf, 0, 1, 5, inf, inf, inf]
开始松弛
[inf, 0, 1, 5, inf, 3, inf]
开始松弛
[inf, 0, 1, 5, -2, 3, inf]
开始松弛
[inf, 0, 1, 5, -2, 3, 1]
开始松弛
[inf, 0, 1, 4, -2, 3, 1]
1code python 2
from collections import deque
def main():n,m [int(v) for v in input().split( )]grid [[] for _ in range(n1)]for _ in range(m):v [int(v) for v in input().split( )]grid[v[0]].append([v[1], v[2]]) # 邻接表 将所有边保存起来 p1 指向 p2权值为 valstart 1 # 起点end n # 终点minDist [float(Inf) for _ in range(n1)]minDist[start] 0que deque()que.append(start) # 队列里放入起点while que:node que.popleft()for edge in grid[node]:s, t, val node, edge[0], edge[1]if minDist[t] minDist[s] val: # 开始松弛minDist[t] minDist[s] valque.append(t) # 松弛过的元素加入队列if minDist[end] float(Inf):print(unconnected) # 不能到达终点else: print(minDist[end]) # 到达终点最短路径
code python 3
from collections import dequeclass Edge:# 邻接表def __init__(self, to, val):self.to to # 链接的节点self.val val # 边的权重# n, m 6, 5
# edges [[5, 6, 1],[4, 5, 1],[3, 4, 1],[2, 3, 1],[1, 2, 1]]n, m 6, 7
edges [[5, 6, -2],[1, 2, 1],[5, 3, 1],[2, 5, 2],[2, 4, -3],[4, 6, 4],[1, 3, 5]]
grid [[] for _ in range(n1)]
for edge in edges:grid[edge[0]].append(Edge(edge[1], edge[2]))start 1 # 起点
end n # 终点minDist [float(Inf) for _ in range(n1)]
minDist[start] 0que deque()
que.append(start) # 队列里放入起点while que:node que.popleft()for edge in grid[node]:s, t, val node, edge.to, edge.valif minDist[t] minDist[s] val: # 开始松弛minDist[t] minDist[s] valque.append(t) # 松弛过的元素加入队列print(开始松弛)print(minDist)if minDist[end] float(Inf):print(unconnected) # 不能到达终点
else: print(minDist[end]) # 到达终点最短路径
