算法打卡：第十一章图论part11

今日收获：Floyd 算法，A * 算法，最短路算法总结

1. Floyd 算法

题目链接：97. 小明逛公园

思路：Floyd用于解决多源最短路问题，对边的正负权值没有要求。核心是动态规划

（1）dp数组的定义：grid[i][j][k] = m，表示节点i 到节点j 以中间节点[1...k] 集合的最短距离为m

（2）初始化：刚开始从 i 到 j 没有经过任何中间节点，所以 k 初始化为0

（3）遍历顺序：算法相当于不断把新的节点加入，计算起点到终点的最短距离，所以外层遍历 k，里面遍历 i 和 j

（4）递推公式：分为经过/不经过 k 节点，两者取较小值。grid[i][j][k] = min(grid[i][k][k - 1] + grid[k][j][k - 1]， grid[i][j][k - 1])

方法：

java">import java.util.*;public class Main{public static void main(String[] args){Scanner sc=new Scanner(System.in);int N=sc.nextInt();int M=sc.nextInt();int[][][] grid=new int[N+1][N+1][N+1];// 初始化动态规划数组for (int i=0;i<N+1;i++){for (int j=0;j<N+1;j++){for (int k=0;k<N+1;k++){grid[i][j][k]=10005;}}}// 接收数据for (int i=0;i<M;i++){int u=sc.nextInt();int v=sc.nextInt();int w=sc.nextInt();grid[u][v][0]=w;  // 双向图grid[v][u][0]=w;}for (int k=1;k<N+1;k++){for (int i=1;i<N+1;i++){for (int j=1;j<N+1;j++){// 不经过k点和经过k点grid[i][j][k]=Math.min(grid[i][j][k-1],grid[i][k][k-1]+grid[k][j][k-1]);}}}int Q=sc.nextInt();while (Q>0){int start=sc.nextInt();int end=sc.nextInt();if (grid[start][end][N]!=10005){System.out.println(grid[start][end][N]);}else {System.out.println(-1);}Q--;}}
}

2. A * 算法

题目链接：127. 骑士的攻击

思路：是广度优先搜索的改良版，影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。

（1）BFS 是没有目的性的一圈一圈去搜索，而 A * 是有方向性的去搜索。

（2）找方向的关键是启发式函数，通过影响队列中节点的排序确定方向

（3）队列中节点排序的依据：每个节点的权值为F（起点经过当前节点到达终点的距离），公式为：F = G + H

G：起点达到目前遍历节点的距离
F：目前遍历的节点到达终点的距离

（4）可以使用优先队列这种数据结构对节点排序，取队头元素就是已排序后的结果

方法：

java">import java.util.*;public class Main{static int[][] moves=new int[1001][1001];  // 记录某个起点到（x,y）的最短路径距离static int b1;  // 终点static int b2;static int[][] dir={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};  // 8个方向public static void main(String[] args){Scanner sc=new Scanner(System.in);int n=sc.nextInt();while (n-->0){int a1=sc.nextInt();int a2=sc.nextInt();b1=sc.nextInt();b2=sc.nextInt();// moves数组初始化为0，每个点作为终点的最短路径长度都为0for (int i=0;i<1001;i++){for (int j=0;j<1001;j++){moves[i][j]=0;}}// 起点的骑士Knight start=new Knight(a1,a2,0,distance(a1,a2));aStar(start);System.out.println(moves[b1][b2]);}}// 广度优先遍历public static void aStar(Knight start){PriorityQueue<Knight> queue=new PriorityQueue<>(new MyComparison());queue.add(start);while (!queue.isEmpty()){Knight cur=queue.poll();  // 当前离终点最近方向的节点if (cur.x==b1&&cur.y==b2){  // 走到了终点break;}for (int i=0;i<8;i++){int nextX=cur.x+dir[i][0];int nextY=cur.y+dir[i][1];if (nextX<=0||nextY<=0||nextX>=1001||nextY>=1001){continue;}// 没有被访问过if (moves[nextX][nextY]==0){moves[nextX][nextY]=moves[cur.x][cur.y]+1;// 添加节点,马走日queue.offer(new Knight(nextX,nextY,cur.g+5,distance(nextX,nextY)));}}}}// 计算当前坐标到终点的欧氏距离public static int distance(int x,int y){return (x-b1)*(x-b1)+(y-b2)*(y-b2);}
}class Knight{int x;  // 骑士当前所处位置的坐标int y;int g;  // 计算权值int h;int 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;}
}// 根据权值排序
class MyComparison implements Comparator<Knight>{@Overridepublic int compare(Knight e1,Knight e2){return Integer.compare(e1.f,e2.f);}}