Day60–图论–94. 城市间货物运输 I（卡码网），95. 城市间货物运输 II（卡码网），96. 城市间货物运输 III（卡码网）
今天是Bellman_ford专场。带你从普通的Bellman_ford，到队列优化的Bellman_ford（SPFA算法），到使用Bellman_ford解决负权回路问题，和使用Bellman_ford解决单源有限最短回路问题。
总共3道题目，六种做法。
94. 城市间货物运输 I（卡码网）
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作（n为节点数量），从而求得目标最短路。
其实 Bellman_ford算法 也是采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。
Bellman_ford 是可以计算 负权值的单源最短路算法。
其算法核心思路是对 所有边进行 n-1 次 松弛。
方法：Bellman_ford
思路：
核心思路代码：
if (minDist[e.to] > minDist[e.from] + e.val) minDist[e.to] = minDist[e.from] + e.val;
如果改一改样子，是不是跟动态规划很像呢？
minDist[B] = min(minDist[A] + value, minDist[B])
其实松弛操作，就是进行“动态规划”。因为每更新一个节点的状态，都会影响其它节点。
所以每更新一个节点，就对全部节点的状态进行更新。（n个节点，更新n-1一次）
实际上，每更新一个节点，并不一定要更新全部节点的minDist。所以下面会讲到优化的方式。
import java.util.*;
public class Main {
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) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Edge> edges = new ArrayList<>();
// 将所有边保存起来
for (int i = 0; i < m; i++) {
int from = in.nextInt();
int to = in.nextInt();
int val = in.nextInt();
edges.add(new Edge(from, to, val));
}
int start = 1; // 起点
int end = n; // 终点
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 对所有边 松弛 n-1 次（这里遍历的是节点，从1遍历到n-1）
for (int i = 1; i < n; i++) {
// 每一次松弛，都是对所有边进行松弛
for (Edge e : edges) {
// 松弛操作
if (minDist[e.from] != Integer.MAX_VALUE
&& minDist[e.to] > minDist[e.from] + e.val) {
minDist[e.to] = minDist[e.from] + e.val;
}
}
}
// 不能到达终点
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
// 到达终点最短路径（运输成本最小）
System.out.println(minDist[end]);
}
}
}
不用队列优化的时候，一旦一个节点更新了，就要刷新整个图的所有节点的minDist，但是这样有很多操作是多余的。比如节点1只和2,3相连，就应该只刷新2,3的midDist。我们用队列记录“要刷新的节点”，可以减少很多操作。
但是队列的入队和出队也是有性能损耗的，如果是稠密图，边比较多，而且互相连接的节点比较多的话，队列带来的性能损耗可能会超过原来遍历节点的损耗。
故此，稀疏图适合用队列优化，稠密图的话，队列优化效果不明显，加上队列操作，还甚至有可能比不优化更加耗时。
方法： 队列优化的 Bellman_ford（又名SPFA）
思路：
- 不优化时，由于要遍历所有的边，所以直接将所有的边存起来就好：
List<Edge> edges = new ArrayList<>();；队列优化时，需要用邻接表保存图，不然每次就要遍历找起点from对应的边了。 - 队列记录，“要刷新的节点”，该节点需要poll出来处理，它所有邻接的节点的minDist
boolean[] isInQue记录在队列，已经在队列的不要重复添加。
import java.util.*;
public class Main {
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) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.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 = in.nextInt();
int to = in.nextInt();
int val = in.nextInt();
graph.get(from).add(new Edge(from, to, val));
}
int start = 1; // 起点
int end = n; // 终点
// 存储从源点到每个节点的最短距离
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 队列记录，“要刷新的节点”，该节点需要poll出来处理，它所有邻接的节点的minDist
Deque<Integer> que = new ArrayDeque<>();
que.offer(start);
// 在队列标志
boolean[] isInQue = new boolean[n + 1];
while (!que.isEmpty()) {
int cur = que.poll();
isInQue[cur] = false;
for (Edge e : graph.get(cur)) {
// 松弛操作
if (minDist[e.to] > minDist[e.from] + e.val) {
minDist[e.to] = minDist[e.from] + e.val;
// 避免重复入队
if (!isInQue[e.to]) {
que.offer(e.to);
isInQue[e.to] = true;
}
}
}
}
// 不能到达终点
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println("unconnected");
} else {
// 到达终点最短路径（运输成本最小）
System.out.println(minDist[end]);
}
}
}
95. 城市间货物运输 II（卡码网）
方法：bellman_ford之判断负权回路
思路：
负权回路的意思：出现环，每走一次环，得出的sum是负数。因为求的是最小值min，所以会一直在这个环转圈圈。
在 bellman_ford 算法中，松弛 n-1 次所有的边 就可以求得 起点到任何节点的最短路径，松弛 n 次以上，minDist数组（记录起到到其他节点的最短距离）中的结果也不会有改变
而本题有负权回路的情况下，一直都会有更短的最短路，所以 松弛 第n次，minDist数组 也会发生改变。
那么解决本题的 核心思路，就是在 《上题》 的基础上，再多松弛一次，看minDist数组 是否发生变化。
import java.util.*;
public class Main {
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) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < m; i++) {
int from = in.nextInt();
int to = in.nextInt();
int val = in.nextInt();
edges.add(new Edge(from, to, val));
}
int start = 1;
int end = n;
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 这里我们松弛n次，最后一次判断负权回路
boolean circle = false;
for (int i = 1; i <= n; i++) {
for (Edge e : edges) {
if (i < n) {
// 照常
if (minDist[e.from] != Integer.MAX_VALUE
&& minDist[e.to] > minDist[e.from] + e.val) {
minDist[e.to] = minDist[e.from] + e.val;
}
} else {
// 多加一次松弛判断负权回路
if (minDist[e.from] != Integer.MAX_VALUE
&& minDist[e.to] > minDist[e.from] + e.val) {
circle = true;
}
}
}
}
// 出现负权回路，转圈圈。
if (circle) {
System.out.println("circle");
} else if (minDist[end] == Integer.MAX_VALUE) {
// 不能到达终点
System.out.println("unconnected");
} else {
// 到达终点最短路径（运输成本最小）
System.out.println(minDist[end]);
}
}
}
方法： 队列优化的 Bellman_ford（又名SPFA）
思路：
思路同上，统计是否有节点，遍历过n次。
如果有，证明存在负权回路，在转圈圈了，此时，清空队列，退出循环。
import java.util.*;
public class Main {
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) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.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 = in.nextInt();
int to = in.nextInt();
int val = in.nextInt();
graph.get(from).add(new Edge(from, to, val));
}
int start = 1;
int end = n;
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
Deque<Integer> que = new ArrayDeque<>();
que.offer(start);
boolean[] isInQue = new boolean[n + 1];
// 统计该节点，入队的次数
int[] countInQue = new int[n + 1];
countInQue[start]++;
// 是否存在负权回路，转圈圈的标志
boolean circle = false;
while (!que.isEmpty()) {
int cur = que.poll();
isInQue[cur] = false;
for (Edge e : graph.get(cur)) {
if (minDist[e.to] > minDist[e.from] + e.val) {
minDist[e.to] = minDist[e.from] + e.val;
// 避免重复入队
if (!isInQue[e.to]) {
que.offer(e.to);
isInQue[e.to] = true;
// 入队次数+1
countInQue[e.to]++;
}
// 如果有节点入队n次，证明已经开始转圈圈，清空队列，退出循环
if (countInQue[e.to] == n) {
circle = true;
que.clear();
break;
}
}
}
}
// 出现负权回路，转圈圈。
if (circle) {
System.out.println("circle");
} else if (minDist[end] == Integer.MAX_VALUE) {
// 不能到达终点
System.out.println("unconnected");
} else {
// 到达终点最短路径（运输成本最小）
System.out.println(minDist[end]);
}
}
}
96. 城市间货物运输 III（卡码网）
其关键在于本题的两个因素：
- 本题可以有负权回路，说明只要多做松弛，结果是会变的。
- 本题要求最多经过k个节点，对松弛次数是有限制的。
方法：bellman_ford之单源有限最短路
思路：
最多经过k座城市，加上start和end，就是一共有k+2个城市。所以要遍历k+1次。
使用minDistCopy记录上一轮遍历的结果。
import java.util.*;
public class Main {
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) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < m; i++) {
int from = in.nextInt();
int to = in.nextInt();
int val = in.nextInt();
edges.add(new Edge(from, to, val));
}
int start = in.nextInt();
int end = in.nextInt();
// 最多经过k座城市，加上start和end，就是一共有k+2个城市
int k = in.nextInt();
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 用来记录上一轮遍历的结果
int[] minDistCopy = new int[n + 1];
// 一共有k+2个城市，所以要遍历k+1遍
for (int i = 1; i <= k + 1; i++) {
// 复制上一轮遍历的结果
System.arraycopy(minDist, 0, minDistCopy, 0, n + 1);
for (Edge e : edges) {
if (minDistCopy[e.from] != Integer.MAX_VALUE
&& minDist[e.to] > minDistCopy[e.from] + e.val) {
minDist[e.to] = minDistCopy[e.from] + e.val;
}
}
}
if (minDist[end] == Integer.MAX_VALUE) {
// 不能到达终点
System.out.println("unreachable");
} else {
// 到达终点最短路径（运输成本最小）
System.out.println(minDist[end]);
}
}
}
方法： 队列优化的 Bellman_ford（又名SPFA）
思路：
关键在于 如何控制松弛k次。可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量。
下一轮松弛的时候，就把队列里 que_size 个节点都弹出来，就是上一轮松弛入队列的节点。
import java.util.*;
public class Main {
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) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.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 = in.nextInt();
int to = in.nextInt();
int val = in.nextInt();
graph.get(from).add(new Edge(from, to, val));
}
int start = in.nextInt();
int end = in.nextInt();
// 最多经过k座城市，加上start和end，就是一共有k+2个城市
int k = in.nextInt();
// 原来要遍历n-1次，现在有k+2个节点，所以要遍历k+1次
k++;
int[] minDist = new int[n + 1];
Arrays.fill(minDist, Integer.MAX_VALUE);
minDist[start] = 0;
// 用来记录上一轮遍历的结果
int[] minDistCopy = new int[n + 1];
Deque<Integer> que = new ArrayDeque<>();
que.offer(start);
int queSize = 0;
while (k-- > 0 && !que.isEmpty()) {
// isInQue标志，每一轮都要初始化一次
boolean[] isInQue = new boolean[n + 1];
// 复制上一轮遍历的结果
System.arraycopy(minDist, 0, minDistCopy, 0, n + 1);
// 这一轮要松弛的个数
queSize = que.size();
// 开始这一轮
while (queSize-- > 0) {
int cur = que.poll();
isInQue[cur] = false;
for (Edge e : graph.get(cur)) {
if (minDist[e.to] > minDistCopy[e.from] + e.val) {
minDist[e.to] = minDistCopy[e.from] + e.val;
if (!isInQue[e.to]) {
que.offer(e.to);
isInQue[e.to] = true;
}
}
}
}
}
// 不能到达终点
if (minDist[end] == Integer.MAX_VALUE) {
System.out.println("unreachable");
} else {
// 到达终点最短路径（运输成本最小）
System.out.println(minDist[end]);
}
}
}