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

代码随想录打卡|Day53 图论（Floyd 算法精讲、A * 算法精讲（A star算法）、最短路算法总结篇、图论总结）

ds 2025/8/23 11:36:14

图论part11

Floyd 算法精讲

代码随想录链接
题目链接

在这里插入图片描述

代码

三维DP数组

import java.util.Scanner;public class Main {// 定义最大距离值，避免使用Integer.MAX_VALUE防止加法溢出public static final int INF = 100000000; // 10^8足够大且不会溢出public static void main(String[] args) {Scanner sc = new Scanner(System.in);/* * 1. 输入处理* 第一行：N(景点数量), M(道路数量)* 接下来M行：u, v, w (双向道路)* 然后一行：Q(查询数量)* 接下来Q行：start, end (查询起点和终点)*/int n = sc.nextInt(); // 景点数量 (1到n编号)int m = sc.nextInt(); // 道路数量/** 2. 初始化三维DP数组* dp[k][i][j]表示从i到j，允许经过前k个节点(1..k)的最短路径* 这里k的范围是0到n：* - k=0表示不允许经过任何中间节点(直接边)* - k=n表示允许经过所有节点*/int[][][] dp = new int[n+1][n+1][n+1];// 初始化所有距离为INF，自己到自己的距离为0for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {for (int k = 0; k <= n; k++) {if (i == j) {dp[k][i][j] = 0; // 自己到自己的距离为0} else {dp[k][i][j] = INF; // 初始化为最大值}}}}// 3. 读取道路信息并填充初始距离(k=0的情况)for (int i = 0; i < m; i++) {int u = sc.nextInt();int v = sc.nextInt();int w = sc.nextInt();// 双向道路，两个方向都要设置dp[0][u][v] = w;dp[0][v][u] = w;}/* * 4. Floyd-Warshall算法核心部分(三维DP版本)* 状态转移方程：* dp[k][i][j] = min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j])* 含义：* - 从i到j允许经过前k个节点的最短路径 =*   min(不经过k的最短路径, 经过k的最短路径)*/for (int k = 1; k <= n; k++) {         // 中间节点for (int i = 1; i <= n; i++) {     // 起点for (int j = 1; j <= n; j++) { // 终点// 比较两种情况：// 1. 不经过节点k的最短路径(dp[k-1][i][j])// 2. 经过节点k的最短路径(dp[k-1][i][k] + dp[k-1][k][j])dp[k][i][j] = Math.min(dp[k-1][i][j], dp[k-1][i][k] + dp[k-1][k][j]);}}}// 5. 处理查询int q = sc.nextInt(); // 查询数量for (int i = 0; i < q; i++) {int start = sc.nextInt();int end = sc.nextInt();// 使用允许经过所有节点(n个)的最短路径作为结果// 如果不可达则输出-1System.out.println(dp[n][start][end] == INF ? -1 : dp[n][start][end]);}}
}

二维DP数组

import java.util.Scanner;public class Main {// 定义最大距离值，避免使用Integer.MAX_VALUE防止加法溢出public static final int INF = 100000000; // 10^8足够大且不会溢出public static void main(String[] args) {Scanner sc = new Scanner(System.in);// 1. 读取景点数量和道路数量int n = sc.nextInt(); // 景点数量 (1到n编号)int m = sc.nextInt(); // 道路数量// 2. 初始化距离矩阵int[][] dist = new int[n+1][n+1]; // 1-based索引// 初始化所有距离为INF，自己到自己的距离为0for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {if (i == j) {dist[i][j] = 0;} else {dist[i][j] = INF;}}}// 3. 读取道路信息并填充初始距离for (int i = 0; i < m; i++) {int u = sc.nextInt();int v = sc.nextInt();int w = sc.nextInt();// 双向道路，两个方向都要设置dist[u][v] = w;dist[v][u] = w;}// 4. Floyd-Warshall算法核心部分for (int k = 1; k <= n; k++) {         // 中间节点for (int i = 1; i <= n; i++) {     // 起点for (int j = 1; j <= n; j++) { // 终点// 如果通过中间节点k可以缩短i到j的距离if (dist[i][k] + dist[k][j] < dist[i][j]) {dist[i][j] = dist[i][k] + dist[k][j];}}}}// 5. 处理查询int q = sc.nextInt(); // 查询数量for (int i = 0; i < q; i++) {int start = sc.nextInt();int end = sc.nextInt();// 输出结果，如果不可达则输出-1System.out.println(dist[start][end] == INF ? -1 : dist[start][end]);}}
}

A * 算法精讲（A star算法）

代码随想录链接
题目链接

在这里插入图片描述

代码(超时，示例正确)

import java.util.*;public class Main {// 定义骑士的8种可能移动方式（马走日）private static final int[][] MOVES = {{1, 2}, {2, 1}, {2, -1}, {1, -2},{-1, -2}, {-2, -1}, {-2, 1}, {-1, 2}};// 节点类，表示棋盘上的一个位置static class Node implements Comparable<Node> {int x, y;        // 当前位置坐标int g;           // 从起点到当前节点的实际代价int h;           // 到目标节点的启发式估计代价Node parent;      // 父节点（用于路径回溯）public Node(int x, int y) {this.x = x;this.y = y;this.g = 0;this.h = 0;}// 计算总代价f = g + hpublic int f() {return g + h;}// 用于优先队列排序@Overridepublic int compareTo(Node other) {return Integer.compare(this.f(), other.f());}// 重写equals和hashCode用于比较节点@Overridepublic boolean equals(Object obj) {if (this == obj) return true;if (obj == null || getClass() != obj.getClass()) return false;Node node = (Node) obj;return x == node.x && y == node.y;}@Overridepublic int hashCode() {return Objects.hash(x, y);}}// A*算法实现public static int aStarKnightPath(int startX, int startY, int targetX, int targetY) {// 如果起点就是终点，直接返回0if (startX == targetX && startY == targetY) {return 0;}// 边界检查if (!isValid(startX, startY) || !isValid(targetX, targetY)) {return -1;}// 初始化开放列表和关闭列表PriorityQueue<Node> openList = new PriorityQueue<>();Set<Node> closedList = new HashSet<>();// 创建起点节点Node startNode = new Node(startX, startY);startNode.g = 0;startNode.h = heuristic(startX, startY, targetX, targetY);openList.add(startNode);while (!openList.isEmpty()) {// 获取当前最优节点Node currentNode = openList.poll();// 如果到达目标节点，返回步数if (currentNode.x == targetX && currentNode.y == targetY) {return currentNode.g;}// 将当前节点加入关闭列表closedList.add(currentNode);// 遍历所有可能的移动for (int[] move : MOVES) {int newX = currentNode.x + move[0];int newY = currentNode.y + move[1];// 检查新位置是否有效if (!isValid(newX, newY)) {continue;}// 创建新节点Node neighbor = new Node(newX, newY);neighbor.g = currentNode.g + 1;  // 每步代价为1neighbor.h = heuristic(newX, newY, targetX, targetY);neighbor.parent = currentNode;// 如果已经在关闭列表中，跳过if (closedList.contains(neighbor)) {continue;}// 检查是否在开放列表中boolean inOpenList = false;for (Node node : openList) {if (node.equals(neighbor)) {inOpenList = true;// 如果找到更优路径，更新节点if (neighbor.g < node.g) {node.g = neighbor.g;node.parent = currentNode;}break;}}// 如果不在开放列表中，加入if (!inOpenList) {openList.add(neighbor);}}}// 如果开放列表为空且未找到路径，返回-1return -1;}// 启发式函数：曼哈顿距离除以3（骑士每步最多移动3格）private static int heuristic(int x1, int y1, int x2, int y2) {return (Math.abs(x1 - x2) + Math.abs(y1 - y2)) / 3;}// 检查坐标是否有效private static boolean isValid(int x, int y) {return x >= 1 && x <= 1000 && y >= 1 && y <= 1000;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();for (int i = 0; i < n; i++) {int a1 = sc.nextInt();int a2 = sc.nextInt();int b1 = sc.nextInt();int b2 = sc.nextInt();int steps = aStarKnightPath(a1, a2, b1, b2);System.out.println(steps);}}
}