算法打卡：第十一章图论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])

方法：

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）可以使用优先队列这种数据结构对节点排序，取队头元素就是已排序后的结果

方法：

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，每个点作为终点的最短路径长度都为0
            for (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>{
    @Override
    public int compare(Knight e1,Knight e2){
        return Integer.compare(e1.f,e2.f);
    }

}