553 lines
17 KiB
Markdown
553 lines
17 KiB
Markdown
|
||
<p align="center"><strong><a href="./qita/join.md">参与本项目</a>，贡献其他语言版本的代码，拥抱开源，让更多学习算法的小伙伴们受益！</strong></p>
|
||
|
||
# bellman_ford之判断负权回路
|
||
|
||
[卡码网：95. 城市间货物运输 II](https://kamacoder.com/problempage.php?pid=1153)
|
||
|
||
【题目描述】
|
||
|
||
某国为促进城市间经济交流，决定对货物运输提供补贴。共有 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](./0094.城市间货物运输I.md) 延伸题目。
|
||
|
||
本题是要我们判断 负权回路，也就是图中出现环且环上的边总权值为负数。
|
||
|
||
如果在这样的图中求最短路的话， 就会在这个环里无限循环 （也是负数+负数 只会越来越小），无法求出最短路径。
|
||
|
||
所以对于 在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。
|
||
|
||
接下来我们来看 如何使用 bellman_ford 算法来判断 负权回路。
|
||
|
||
在 [kama94.城市间货物运输I](./0094.城市间货物运输I.md) 中 我们讲了 bellman_ford 算法的核心就是一句话：对 所有边 进行 n-1 次松弛。 同时文中的 【拓展】部分， 我们也讲了 松弛n次以上 会怎么样？
|
||
|
||
在没有负权回路的图中，松弛 n 次以上 ，结果不会有变化。
|
||
|
||
但本题有 负权回路，如果松弛 n 次，结果就会有变化了，因为 有负权回路 就是可以无限最短路径（一直绕圈，就可以一直得到无限小的最短距离）。
|
||
|
||
那么每松弛一次，都会更新最短路径，所以结果会一直有变化。
|
||
|
||
（如果对于 bellman_ford 不了解的录友，建议详细看这里：[kama94.城市间货物运输I](./0094.城市间货物运输I.md)）
|
||
|
||
以上为理论分析，接下来我们再画图举例。
|
||
|
||
我们拿题目中示例来画一个图：
|
||
|
||
|
||
|
||
图中 节点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](./0094.城市间货物运输I.md)）
|
||
|
||
而本题有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变。
|
||
|
||
那么解决本题的 核心思路，就是在 [kama94.城市间货物运输I](./0094.城市间货物运输I.md) 的基础上，再多松弛一次，看minDist数组 是否发生变化。
|
||
|
||
代码和 [kama94.城市间货物运输I](./0094.城市间货物运输I.md) 基本是一样的，如下：（关键地方已注释）
|
||
|
||
```CPP
|
||
#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](./0094.城市间货物运输I-SPFA) 中，我们讲过 在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n为节点数量），所以每个节点最多加入 n-1 次队列。
|
||
|
||
那么如果节点加入队列的次数 超过了 n-1次 ，那么该图就一定有负权回路。
|
||
|
||
所以本题也是可以使用 SPFA 来做的。 代码如下：
|
||
|
||
```CPP
|
||
#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;
|
||
}
|
||
}
|
||
```
|
||
|
||
以上代码看上去没问题，但提交之后会发现报错了，为什么呢？
|
||
|
||
例如这组数据：
|
||
|
||
```
|
||
4 6
|
||
1 4 3
|
||
1 2 1
|
||
1 3 1
|
||
3 2 -2
|
||
2 4 1
|
||
3 4 0
|
||
```
|
||
|
||
如图：
|
||
|
||
|
||
|
||
上面代码在执行的过程中，节点4 已经出队列了，但 计算入度会反复计算 节点4的入度，导致 误判 该图有环。
|
||
|
||
我们需要记录哪些节点已经出队列了，哪些节点在队列里面，对于已经出队列的节点不用统计入度，以下为优化后的代码：
|
||
|
||
```CPP
|
||
#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]++;
|
||
vector<bool> inQueue(n+1, false); // 记录节点是否在队列中
|
||
|
||
bool flag = false;
|
||
while (!que.empty()) {
|
||
|
||
int node = que.front(); que.pop();
|
||
inQueue[node] = false; // 节点出队
|
||
|
||
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;
|
||
if (!inQueue[to]) { // 避免重复入队
|
||
que.push(to);
|
||
inQueue[to] = true;
|
||
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;
|
||
}
|
||
}
|
||
```
|
||
|
||
## 其他语言版本
|
||
|
||
### Java
|
||
```Java
|
||
import java.util.*;
|
||
|
||
public class Main {
|
||
// 基于Bellman_ford-SPFA方法
|
||
// Define an inner class Edge
|
||
static class Edge {
|
||
int from;
|
||
int to;
|
||
int val;
|
||
public Edge(int from, int to, int val) {
|
||
this.from = from;
|
||
this.to = to;
|
||
this.val = val;
|
||
}
|
||
}
|
||
|
||
public static void main(String[] args) {
|
||
// Input processing
|
||
Scanner sc = new Scanner(System.in);
|
||
int n = sc.nextInt();
|
||
int m = sc.nextInt();
|
||
List<List<Edge>> graph = new ArrayList<>();
|
||
|
||
for (int i = 0; i <= n; i++) {
|
||
graph.add(new ArrayList<>());
|
||
}
|
||
|
||
for (int i = 0; i < m; i++) {
|
||
int from = sc.nextInt();
|
||
int to = sc.nextInt();
|
||
int val = sc.nextInt();
|
||
graph.get(from).add(new Edge(from, to, val));
|
||
}
|
||
|
||
// Declare the minDist array to record the minimum distance form current node to the original node
|
||
int[] minDist = new int[n + 1];
|
||
Arrays.fill(minDist, Integer.MAX_VALUE);
|
||
minDist[1] = 0;
|
||
|
||
// Declare a queue to store the updated nodes instead of traversing all nodes each loop for more efficiency
|
||
Queue<Integer> queue = new LinkedList<>();
|
||
queue.offer(1);
|
||
|
||
// Declare an array to record the times each node has been offered in the queue
|
||
int[] count = new int[n + 1];
|
||
count[1]++;
|
||
|
||
// Declare a boolean array to record if the current node is in the queue to optimise the processing
|
||
boolean[] isInQueue = new boolean[n + 1];
|
||
|
||
// Declare a boolean value to check if there is a negative weight loop inside the graph
|
||
boolean flag = false;
|
||
|
||
while (!queue.isEmpty()) {
|
||
int curNode = queue.poll();
|
||
isInQueue[curNode] = false; // Represents the current node is not in the queue after being polled
|
||
for (Edge edge : graph.get(curNode)) {
|
||
if (minDist[edge.to] > minDist[edge.from] + edge.val) { // Start relaxing the edge
|
||
minDist[edge.to] = minDist[edge.from] + edge.val;
|
||
if (!isInQueue[edge.to]) { // Don't add the node if it's already in the queue
|
||
queue.offer(edge.to);
|
||
count[edge.to]++;
|
||
isInQueue[edge.to] = true;
|
||
}
|
||
|
||
if (count[edge.to] == n) { // If some node has been offered in the queue more than n-1 times
|
||
flag = true;
|
||
while (!queue.isEmpty()) queue.poll();
|
||
break;
|
||
}
|
||
}
|
||
}
|
||
}
|
||
|
||
if (flag) {
|
||
System.out.println("circle");
|
||
} else if (minDist[n] == Integer.MAX_VALUE) {
|
||
System.out.println("unconnected");
|
||
} else {
|
||
System.out.println(minDist[n]);
|
||
}
|
||
}
|
||
}
|
||
|
||
```
|
||
|
||
### Python
|
||
|
||
Bellman-Ford方法求解含有负回路的最短路问题
|
||
|
||
```python
|
||
import sys
|
||
|
||
def main():
|
||
input = sys.stdin.read
|
||
data = input().split()
|
||
index = 0
|
||
|
||
n = int(data[index])
|
||
index += 1
|
||
m = int(data[index])
|
||
index += 1
|
||
|
||
grid = []
|
||
for i in range(m):
|
||
p1 = int(data[index])
|
||
index += 1
|
||
p2 = int(data[index])
|
||
index += 1
|
||
val = int(data[index])
|
||
index += 1
|
||
# p1 指向 p2，权值为 val
|
||
grid.append([p1, p2, val])
|
||
|
||
start = 1 # 起点
|
||
end = n # 终点
|
||
|
||
minDist = [float('inf')] * (n + 1)
|
||
minDist[start] = 0
|
||
flag = False
|
||
|
||
for i in range(1, n + 1): # 这里我们松弛n次，最后一次判断负权回路
|
||
for side in grid:
|
||
from_node = side[0]
|
||
to = side[1]
|
||
price = side[2]
|
||
if i < n:
|
||
if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
|
||
minDist[to] = minDist[from_node] + price
|
||
else: # 多加一次松弛判断负权回路
|
||
if minDist[from_node] != float('inf') and minDist[to] > minDist[from_node] + price:
|
||
flag = True
|
||
|
||
if flag:
|
||
print("circle")
|
||
elif minDist[end] == float('inf'):
|
||
print("unconnected")
|
||
else:
|
||
print(minDist[end])
|
||
|
||
if __name__ == "__main__":
|
||
main()
|
||
|
||
```
|
||
|
||
SPFA方法求解含有负回路的最短路问题
|
||
|
||
```python
|
||
from collections import deque
|
||
from math import inf
|
||
|
||
def main():
|
||
n, m = [int(i) for i in input().split()]
|
||
graph = [[] for _ in range(n+1)]
|
||
min_dist = [inf for _ in range(n+1)]
|
||
count = [0 for _ in range(n+1)] # 记录节点加入队列的次数
|
||
for _ in range(m):
|
||
s, t, v = [int(i) for i in input().split()]
|
||
graph[s].append([t, v])
|
||
|
||
min_dist[1] = 0 # 初始化
|
||
count[1] = 1
|
||
d = deque([1])
|
||
flag = False
|
||
|
||
while d: # 主循环
|
||
cur_node = d.popleft()
|
||
for next_node, val in graph[cur_node]:
|
||
if min_dist[next_node] > min_dist[cur_node] + val:
|
||
min_dist[next_node] = min_dist[cur_node] + val
|
||
count[next_node] += 1
|
||
if next_node not in d:
|
||
d.append(next_node)
|
||
if count[next_node] == n: # 如果某个点松弛了n次，说明有负回路
|
||
flag = True
|
||
if flag:
|
||
break
|
||
|
||
if flag:
|
||
print("circle")
|
||
else:
|
||
if min_dist[-1] == inf:
|
||
print("unconnected")
|
||
else:
|
||
print(min_dist[-1])
|
||
|
||
|
||
if __name__ == "__main__":
|
||
main()
|
||
```
|
||
|
||
### Go
|
||
|
||
### Rust
|
||
|
||
### JavaScript
|
||
|
||
### TypeScript
|
||
|
||
### PhP
|
||
|
||
### Swift
|
||
|
||
### Scala
|
||
|
||
### C#
|
||
|
||
### Dart
|
||
|
||
### C
|
||
|