Day60--图论--94. 城市间货物运输 I（卡码网），95. 城市间货物运输 II（卡码网），96. 城市间货物运输 III（卡码网）

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）

思路：

1. 不优化时，由于要遍历所有的边，所以直接将所有的边存起来就好：List edges = new ArrayList();；队列优化时，需要用邻接表保存图，不然每次就要遍历找起点from对应的边了。
2. 队列记录，“要刷新的节点”，该节点需要poll出来处理，它所有邻接的节点的minDist
3. 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]); } }}