网站改版的目的,免费建站优化,网络推广工作室 是干啥的,网站建设编程软件Day60–图论–94. 城市间货物运输 I#xff08;卡码网#xff09;#xff0c;95. 城市间货物运输 II#xff08;卡码网#xff09;#xff0c;96. 城市间货物运输 III#xff08;卡码网#xff09; 今天是Bellman_ford专场。带你从普通的Bellman_ford#xff0c;到队列…Day60–图论–94. 城市间货物运输 I卡码网95. 城市间货物运输 II卡码网96. 城市间货物运输 III卡码网 今天是Bellman_ford专场。带你从普通的Bellman_ford到队列优化的Bellman_fordSPFA算法到使用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();ListEdge 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-1for (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
思路
不优化时由于要遍历所有的边所以直接将所有的边存起来就好ListEdge edges new ArrayList();队列优化时需要用邻接表保存图不然每次就要遍历找起点from对应的边了。队列记录“要刷新的节点”该节点需要poll出来处理它所有邻接的节点的minDistboolean[] 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();ListListEdge 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出来处理它所有邻接的节点的minDistDequeInteger 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();ListEdge 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();ListListEdge 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;DequeInteger 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]);}}
}96. 城市间货物运输 III卡码网 其关键在于本题的两个因素 本题可以有负权回路说明只要多做松弛结果是会变的。本题要求最多经过k个节点对松弛次数是有限制的。 方法bellman_ford之单源有限最短路
思路
最多经过k座城市加上start和end就是一共有k2个城市。所以要遍历k1次。
使用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();ListEdge 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就是一共有k2个城市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];// 一共有k2个城市所以要遍历k1遍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();ListListEdge 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就是一共有k2个城市int k in.nextInt();// 原来要遍历n-1次现在有k2个节点所以要遍历k1次k;int[] minDist new int[n 1];Arrays.fill(minDist, Integer.MAX_VALUE);minDist[start] 0;// 用来记录上一轮遍历的结果int[] minDistCopy new int[n 1];DequeInteger 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]);}}
}
