代码随想录算法训练营第71天:路径算法
Bellman_ford 算法精讲
卡码网:94. 城市间货物运输 I(opens new window)
题目描述
某国为促进城市间经济交流,决定对货物运输提供补贴。共有 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
#思路
本题依然是单源最短路问题,求 从 节点1 到节点n 的最小费用。 但本题不同之处在于 边的权值是有负数了。
从 节点1 到节点n 的最小费用也可以是负数,费用如果是负数 则表示 运输的过程中 政府补贴大于运输成本。
在求单源最短路的方法中,使用dijkstra 的话,则要求图中边的权值都为正数。
我们在 dijkstra朴素版 中专门有讲解:为什么有边为负数 使用dijkstra就不行了。
本题是经典的带负权值的单源最短路问题,此时就轮到Bellman_ford登场了,接下来我们来详细介绍Bellman_ford 算法 如何解决这类问题。
该算法是由 R.Bellman 和L.Ford 在20世纪50年代末期发明的算法,故称为Bellman_ford算法。
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作(n为节点数量),从而求得目标最短路。
#什么叫做松弛
看到这里,估计大家都比较晕了,为什么是 n-1 次,那“松弛”这两个字究竟是个啥意思?
我们先来说什么是 “松弛”。
《算法四》里面把这个操作叫做 “放松”, 英文版里叫做 “relax the edge”
所以大家翻译过来,就是 “放松” 或者 “松弛” 。
但《算法四》没有具体去讲这个 “放松” 究竟是个啥? 网上很多题解也没有讲题解里的 “松弛这条边,松弛所有边”等等 里面的 “松弛” 究竟是什么意思?
这里我给大家举一个例子,每条边有起点、终点和边的权值。例如一条边,节点A 到 节点B 权值为value,如图:
minDist[B] 表示 到达B节点 最小权值,minDist[B] 有哪些状态可以推出来?
状态一: minDist[A] + value 可以推出 minDist[B] 状态二: minDist[B]本身就有权值 (可能是其他边链接的节点B 例如节点C,以至于 minDist[B]记录了其他边到minDist[B]的权值)
minDist[B] 应为如何取舍。
本题我们要求最小权值,那么 这两个状态我们就取最小的
if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value
也就是说,如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径,即如果 minDist[B] > minDist[A] + value
,那么我们就更新 minDist[B] = minDist[A] + value
,这个过程就叫做 “松弛” 。
以上讲了这么多,其实都是围绕以下这句代码展开:
if (minDist[B] > minDist[A] + value) minDist[B] = minDist[A] + value
这句代码就是 Bellman_ford算法的核心操作。
以上代码也可以这么写:minDist[B] = min(minDist[A] + value, minDist[B])
如果大家看过代码随想录的动态规划章节,会发现 无论是背包问题还是子序列问题,这段代码(递推公式)出现频率非常高的。
其实 Bellman_ford算法 也是采用了动态规划的思想,即:将一个问题分解成多个决策阶段,通过状态之间的递归关系最后计算出全局最优解。
(如果理解不了动态规划的思想也无所谓,理解我上面讲的松弛操作就好)
那么为什么是 n - 1次 松弛呢?
这里要给大家模拟一遍 Bellman_ford 的算法才行,接下来我们来看看对所有边松弛 n - 1 次的操作是什么样的。
我们依然使用minDist数组来表达 起点到各个节点的最短距离,例如minDist[3] = 5 表示起点到达节点3 的最小距离为5
#模拟过程
初始化过程。
起点为节点1, 起点到起点的距离为0,所以 minDist[1] 初始化为0
如图:
其他节点对应的minDist初始化为max,因为我们要求最小距离,那么还没有计算过的节点 默认是一个最大数,这样才能更新最小距离。
对所有边 进行第一次松弛: (什么是松弛,在上面我已经详细讲过)
以示例给出的所有边为例:
5 6 -2
1 2 1
5 3 1
2 5 2
2 4 -3
4 6 4
1 3 5
接下来我们来松弛一遍所有的边。
边:节点5 -> 节点6,权值为-2 ,minDist[5] 还是默认数值max,所以不能基于 节点5 去更新节点6,如图:
(在复习一下,minDist[5] 表示起点到节点5的最短距离)
边:节点1 -> 节点2,权值为1 ,minDist[2] > minDist[1] + 1 ,更新 minDist[2] = minDist[1] + 1 = 0 + 1 = 1 ,如图:
边:节点5 -> 节点3,权值为1 ,minDist[5] 还是默认数值max,所以不能基于节点5去更新节点3 如图:
边:节点2 -> 节点5,权值为2 ,minDist[5] > minDist[2] + 2 (经过上面的计算minDist[2]已经不是默认值,而是 1),更新 minDist[5] = minDist[2] + 2 = 1 + 2 = 3 ,如图:
边:节点2 -> 节点4,权值为-3 ,minDist[4] > minDist[2] + (-3),更新 minDist[4] = minDist[2] + (-3) = 1 + (-3) = -2 ,如图:
边:节点4 -> 节点6,权值为4 ,minDist[6] > minDist[4] + 4,更新 minDist[6] = minDist[4] + 4 = -2 + 4 = 2
边:节点1 -> 节点3,权值为5 ,minDist[3] > minDist[1] + 5,更新 minDist[3] = minDist[1] + 5 = 0 + 5 = 5 ,如图:
以上是对所有边进行一次松弛之后的结果。
那么需要对所有边松弛几次才能得到 起点(节点1) 到终点(节点6)的最短距离呢?
对所有边松弛一次,相当于计算 起点到达 与起点一条边相连的节点 的最短距离。
上面的距离中,我们得到里 起点达到 与起点一条边相邻的节点2 和 节点3 的最短距离,分别是 minDist[2] 和 minDist[3]
这里有录友疑惑了 minDist[3] = 5,分明不是 起点到达 节点3 的最短距离,节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 距离才是4。
注意我上面讲的是 对所有边松弛一次,相当于计算 起点到达 与起点一条边相连的节点 的最短距离,这里 说的是 一条边相连的节点。
与起点(节点1)一条边相邻的节点,到达节点2 最短距离是 1,到达节点3 最短距离是5。
而 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线 是 与起点 三条边相连的路线了。
所以对所有边松弛一次 能得到 与起点 一条边相连的节点最短距离。
那对所有边松弛两次 可以得到与起点 两条边相连的节点的最短距离。
那对所有边松弛三次 可以得到与起点 三条边相连的节点的最短距离,这个时候,我们就能得到到达节点3真正的最短距离,也就是 节点1 -> 节点2 -> 节点5 -> 节点3 这条路线。
那么再回归刚刚的问题,需要对所有边松弛几次才能得到 起点(节点1) 到终点(节点6)的最短距离呢?
节点数量为n,那么起点到终点,最多是 n-1 条边相连。
那么无论图是什么样的,边是什么样的顺序,我们对所有边松弛 n-1 次 就一定能得到 起点到达 终点的最短距离。
其实也同时计算出了,起点 到达 所有节点的最短距离,因为所有节点与起点连接的边数最多也就是 n-1 条边。
截止到这里,Bellman_ford 的核心算法思路,大家就了解的差不多了。
共有两个关键点。
- “松弛”究竟是个啥?
- 为什么要对所有边松弛 n - 1 次 (n为节点个数) ?
那么Bellman_ford的解题解题过程其实就是对所有边松弛 n-1 次,然后得出得到终点的最短路径。
#代码
理解上面讲解的内容,代码就更容易写了,本题代码如下:(详细注释)
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {
int n, m, p1, p2, val;
cin >> n >> m;vector<vector<int>> grid;// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2,权值为 val
grid.push_back({p1, p2, val});}
int start = 1; // 起点
int end = n; // 终点vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
for (vector<int> &side : grid) { // 每一次松弛,都是对所有边进行松弛
int from = side[0]; // 边的出发点
int to = side[1]; // 边的到达点
int price = side[2]; // 边的权值
// 松弛操作
// minDist[from] != INT_MAX 防止从未计算过的节点出发
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
}
}
}
if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径}
- 时间复杂度: O(N * E) , N为节点数量,E为图中边的数量
- 空间复杂度: O(N) ,即 minDist 数组所开辟的空间
关于空间复杂度,可能有录友疑惑,代码中数组grid不也开辟空间了吗? 为什么只算minDist数组的空间呢?
grid数组是用来存图的,这是题目描述中必须要使用的空间,而不是我们算法所使用的空间。
我们在讲空间复杂度的时候,一般都是说,我们这个算法所用的空间复杂度。
#拓展
有录友可能会想,那我 松弛 n 次,松弛 n + 1次,松弛 2 * n 次会怎么样?
其实没啥影响,结果不会变的,因为 题目中说了 “同时保证道路网络中不存在任何负权回路” 也就是图中没有 负权回路(在有向图中出现有向环 且环的总权值为负数)。
那么我们只要松弛 n - 1次 就一定能得到结果,没必要在松弛更多次了。
这里有疑惑的录友,可以加上打印 minDist数组 的日志,尝试一下,看看松弛 n 次会怎么样。
你会发现 松弛 大于 n - 1次,minDist数组 就不会变化了。
这里我给出打印日志的代码:
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {
int n, m, p1, p2, val;
cin >> n >> m;vector<vector<int>> grid;// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2,权值为 val
grid.push_back({p1, p2, val});}
int start = 1; // 起点
int end = n; // 终点vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
for (int i = 1; i < n; i++) { // 对所有边 松弛 n-1 次
for (vector<int> &side : grid) { // 每一次松弛,都是对所有边进行松弛
int from = side[0]; // 边的出发点
int to = side[1]; // 边的到达点
int price = side[2]; // 边的权值
// 松弛操作
// minDist[from] != INT_MAX 防止从未计算过的节点出发
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) {
minDist[to] = minDist[from] + price;
}
}
cout << "对所有边松弛 " << i << "次" << endl;
for (int k = 1; k <= n; k++) {
cout << minDist[k] << " ";
}
cout << endl;
}
if (minDist[end] == INT_MAX) cout << "unconnected" << endl; // 不能到达终点
else cout << minDist[end] << endl; // 到达终点最短路径}
通过打日志,大家发现,怎么对所有边进行第二次松弛以后结果就 不再变化了,那根本就不用松弛 n - 1 ?
这是本题的样例的特殊性, 松弛 n-1 次 是保证对任何图 都能最后求得到终点的最小距离。
如果还想不明白 我再举一个例子,用以下测试用例再跑一下。
6 5
5 6 1
4 5 1
3 4 1
2 3 1
1 2 1
打印结果:
对所有边松弛 1次
0 1 2147483647 2147483647 2147483647 2147483647
对所有边松弛 2次
0 1 2 2147483647 2147483647 2147483647
对所有边松弛 3次
0 1 2 3 2147483647 2147483647
对所有边松弛 4次
0 1 2 3 4 2147483647
对所有边松弛 5次
0 1 2 3 4 5
你会发现到 n-1 次 才打印出最后的最短路结果。
关于上面的讲解,大家一定要多写代码去实验,验证自己的想法。
至于 负权回路 ,我在下一篇会专门讲解这种情况,大家有个印象就好。
#总结
Bellman_ford 是可以计算 负权值的单源最短路算法。
其算法核心思路是对 所有边进行 n-1 次 松弛。
弄清楚 什么是 松弛? 为什么要 n-1 次? 对理解Bellman_ford 非常重要。
Bellman_ford 队列优化算法(又名SPFA)
卡码网:94. 城市间货物运输 I(opens new window)
题目描述
某国为促进城市间经济交流,决定对货物运输提供补贴。共有 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->节点5) 。
而松弛 边(节点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堆 中 图的存储 部分。
整体代码如下:
#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;vector<list<Edge>> grid(n + 1); // 邻接表// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2,权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;queue<int> 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 条指向该节点的边, 我再来举个例子,如图:
(opens new window)
图中 每个节点都与其他所有节点相连,节点数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)
,从而不会有新的节点加入到队列。
但如果本题有 负权回路,那情况就不一样了,我在下一题目讲解中,会重点讲解 负权回路 带来的变化。
bellman_ford之判断负权回路
卡码网:95. 城市间货物运输 II(opens new window)
【题目描述】
某国为促进城市间经济交流,决定对货物运输提供补贴。共有 n 个编号为 1 到 n 的城市,通过道路网络连接,网络中的道路仅允许从某个城市单向通行到另一个城市,不能反向通行。
网络中的道路都有各自的运输成本和政府补贴,道路的权值计算方式为:运输成本 - 政府补贴。权值为正表示扣除了政府补贴后运输货物仍需支付的费用;
权值为负则表示政府的补贴超过了支出的运输成本,实际表现为运输过程中还能赚取一定的收益。
然而,在评估从城市 1 到城市 n 的所有可能路径中综合政府补贴后的最低运输成本时,存在一种情况:图中可能出现负权回路。
负权回路是指一系列道路的总权值为负,这样的回路使得通过反复经过回路中的道路,理论上可以无限地减少总成本或无限地增加总收益。
为了避免货物运输商采用负权回路这种情况无限的赚取政府补贴,算法还需检测这种特殊情况。
请找出从城市 1 到城市 n 的所有可能路径中,综合政府补贴后的最低运输成本。同时能够检测并适当处理负权回路的存在。
城市 1 到城市 n 之间可能会出现没有路径的情况
【输入描述】
第一行包含两个正整数,第一个正整数 n 表示该国一共有 n 个城市,第二个整数 m 表示这些城市中共有 m 条道路。
接下来为 m 行,每行包括三个整数,s、t 和 v,表示 s 号城市运输货物到达 t 号城市,道路权值为 v。
【输出描述】
如果没有发现负权回路,则输出一个整数,表示从城市 1 到城市 n 的最低运输成本(包括政府补贴)。
如果该整数是负数,则表示实现了盈利。如果发现了负权回路的存在,则输出 “circle”。如果从城市 1 无法到达城市 n,则输出 “unconnected”。
输入示例
4 4
1 2 -1
2 3 1
3 1 -1
3 4 1
输出示例
circle
#思路
本题是 kama94.城市间货物运输I 延伸题目。
本题是要我们判断 负权回路,也就是图中出现环且环上的边总权值为负数。
如果在这样的图中求最短路的话, 就会在这个环里无限循环 (也是负数+负数 只会越来越小),无法求出最短路径。
所以对于 在有负权值的图中求最短路,都需要先看看这个图里有没有负权回路。
接下来我们来看 如何使用 bellman_ford 算法来判断 负权回路。
在 kama94.城市间货物运输I 中 我们讲了 bellman_ford 算法的核心就是一句话:对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分, 我们也讲了 松弛n次以上 会怎么样?
在没有负权回路的图中,松弛 n 次以上 ,结果不会有变化。
但本题有 负权回路,如果松弛 n 次,结果就会有变化了,因为 有负权回路 就是可以无限最短路径(一直绕圈,就可以一直得到无限小的最短距离)。
那么每松弛一次,都会更新最短路径,所以结果会一直有变化。
(如果对于 bellman_ford 不了解的录友,建议详细看这里:kama94.城市间货物运输I)
以上为理论分析,接下来我们再画图举例。
我们拿题目中示例来画一个图:
图中 节点1 到 节点4 的最短路径是多少(题目中的最低运输成本) (注意边可以为负数的)
节点1 -> 节点2 -> 节点3 -> 节点4,这样的路径总成本为 -1 + 1 + 1 = 1
而图中有负权回路:
那么我们在负权回路中多绕一圈,我们的最短路径 是不是就更小了 (也就是更低的运输成本)
节点1 -> 节点2 -> 节点3 -> 节点1 -> 节点2 -> 节点3 -> 节点4,这样的路径总成本 (-1) + 1 + (-1) + (-1) + 1 + (-1) + 1 = -1
如果在负权回路多绕两圈,三圈,无穷圈,那么我们的总成本就会无限小, 如果要求最小成本的话,你会发现本题就无解了。
在 bellman_ford 算法中,松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径,松弛 n 次以上,minDist数组(记录起到到其他节点的最短距离)中的结果也不会有改变 (如果对 bellman_ford 算法 不了解,也不知道 minDist 是什么,建议详看上篇讲解kama94.城市间货物运输I)
而本题有负权回路的情况下,一直都会有更短的最短路,所以 松弛 第n次,minDist数组 也会发生改变。
那么解决本题的 核心思路,就是在 kama94.城市间货物运输I 的基础上,再多松弛一次,看minDist数组 是否发生变化。
代码和 kama94.城市间货物运输I 基本是一样的,如下:(关键地方已注释)
#include <iostream>
#include <vector>
#include <list>
#include <climits>
using namespace std;int main() {
int n, m, p1, p2, val;
cin >> n >> m;vector<vector<int>> grid;for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2,权值为 val
grid.push_back({p1, p2, val});}
int start = 1; // 起点
int end = n; // 终点vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;
bool flag = false;
for (int i = 1; i <= n; i++) { // 这里我们松弛n次,最后一次判断负权回路
for (vector<int> &side : grid) {
int from = side[0];
int to = side[1];
int price = side[2];
if (i < n) {
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) minDist[to] = minDist[from] + price;
} else { // 多加一次松弛判断负权回路
if (minDist[from] != INT_MAX && minDist[to] > minDist[from] + price) flag = true;}
}}if (flag) cout << "circle" << endl;
else if (minDist[end] == INT_MAX) {
cout << "unconnected" << endl;
} else {
cout << minDist[end] << endl;
}
}
- 时间复杂度: O(N * E) , N为节点数量,E为图中边的数量
- 空间复杂度: O(N) ,即 minDist 数组所开辟的空间
#拓展
本题可不可 使用 队列优化版的bellman_ford(SPFA)呢?
上面的解法中,我们对所有边松弛了n-1次后,在松弛一次,如果出现minDist出现变化就判断有负权回路。
如果使用 SPFA 那么节点都是进队列的,那么节点进入队列几次后 足够判断该图是否有负权回路呢?
在 0094.城市间货物运输I-SPFA 中,我们讲过 在极端情况下,即:所有节点都与其他节点相连,每个节点的入度为 n-1 (n为节点数量),所以每个节点最多加入 n-1 次队列。
那么如果节点加入队列的次数 超过了 n-1次 ,那么该图就一定有负权回路。
所以本题也是可以使用 SPFA 来做的。 代码如下:
#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;vector<list<Edge>> grid(n + 1); // 邻接表// 将所有边保存起来
for(int i = 0; i < m; i++){
cin >> p1 >> p2 >> val;
// p1 指向 p2,权值为 val
grid[p1].push_back(Edge(p2, val));
}
int start = 1; // 起点
int end = n; // 终点vector<int> minDist(n + 1 , INT_MAX);
minDist[start] = 0;queue<int> que;
que.push(start); // 队列里放入起点 vector<int> count(n+1, 0); // 记录节点加入队列几次
count[start]++;bool flag = false;
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);
count[to]++;
if (count[to] == n) {// 如果加入队列次数超过 n-1次 就说明该图与负权回路
flag = true;
while (!que.empty()) que.pop();
break;
}
}
}
}if (flag) cout << "circle" << endl;
else if (minDist[end] == INT_MAX) {
cout << "unconnected" << endl;
} else {
cout << minDist[end] << endl;
}}