当前位置: 首页 > ds >正文

Day59--图论--47. 参加科学大会(卡码网),94. 城市间货物运输 I(卡码网)

Day59–图论–47. 参加科学大会(卡码网),94. 城市间货物运输 I(卡码网)

今天学习了dijkstra(堆优化版),比较一下它和昨天的dijkstra(朴素版)优化在了哪里?为什么dijkstra不能计算有负值权重的最短路径?要使用Bellman_ford,它像不像动态规划?

47. 参加科学大会(卡码网)

方法:dijkstra(堆优化版)

思路:

就像Prim和Kruskal一样,一个是针对点,一个是针对边。dijkstra朴素版针对于点,而堆优化版针对于边——所以适用于稀疏图。

  1. 传统三步曲:
    1. 第一步,选源点到哪个节点近且该节点未被访问过
    2. 第二步,该最近节点被标记访问过
    3. 第三步,更新非访问节点到源点的距离(即更新minDist数组)
  2. 改用邻接表存储(定义一个Edge类,每个edge存储指向的节点to和边的权重val。每个节点都拥有一个LinkedList<Edge>来存储自己的邻接表)
  3. 使用int[] minDist数组,存储从源点到每个节点的最短距离。
  4. 新定义一个Pair类,存储两个值,一个是节点,一个是从源点到每个节点的最短距离。其实存的东西和minDist是一样的,本意就如此,用途不同:更新完非访问节点到源点的距离的时候,一边更新minDist,一边组成一个Pair,丢到小顶堆PriorityQueue里面去。
  5. 堆优化三步曲:
    1. 第一步,从小顶堆PriorityQueue取一个源点到目前点距离最小的节点。
    2. 第二步,该最近节点被标记访问过
    3. 第三步,更新非访问节点到源点的距离(即,取该节点的邻接表,对于未访问的邻接元素,更新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]);}}
}
http://www.xdnf.cn/news/18033.html

相关文章:

  • 【DDIA】第二部分:分布式数据
  • 应用层协议——HTTP
  • 抽奖程序web程序
  • JavaScript 基础实战:DOM 操作、数据类型与常见需求实现
  • 项目管理工具
  • NPM 、 NPX
  • 清除 pnpm 缓存,解决不同源安装依赖包失败的问题
  • electron之win/mac通知免打扰
  • 【R语言】R 语言中 gsub 与正则表达式详解(含 POSIX 与 Perl 风格实例)
  • 汽车电子:现代汽车的智能核心
  • [激光原理与应用-287]:理论 - 波动光学 - 电磁波既能承载能量,又能承载信息?
  • 【软件设计模式】前置知识类图、七大原则(精简笔记版)
  • Spark 运行流程核心组件(二)任务调度
  • EN/IEC 55015 照明设备的电磁兼容标准安全
  • Docker Compose部署Clickhouse最新版
  • 【LINUX网络】HTTP协议基本结构、搭建自己的HTTP简单服务器
  • 为什么游戏会出现“卡顿”:`clock.tick()` v.s. `clock.get_fps()`
  • 【uni-app】根据角色/身份切换显示不同的 自定义 tabbar
  • 线性代数 · 直观理解矩阵 | 空间变换 / 特征值 / 特征向量
  • CERT/CC警告:新型HTTP/2漏洞“MadeYouReset“恐致全球服务器遭DDoS攻击瘫痪
  • 机械加工元件——工业精密制造的璀璨明珠
  • Day14: Flask太空站搭建指南:从零到超光速的Web开发之旅
  • git clone https://gh.llkk.cc/
  • C++从入门到实战(十九)C++ vector容器及其常用接口
  • 电子电路学习日记
  • qt项目中解决关闭弹窗后执行主界面的信号槽时闪退问题
  • MySql——聚簇索引(主键索引)和非聚簇索索引(非主键索引)引区别(即聚集索引和非聚集索引区别)
  • Java 学习笔记(基础篇2)
  • Docker build创建镜像命令入门教程
  • **超融合架构中的发散创新:探索现代编程语言的挑战与机遇**一、引言随着数字化时代的快速发展,超融合架构已成为IT领域的一种重要趋势