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

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<Edge> 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出来处理，它所有邻接的节点的minDistDeque<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]);}}
}

方法：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;// 入队次数+1countInQue[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]);}}
}

其关键在于本题的两个因素：

• 本题可以有负权回路，说明只要多做松弛，结果是会变的。
• 本题要求最多经过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]);}}
}