day60 图论章节刷题Part10（Floyd 算法、A * 算法）

Floyd 算法

思路：本题是多源最短路问题，使用Floyd算法求解。Floyd 算法对边的权值正负没有要求，核心思想是动态规划。
我们使用动规五部曲来理解和应用Floyd算法：

1、确定dp数组（dp table）以及下标的含义
我们用 grid数组来存图，那就把dp数组命名为 grid。grid[i][j][k] = m，表示 节点i 到 节点j 以[1…k] 集合为中间节点的最短距离为m。

2、确定递推公式
分两种情况：
（1）节点i 到 节点j 的最短路径经过节点k：grid[i][j][k] = grid[i][k][k - 1] + grid[k][j][k - 1]
（2）节点i 到 节点j 的最短路径不经过节点k：grid[i][j][k] = grid[i][j][k - 1]
因为求最短路，取两种情况的最小值： grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

3、dp数组初始化
在开始输入边时不经过其他节点，可以把k 赋值为 0，即grid[i][j][0]。同时，本题求的是最小值，grid数组中其他元素数值应该初始为一个最大数。

4、确定遍历顺序
从递推公式：grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1]) 可以看出，我们需要三个for循环，分别遍历i，j 和k。我们把 k =0 的 i 和j 对应的数值都初始化了，再去计算 k = 1 时 i 和 j 对应的数值。这就好比是一个三维坐标，i 和j 是平层，而k 是 垂直向上 的。遍历的顺序是从底向上 一层一层去遍历。所以遍历k 的for循环一定是在最外面。

5、举例推导dp数组

代码如下：

import java.util.*;
public class Main{public static void main (String[] args) {Scanner scan =new Scanner(System.in);int n=scan.nextInt();int m=scan.nextInt();int[][][] grid=new int[n+1][n+1][n+1];for(int i=0;i<=n;i++){for(int j=0;j<=n;j++){Arrays.fill(grid[i][j],Integer.MAX_VALUE);}}//添加边的权重，初始化for(int i=0;i<m;i++){int l=scan.nextInt();int r=scan.nextInt();int val=scan.nextInt();grid[l][r][0]=val;grid[r][l][0]=val;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){if (grid[i][k][k - 1] != Integer.MAX_VALUE && grid[k][j][k - 1] != Integer.MAX_VALUE) {grid[i][j][k] = Math.min(grid[i][k][k - 1] + grid[k][j][k - 1], grid[i][j][k - 1]);} else {grid[i][j][k] = grid[i][j][k - 1];}}}}int num=scan.nextInt();while(num>0){int start=scan.nextInt();int end=scan.nextInt();num--;if(grid[start][end][n]==Integer.MAX_VALUE) System.out.println(-1);else System.out.println(grid[start][end][n]);}}
}

注意：当两个 Integer.MAX_VALUE 值相加时，会导致整数溢出，结果会变成一个非常小的负数，如 -128。

A * 算法（A star算法）

Astar 是一种 广搜或者 dijkstra 的改良版。在搜索最短路的时候， 如果是无权图（边的权值都是1） 那就用广搜，代码简洁，时间效率和 dijkstra 差不多；如果是有权图（边有不同的权值），优先考虑 dijkstra。

Astar 关键在于 启发式函数，也就是影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。BFS 是没有目的性的 一圈一圈去搜索， 而 A * 是有方向性的去搜索，关键在于启发式函数。

由于从队列里取出什么元素，接下来就是从哪里开始搜索。所以启发式函数主要影响队列里元素的排序！对队列里节点进行排序，就需要给每一个节点权值，权值F = G（起点达到目前遍历节点的距离） + H（目前遍历的节点到达终点的距离）

本题的图是无权网格状，在计算两点距离通常有如下三种计算方式：

• 曼哈顿距离，计算方式： d = abs(x1-x2)+abs(y1-y2)
• 欧氏距离（欧拉距离） ，计算方式：d = sqrt( (x1-x2)^2 + (y1-y2)^2 )
• 切比雪夫距离，计算方式：d = max(abs(x1 - x2), abs(y1 - y2))

本题，采用欧拉距离才能最大程度体现 点与点之间的距离。使用欧拉距离计算 和 广搜搜出来的最短路的节点数是一样的。

计算出来 F 之后，按照 F 的 大小选择出队列的节点。可以使用 优先级队列，每次出队列就是F最小的节点。

代码如下：

import java.util.PriorityQueue;
import java.util.Scanner;public class Main {// 定义一个存储移动步数的数组static int[][] moves = new int[1001][1001];// 定义骑士的移动方向static int[][] dir = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};static int b1, b2; // 目标位置// 定义骑士的状态static class Knight implements Comparable<Knight> {int x, y; // 当前坐标int g, h, f; // G, H, F 值@Overridepublic int compareTo(Knight k) { // 重载比较方法，以便优先队列可以排序return Integer.compare(this.f, k.f);}}// 估算函数，使用欧几里得距离的平方static int Heuristic(Knight k) {return (k.x - b1) * (k.x - b1) + (k.y - b2) * (k.y - b2); // 省略开根号以提高精度}// A* 算法实现static void astar(Knight k) {PriorityQueue<Knight> que = new PriorityQueue<>(); // 创建优先队列que.add(k); // 将起始节点加入队列while (!que.isEmpty()) {Knight cur = que.poll(); // 取出队列中优先级最高的节点// 如果到达目标位置，则结束搜索if (cur.x == b1 && cur.y == b2) {break;}// 遍历所有可能的骑士移动for (int i = 0; i < 8; i++) {Knight next = new Knight(); // 创建下一个节点next.x = cur.x + dir[i][0]; // 更新 x 坐标next.y = cur.y + dir[i][1]; // 更新 y 坐标// 检查下一个位置是否在有效范围内if (next.x < 1 || next.x > 1000 || next.y < 1 || next.y > 1000) {continue;}// 检查该位置是否已经访问过if (moves[next.x][next.y] == 0) {moves[next.x][next.y] = moves[cur.x][cur.y] + 1; // 更新步数// 计算 G, H 和 F 值next.g = cur.g + 5; // 统一不开根号以提高精度next.h = Heuristic(next);next.f = next.g + next.h;que.add(next); // 将下一个节点加入队列}}}}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 坐标b1 = scanner.nextInt(); // 目标 x 坐标b2 = scanner.nextInt(); // 目标 y 坐标// 清空步数数组for (int i = 0; i < moves.length; i++) {for (int j = 0; j < moves[i].length; j++) {moves[i][j] = 0;}}// 初始化起始节点Knight start = new Knight();start.x = a1;start.y = a2;start.g = 0;start.h = Heuristic(start);start.f = start.g + start.h;// 执行 A* 算法astar(start);// 输出到达目标位置的步数System.out.println(moves[b1][b2]);}scanner.close(); // 关闭扫描器}
}