Day59--图论--47. 参加科学大会(卡码网),94. 城市间货物运输 I(卡码网)
Day59–图论–47. 参加科学大会(卡码网),94. 城市间货物运输 I(卡码网)
今天学习了dijkstra(堆优化版),比较一下它和昨天的dijkstra(朴素版)优化在了哪里?为什么dijkstra不能计算有负值权重的最短路径?要使用Bellman_ford,它像不像动态规划?
47. 参加科学大会(卡码网)
方法:dijkstra(堆优化版)
思路:
就像Prim和Kruskal一样,一个是针对点,一个是针对边。dijkstra朴素版针对于点,而堆优化版针对于边——所以适用于稀疏图。
- 传统三步曲:
- 第一步,选源点到哪个节点近且该节点未被访问过
- 第二步,该最近节点被标记访问过
- 第三步,更新非访问节点到源点的距离(即更新minDist数组)
- 改用邻接表存储(定义一个Edge类,每个edge存储指向的节点to和边的权重val。每个节点都拥有一个
LinkedList<Edge>
来存储自己的邻接表) - 使用int[] minDist数组,存储从源点到每个节点的最短距离。
- 新定义一个Pair类,存储两个值,一个是节点,一个是从源点到每个节点的最短距离。其实存的东西和minDist是一样的,本意就如此,用途不同:更新完非访问节点到源点的距离的时候,一边更新minDist,一边组成一个Pair,丢到小顶堆PriorityQueue里面去。
- 堆优化三步曲:
- 第一步,从小顶堆PriorityQueue取一个源点到目前点距离最小的节点。
- 第二步,该最近节点被标记访问过
- 第三步,更新非访问节点到源点的距离(即,取该节点的邻接表,对于未访问的邻接元素,更新minDist,并组装一个Pair丢到小顶堆里)
import java.util.*;// 小顶堆的比较器
class HeapComparison implements Comparator<Pair> {@Overridepublic int compare(Pair p1, Pair p2) {return Integer.compare(p1.weight, p2.weight);}
}// 定义一个类来表示键值对
class Pair {int node; // 节点int weight; // 源点到该节点的权值Pair(int node, int weight) {this.node = node;this.weight = weight;}
}// 定义一个类来表示带权重的边
class Edge {int to; // 邻接顶点int val; // 边的权重Edge(int to, int val) { // 构造函数this.to = to;this.val = val;}
}public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n = in.nextInt();int m = in.nextInt();List<List<Edge>> grid = new ArrayList<>();for (int i = 0; i <= n; i++) {grid.add(new LinkedList<>());}for (int i = 0; i < m; i++) {int p1 = in.nextInt();int p2 = in.nextInt();int val = in.nextInt();// p1 指向 p2,权值为 valgrid.get(p1).add(new Edge(p2, val));}int start = 1; // 起点int end = n; // 终点// 存储从源点到每个节点的最短距离int[] minDist = new int[n + 1];Arrays.fill(minDist, Integer.MAX_VALUE);// 记录顶点是否被访问过boolean[] visited = new boolean[n + 1];// 优先队列中存放 Pair<节点,源点到该节点的权值>PriorityQueue<Pair> pq = new PriorityQueue<>(new HeapComparison());// 初始化队列,源点到源点的距离为0pq.add(new Pair(start, 0));minDist[start] = 0; // 起始点到自身的距离为0while (!pq.isEmpty()) {// 1. 第一步,选源点到哪个节点近且该节点未被访问过 (通过优先级队列来实现)// Pair <节点, 源点到该节点的距离>Pair p = pq.poll();int cur = p.node;if (visited[cur]) continue;// 2. 第二步,该最近节点被标记访问过visited[cur] = true;// 3. 第三步,更新非访问节点到源点的距离(即更新minDist数组)for (Edge edge : grid.get(cur)) { // 遍历 cur指向的节点// cur指向的节点edge.to,这条边的权值为 edge.valif (!visited[edge.to]&& minDist[cur] != Integer.MAX_VALUE&& minDist[cur] + edge.val < minDist[edge.to]) { // 更新minDistminDist[edge.to] = minDist[cur] + edge.val;pq.add(new Pair(edge.to, minDist[edge.to]));}}}if (minDist[end] == Integer.MAX_VALUE) {System.out.println(-1); // 不能到达终点} else {System.out.println(minDist[end]); // 到达终点最短路径}}
}
94. 城市间货物运输 I(卡码网)
Bellman_ford算法的核心思想是 对所有边进行松弛n-1次操作(n为节点数量),从而求得目标最短路。
其实 Bellman_ford算法 也是采用了动态规划的思想,即:将一个问题分解成多个决策阶段,通过状态之间的递归关系最后计算出全局最优解。
Bellman_ford 是可以计算 负权值的单源最短路算法。
其算法核心思路是对 所有边进行 n-1 次 松弛。
方法:Bellman_ford
思路:
其实松弛操作,就是进行“动态规划”。因为每更新一个节点的状态,都会影响其它节点。
所以每更新一个节点,就需要对全部节点的状态进行更新。(n个节点,更新n-1一次就够了)
核心代码:minDist[B] = min(minDist[A] + value, minDist[B])
也就是说,如果 通过 A 到 B 这条边可以获得更短的到达B节点的路径,即如果 minDist[B] > minDist[A] + value
,那么我们就更新 minDist[B] = minDist[A] + value
,这个过程就叫做 “松弛” 。
import java.util.*;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 class Main {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) {// 松弛操作// minDist[from] != Integer.MAX_VALUE 防止从未计算过的节点出发if (minDist[e.from] != Integer.MAX_VALUE) {// 动态规划,更新e.to这个节点的minDistminDist[e.to] = Math.min(minDist[e.to], minDist[e.from] + e.val);}}}// 不能到达终点if (minDist[end] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {// 到达终点最短路径(运输成本最小)System.out.println(minDist[end]);}}
}