day55 代码随想录算法训练营 图论专题9

1 今日打卡

dijkstra堆优化版 47. 参加科学大会（第六期模拟笔试）

bellman_ford算法 94. 城市间货物运输 I

2 dijkstra堆优化版

2.1 思路

数据结构准备：用邻接表存储图的边信息，用优先队列（小顶堆）快速找到当前距离起点最近的未访问节点，用数组记录起点到各节点的最短距离、访问状态。
初始化：起点到自身的距离设为 0，其余节点初始化为无穷大；优先队列加入起点（距离为 0）。
核心循环：
从优先队列取出当前距离起点最近的节点，标记为已访问。
遍历该节点的所有邻接边，更新邻接节点的最短距离（若通过当前节点到达邻接节点的路径更短）。
把更新后的邻接节点加入优先队列，继续循环直到队列为空。
结果输出：若终点距离仍为无穷大，说明无法到达；否则输出最短距离。

2.2 实现代码

import java.util.*; // 定义边的类：存储邻接顶点和边的权重 class Edge { int to; // 边指向的邻接顶点编号 int val; // 这条边的权重（长度） // 构造方法：初始化边的指向和权重 Edge(int to, int val) { this.to = to; this.val = val; } } // 自定义优先队列的比较器：按Pair的第二个值（距离）升序排列（小顶堆） class MyComparison implements Comparator<Pair<Integer, Integer>> { @Override public int compare(Pair<Integer, Integer> lhs, Pair<Integer, Integer> rhs) { // 比较两个Pair的第二个元素（距离），保证优先队列弹出距离最小的节点 return Integer.compare(lhs.second, rhs.second); } } // 自定义Pair类：存储<节点编号, 起点到该节点的距离> class Pair<U, V> { public final U first; // 第一个元素：节点编号 public final V second; // 第二个元素：起点到该节点的距离 // 构造方法：初始化Pair的两个元素 public Pair(U first, V second) { this.first = first; this.second = second; } } public class Main { public static void main(String[] args) { // 1. 输入处理：读取图的节点数n和边数m Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); // 节点总数（节点编号从1到n） int m = scanner.nextInt(); // 边的总数 // 2. 构建邻接表：存储图的边信息（grid[i]存储节点i的所有出边） List<List<Edge>> grid = new ArrayList<>(n + 1); // 初始化邻接表：节点编号从1开始，所以初始化n+1个空列表 for (int i = 0; i <= n; i++) { grid.add(new ArrayList<>()); } // 3. 读取每条边的信息，填充邻接表 for (int i = 0; i < m; i++) { int p1 = scanner.nextInt(); // 边的起点 int p2 = scanner.nextInt(); // 边的终点 int val = scanner.nextInt();// 边的权重 // 向p1的出边列表中添加一条指向p2、权重为val的边 grid.get(p1).add(new Edge(p2, val)); } // 4. 定义起点和终点：起点固定为1，终点固定为n int start = 1; // 最短路径的起点 int end = n; // 最短路径的终点 // 5. 初始化最短距离数组：minDist[i]表示起点到节点i的最短距离 int[] minDist = new int[n + 1]; // 初始化为无穷大（表示初始时无法到达） Arrays.fill(minDist, Integer.MAX_VALUE); // 6. 初始化访问状态数组：visited[i]为true表示节点i已处理完毕 boolean[] visited = new boolean[n + 1]; // 7. 初始化优先队列：存储<节点编号, 起点到该节点的距离>，按距离升序排列 PriorityQueue<Pair<Integer, Integer>> pq = new PriorityQueue<>(new MyComparison()); // 8. 起点初始化：起点到自身的距离为0，加入优先队列 pq.add(new Pair<>(start, 0)); minDist[start] = 0; // 9. Dijkstra核心循环：处理所有节点 while (!pq.isEmpty()) { // 9.1 取出当前距离起点最近的节点（优先队列顶） Pair<Integer, Integer> cur = pq.poll(); int curNode = cur.first; // 当前节点编号 int curDist = cur.second; // 起点到当前节点的距离 // 9.2 如果该节点已处理过，直接跳过（避免重复处理） if (visited[curNode]) continue; // 9.3 标记该节点为已访问（处理完毕，最短距离已确定） visited[curNode] = true; // 9.4 遍历当前节点的所有出边，更新邻接节点的最短距离 for (Edge edge : grid.get(curNode)) { int nextNode = edge.to; // 邻接节点编号 int edgeVal = edge.val; // 当前边的权重 // 条件：邻接节点未访问 + 起点到当前节点的距离 + 边权重 < 起点到邻接节点的当前最短距离 if (!visited[nextNode] && minDist[curNode] != Integer.MAX_VALUE && minDist[curNode] + edgeVal < minDist[nextNode]) { // 更新邻接节点的最短距离 minDist[nextNode] = minDist[curNode] + edgeVal; // 将更新后的邻接节点加入优先队列（可能重复加入，但不影响，因为已访问的会跳过） pq.add(new Pair<>(nextNode, minDist[nextNode])); } } } // 10. 输出结果 if (minDist[end] == Integer.MAX_VALUE) { // 终点距离仍为无穷大，说明无法到达 System.out.println(-1); } else { // 输出起点到终点的最短距离 System.out.println(minDist[end]); } // 关闭扫描器（规范写法） scanner.close(); } }

3 bell_ford算法

3.1 思路

数据结构准备：用邻接表存储图的边信息，用普通队列（而非优先队列）存储待松弛的节点，用数组记录起点到各节点的最短距离、节点是否在队列中（避免重复入队）。
初始化：起点到自身的距离设为 0，其余节点初始化为无穷大；起点加入队列并标记为 “在队列中”。
核心循环（松弛操作）：
从队列取出节点，取消其 “在队列中” 的标记。
遍历该节点的所有邻接边，若通过当前节点到达邻接节点的路径更短，则更新邻接节点的最短距离。
若邻接节点不在队列中，将其加入队列并标记，继续循环直到队列为空。
结果输出：若终点距离仍为无穷大，说明无法到达；否则输出最短距离。

3.2 实现代码

import java.util.*; public class Main { // 定义边的内部类：存储边的终点和权重 static class Link { int to; // 边指向的邻接节点编号 int val; // 这条边的权重（长度） // 构造方法：初始化边的终点和权重 public Link(int to, int val) { this.to = to; this.val = val; } } public static void main(String[] args) { // 1. 输入处理：读取节点数n和边数m Scanner sc = new Scanner(System.in); int n = sc.nextInt(), m = sc.nextInt(); // n=节点总数（1~n），m=边总数 // 2. 构建邻接表：存储图的边信息（map[i]存储节点i的所有出边） List<List<Link>> map = new ArrayList<>(); // 初始化邻接表：节点编号从1开始，所以初始化n+1个空列表 for (int i = 0; i <= n; i++) { map.add(new ArrayList<>()); } // 3. 读取每条边的信息，填充邻接表 for (int i = 0; i < m; i++) { int from = sc.nextInt(); // 边的起点 int to = sc.nextInt(); // 边的终点 int val = sc.nextInt(); // 边的权重 // 向起点from的出边列表中添加一条指向to、权重为val的边 map.get(from).add(new Link(to, val)); } // 4. 初始化最短距离数组：minDist[i]表示起点(1)到节点i的最短距离 int[] minDist = new int[n + 1]; // 初始化为无穷大（表示初始时无法到达） Arrays.fill(minDist, Integer.MAX_VALUE); minDist[1] = 0; // 起点(1)到自身的距离为0 // 5. 初始化队列标记数组：isInQueue[i]为true表示节点i已在队列中（避免重复入队） boolean[] isInQueue = new boolean[n + 1]; Queue<Integer> que = new LinkedList<>(); // 存储待松弛的节点 que.add(1); // 起点加入队列 isInQueue[1] = true; // 标记起点在队列中 // 6. SPFA核心循环：松弛所有可优化的边 while (!que.isEmpty()) { int cur = que.poll(); // 取出队列头部的节点（当前待处理节点） isInQueue[cur] = false; // 取消该节点的队列标记（允许后续重新入队） // 遍历当前节点的所有出边，进行松弛操作 for (Link link : map.get(cur)) { int to = link.to; // 邻接节点编号 int val = link.val; // 当前边的权重 // 松弛条件：起点到cur的距离 + 边权重 < 起点到to的当前最短距离 // 补充：minDist[cur] != Integer.MAX_VALUE 避免无穷大+数值溢出 if (minDist[cur] != Integer.MAX_VALUE && minDist[cur] + val < minDist[to]) { minDist[to] = minDist[cur] + val; // 更新最短距离 // 若邻接节点不在队列中，加入队列并标记 if (!isInQueue[to]) { que.add(to); isInQueue[to] = true; } } } } // 7. 输出结果 if (minDist[n] == Integer.MAX_VALUE) { // 终点n的距离仍为无穷大，说明无法到达 System.out.println("unconnected"); } else { // 输出起点1到终点n的最短距离 System.out.println(minDist[n]); } sc.close(); // 关闭扫描器（规范写法） } }