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

1 今日打卡dijkstra堆优化版 47. 参加科学大会第六期模拟笔试bellman_ford算法 94. 城市间货物运输 I2 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 ComparatorPairInteger, Integer { Override public int compare(PairInteger, Integer lhs, PairInteger, Integer rhs) { // 比较两个Pair的第二个元素距离保证优先队列弹出距离最小的节点 return Integer.compare(lhs.second, rhs.second); } } // 自定义Pair类存储节点编号, 起点到该节点的距离 class PairU, 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的所有出边 ListListEdge grid new ArrayList(n 1); // 初始化邻接表节点编号从1开始所以初始化n1个空列表 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. 初始化优先队列存储节点编号, 起点到该节点的距离按距离升序排列 PriorityQueuePairInteger, Integer pq new PriorityQueue(new MyComparison()); // 8. 起点初始化起点到自身的距离为0加入优先队列 pq.add(new Pair(start, 0)); minDist[start] 0; // 9. Dijkstra核心循环处理所有节点 while (!pq.isEmpty()) { // 9.1 取出当前距离起点最近的节点优先队列顶 PairInteger, 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~nm边总数 // 2. 构建邻接表存储图的边信息map[i]存储节点i的所有出边 ListListLink map new ArrayList(); // 初始化邻接表节点编号从1开始所以初始化n1个空列表 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]; QueueInteger 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(); // 关闭扫描器规范写法 } }