Day52 | dijkstra（堆优化版）Bellman_ford 算法
dijkstra（堆优化版）
题目
47. 参加科学大会
47. 参加科学大会（第六期模拟笔试）
题目描述
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。
小明的起点是第一个车站，终点是最后一个车站。然而，途中的各个车站之间的道路状况、交通拥堵程度以及可能的自然因素（如天气变化）等不同，这些因素都会影响每条路径的通行时间。
小明希望能选择一条花费时间最少的路线，以确保他能够尽快到达目的地。
输入描述
第一行包含两个正整数，第一个正整数 N 表示一共有 N 个公共汽车站，第二个正整数 M 表示有 M 条公路。
接下来为 M 行，每行包括三个整数，S、E 和 V，代表了从 S 车站可以单向直达 E 车站，并且需要花费 V 单位的时间。
输出描述
输出一个整数，代表小明从起点到终点所花费的最小时间。
思路
- 初始化一个网格
grid来存储各个节点之间的距离，初始值设为Integer.MAX_VALUE表示不可达。 - 读取输入来填充网格中的实际距离。
- 创建两个数组
minDist和visited分别用来记录从起始点到每个节点的最短距离以及节点是否已经被访问。 - 使用循环遍历所有的节点，每次选择一个距离起点最近且未被访问过的节点。
- 更新其他未访问节点的最短距离，如果通过当前节点可以达到更短的距离，则更新这个距离。
- 输出从起点到终点的最短距离，如果不可达则输出
-1。
代码
import java.util.*;class Edge {int to; // 邻接顶点int val; // 边的权重Edge(int to, int val) {this.to = to;this.val = val;}
}class MyComparison implements Comparator<Pair<Integer, Integer>> {@Overridepublic int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) {return Integer.compare(lhs.second, rhs.second);}
}class Pair<U, V> {public final U first;public final V second;public Pair(U first, V second) {this.first = first;this.second = second;}
}public class Main {public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();List<List<Edge>> grid = new ArrayList<>(n + 1);for (int i = 0; i <= n; i++) {grid.add(new ArrayList<>());}for (int i = 0; i < m; i++) {int p1 = scanner.nextInt();int p2 = scanner.nextInt();int val = scanner.nextInt();grid.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<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison());// 初始化队列，源点到源点的距离为0，所以初始为0pq.add(new Pair<>(start, 0));minDist[start] = 0; // 起始点到自身的距离为0while (!pq.isEmpty()) {// 1. 第一步，选源点到哪个节点近且该节点未被访问过（通过优先级队列来实现）// <节点， 源点到该节点的距离>Pair<Integer, Integer> cur = pq.poll();if (visited[cur.first]) continue;// 2. 第二步，该最近节点被标记访问过visited[cur.first] = true;// 3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）for (Edge edge : grid.get(cur.first)) { // 遍历 cur指向的节点，cur指向的节点为 edge// cur指向的节点edge.to，这条边的权值为 edge.valif (!visited[edge.to] && minDist[cur.first] + edge.val < minDist[edge.to]) { // 更新minDistminDist[edge.to] = minDist[cur.first] + 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]); // 到达终点最短路径}}
}易错点
如果起始点和结束点相同，或者图中没有直接或间接连接起始点和结束点的路径，那么 minDist[end] 将保持为 Integer.MAX_VALUE，这是正确的行为。但是，在实际应用中需要注意边界情况，例如输入数据的有效性验证。
Bellman_ford 算法
题目
城市间货物运输 I
94. 城市间货物运输 I
思路
-
定义 Edge 类：创建一个内部类
Edge来表示图中的每条边，包含起点from、终点to和边的权重val。 -
输入处理：从标准输入读取节点数
n和边数m，然后读取每条边的信息并将其存储在List<Edge>中。 -
初始化距离数组：创建一个数组
minDist来存储从起始节点（默认为 1）到每个节点的最短距离。所有节点的初始距离都设为Integer.MAX_VALUE，除了起始节点设为 0。 -
松弛操作：执行
n - 1次松弛操作来更新minDist数组。每次迭代都会遍历所有边，并尝试通过每条边来减少到达目标节点的距离。 -
结果输出：最后检查
minDist[n]是否仍然为Integer.MAX_VALUE，如果是，则表示不存在从起始节点到目标节点的路径；否则输出最短路径长度。
代码
import java.util.*;
public class Main {// Define an inner class Edgestatic 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) {// Input processingScanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();List<Edge> edges = new ArrayList<>();for (int i = 0; i < m; i++) {int from = sc.nextInt();int to = sc.nextInt();int val = sc.nextInt();edges.add(new Edge(from, to, val));}// Represents the minimum distance from the current node to the original nodeint[] minDist = new int[n + 1];// Initialize the minDist arrayArrays.fill(minDist, Integer.MAX_VALUE);minDist[1] = 0;// Starts the loop to relax all edges n - 1 times to update minDist arrayfor (int i = 1; i < n; i++) {for (Edge edge : edges) {// Updates the minDist arrayif (minDist[edge.from] != Integer.MAX_VALUE && (minDist[edge.from] + edge.val) < minDist[edge.to]) {minDist[edge.to] = minDist[edge.from] + edge.val;}}}// Outcome printingif (minDist[n] == Integer.MAX_VALUE) {System.out.println("unconnected");} else {System.out.println(minDist[n]);}}
}易错点
代码假设起始节点总是 1，但在实际应用中，起始节点可能是任意一个节点。如果输入指定起始节点，需要相应修改代码
总结
算法真是一个坚持的过程
继续加油！