day58 代码随想录算法训练营 图论专题11

1 今日打卡Floyd算法 97. 小明逛公园A*算法 127. 骑士的攻击2 Floyd算法2.1 思路核心原理对于任意两个节点 i 和 j尝试以节点 k 作为中间节点更新 i 到 j 的最短路径即 i - j 的最短路径 min (原 i-j 路径i-k-j 路径)。三层循环逻辑外层循环 k枚举所有可能的中间节点从 1 到 n中层循环 i枚举所有起点内层循环 j枚举所有终点初始化自身到自身的距离为 0代码中未显式写但可补充直接相连的节点距离为输入的边权无直接相连的节点距离设为一个极大值表示不可达。2.2 实现代码import java.util.*; public class Main { public static void main(String[] args) { // 1. 输入处理读取节点数n和边数m Scanner sc new Scanner(System.in); int n sc.nextInt(), m sc.nextInt(); // n节点总数m边的数量 // 2. 初始化三维数组grid[i][j][k] 表示经过前k个中间节点后i到j的最短路径 // 维度说明i(起点)、j(终点)、k(中间节点上限)范围1~n方便节点编号对应 int[][][] grid new int[n 1][n 1][n 1]; for (int i 0; i n; i) { for (int j 0; j n; j) { // 初始化所有路径为极大值10001需大于可能的最大路径和表示初始不可达 Arrays.fill(grid[i][j], 10001); // 补充自身到自身的距离为0原代码遗漏建议添加 if (i j) { grid[i][j][0] 0; } } } // 3. 读取边的信息初始化直接相连的节点路径k0表示无中间节点 for (int i 0; i m; i) { int src sc.nextInt(); // 起点 int dst sc.nextInt(); // 终点 int val sc.nextInt(); // 边权路径长度 // 无向图双向路径都要赋值 grid[src][dst][0] val; grid[dst][src][0] val; } // 4. Floyd核心动态规划更新最短路径 // k枚举中间节点第k个中间节点 for (int k 1; k n; k) { // i枚举所有起点 for (int i 1; i n; i) { // j枚举所有终点 for (int j 1; j n; j) { // 状态转移方程 // 经过前k个中间节点的i-j路径 min(不经过k的路径, 经过k的路径(i-k k-j)) grid[i][j][k] Math.min(grid[i][j][k - 1], grid[i][k][k - 1] grid[k][j][k - 1]); } } } // 5. 处理查询输出指定起点到终点的最短路径 int q sc.nextInt(); // 查询次数 while (q 0) { int start sc.nextInt(); // 查询的起点 int end sc.nextInt(); // 查询的终点 // grid[start][end][n] 表示经过所有n个中间节点后start到end的最短路径 if (grid[start][end][n] 10001) { System.out.println(-1); // 不可达输出-1 } else { System.out.println(grid[start][end][n]); // 输出最短路径长度 } q--; } sc.close(); // 关闭输入流 } }3 A*算法3.1 思路A*A-Star算法是一种启发式搜索算法核心是结合「实际代价G」和「预估代价H」来引导搜索方向相比普通 BFS 能更快找到最优路径适用于最短路径问题如本题的骑士走棋盘核心公式F G HG从起点到当前节点的实际移动代价本题中骑士每走一步G 增加 5对应 “马走日” 的欧氏距离平方12225H从当前节点到终点的预估代价启发函数本题用欧氏距离平方避免开根号提升计算效率F总代价算法优先选择 F 最小的节点扩展能快速逼近终点。核心流程用优先队列最小堆存储待扩展的节点按 F 值从小到大排序每次取出 F 最小的节点扩展其所有合法邻接节点骑士的 8 种走法记录每个节点的实际移动步数直到找到终点。3.2 实现代码import java.util.PriorityQueue; import java.util.Arrays; import java.util.Scanner; // 骑士节点类存储坐标、G/H/F值 class Knight implements ComparableKnight { int x, y; // 坐标 int g, h, f;// G(实际代价)、H(预估代价)、F(总代价) // 构造方法 public Knight(int x, int y, int g, int h) { this.x x; this.y y; this.g g; this.h h; this.f g h; // F G H } // 重写比较器优先队列按F值升序排列F小的先出队 Override public int compareTo(Knight other) { return Integer.compare(this.f, other.f); } } public class Main { // 骑士的8个移动方向马走日 private static final int[][] dir {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}}; // 记录每个位置的移动步数初始为0表示未访问 private static int[][] moves; // 终点坐标全局变量方便启发函数调用 private static int targetX, targetY; // 启发函数计算当前节点到终点的欧氏距离平方不开根号提升效率 private static int heuristic(int x, int y) { int dx x - targetX; int dy y - targetY; return dx * dx dy * dy; } // A* 核心搜索方法 private static void aStar(int startX, int startY) { // 初始化优先队列最小堆按F值升序排列 PriorityQueueKnight queue new PriorityQueue(); // 起点入队G0无移动代价H为起点到终点的预估代价 queue.add(new Knight(startX, startY, 0, heuristic(startX, startY))); // 起点步数记为0 moves[startX][startY] 0; // 开始搜索 while (!queue.isEmpty()) { // 取出F值最小的节点当前最优节点 Knight cur queue.poll(); int curX cur.x; int curY cur.y; // 到达终点直接退出A*找到的第一条路径就是最短路径 if (curX targetX curY targetY) { return; } // 遍历8个移动方向 for (int[] d : dir) { int nextX curX d[0]; int nextY curY d[1]; // 边界检查棋盘范围1~1000 if (nextX 1 || nextX 1000 || nextY 1 || nextY 1000) { continue; } // 未访问过的节点moves为0表示未访问 if (moves[nextX][nextY] 0) { // 记录步数当前步数1每走一步步数1 moves[nextX][nextY] moves[curX][curY] 1; // 计算新节点的G、H、FG当前G5马走日的距离平方 int newG cur.g 5; int newH heuristic(nextX, nextY); // 新节点入队 queue.add(new Knight(nextX, nextY, newG, newH)); } } } } public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); // 测试用例数 while (n-- 0) { int a1 scanner.nextInt(); // 起点x int a2 scanner.nextInt(); // 起点y targetX scanner.nextInt();// 终点x targetY scanner.nextInt();// 终点y // 初始化步数数组1001*1001适配1~1000的坐标每次用例重置 moves new int[1001][1001]; // 若起点终点直接输出0避免不必要的搜索 if (a1 targetX a2 targetY) { System.out.println(0); continue; } // 执行A*搜索 aStar(a1, a2); // 输出终点的步数 System.out.println(moves[targetX][targetY]); } scanner.close(); } }