最短路问题刷题笔记

dijkstra 朴素版#

dijkstra 算法：在有权图（权值非负数）中求从起点到其他节点的最短路径算法。

dijkstra 算法可以同时求起点到所有节点的最短路径
权值不能为负数

在 dijkstra 算法中，使用一个minDist 数组用来记录每一个节点距离源点的最小距离。

dijkstra 三部曲

第一步，选源点到哪个节点近且该节点未被访问过
第二步，该最近节点被标记访问过
第三步，更新非访问节点到源点的距离（即更新 minDist 数组）

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt(); // 节点数
        int M = input.nextInt(); // 边数

        // 记录有向图中边的权值
        int[][] grid = new int[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                grid[i][j] = Integer.MAX_VALUE;
            }
        }
        for (int i = 0; i < M; i++) {
            int S = input.nextInt();
            int E = input.nextInt();
            int V = input.nextInt();
            grid[S - 1][E - 1] = V;
        }
        input.close();

        // 记录起点到所有节点的路径的最短长度
        int[] minDist = new int[N];
        for (int i = 0; i < N; i++) {
            minDist[i] = Integer.MAX_VALUE;
        }
        minDist[0] = 0; // 起点距离初始化为0

        // 记录一个节点是否被选择(访问)过了
        boolean[] visited = new boolean[N];

        // 三部曲 N 次，确保计算出最短距离
        for (int i = 0; i < N; i++) {

            int min = Integer.MAX_VALUE;
            int cur = 0;

            // 选择距离起点最近且未访问过的节点
            for (int j = 0; j < N; j++) {
                if (visited[j] == false && minDist[j] < min) {
                    min = minDist[j];
                    cur = j;
                }
            }

            // 标记这个节点为已访问
            visited[cur] = true;

            // 更新minDist数组的值
            for (int j = 0; j < N; j++) {
                if (visited[j] == false && grid[cur][j] != Integer.MAX_VALUE && minDist[j] > grid[cur][j] + min) {
                    minDist[j] = grid[cur][j] + min;
                }
            }
        }

        if (minDist[N - 1] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(minDist[N - 1]);
        }
    }
}

时间复杂度：O (n^2)

dijkstra 堆优化版#

朴素版的 dijkstra 时间复杂度为 O (n^2)，只和 n （节点数量）有关系。

如果 n 很大的话，可以换一个角度来优先性能，从边的数量出发。

和朴素版 dijkstra 的主要区别是两点：

邻接表的表示方式不同
使用优先级队列（小顶堆）来对新链接的边排序

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

class Edge {
    int to, weight;

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

class Pair {
    int node, dist;

    Pair(int node, int dist) {
        this.node = node;
        this.dist = dist;
    }
}

class MyComparison implements Comparator<Pair> {
    @Override
    public int compare(Pair lhs, Pair rhs) {
        return Integer.compare(lhs.dist, rhs.dist);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt(); // 节点数
        int M = input.nextInt(); // 边数

        // 邻接表记录有向图中边的权值
        List<List<Edge>> grid = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            grid.add(new ArrayList<>());
        }
        for (int i = 0; i < M; i++) {
            int S = input.nextInt();
            int E = input.nextInt();
            int V = input.nextInt();
            grid.get(S - 1).add(new Edge(E - 1, V));
        }
        input.close();

        // 记录起点到所有节点的路径的最短长度
        int[] minDist = new int[N];
        for (int i = 0; i < N; i++) {
            minDist[i] = Integer.MAX_VALUE;
        }
        minDist[0] = 0; // 起点距离初始化为0

        // 记录一个节点是否被选择(访问)过了
        boolean[] visited = new boolean[N];

        // 初始化优先级队列(小顶堆)，<节点， 该节点到起点的距离>
        PriorityQueue<Pair> pq = new PriorityQueue<>(new MyComparison());
        pq.add(new Pair(0, 0));

        // 遍历边
        while (!pq.isEmpty()) {

            // 选择距离起点最近且未访问过的节点，优先级队列实现
            Pair cur = pq.poll();

            // 标记这个节点为已访问
            visited[cur.node] = true;

            // 更新minDist数组的值，遍历cur指向的节点和边
            for (Edge edge : grid.get(cur.node)) {
                if (visited[edge.to] == false && minDist[edge.to] > minDist[cur.node] + edge.weight) {
                    minDist[edge.to] = minDist[cur.node] + edge.weight;
                    pq.add(new Pair(edge.to, minDist[edge.to])); // 类似于广搜或层序遍历
                }
            }
        }

        if (minDist[N - 1] == Integer.MAX_VALUE) {
            System.out.println(-1);
        } else {
            System.out.println(minDist[N - 1]);
        }
    }
}

注意，如果使用 lamda 表达式来进行排序的话会超时。

时间复杂度：O (E * (N + logE)) E 为边的数量，N 为节点数量

while (!pq.empty()) 时间复杂度为 E ，while 里面每次取元素时间复杂度为 logE，和一个 for 循环时间复杂度为 N 。

总的来说，dijkstra 算法是一种贪心的策略，每一次选择距离最近的一个节点来更新最短距离，其堆优化版本又带有广度优先搜索的影子。

Bellman_ford#

本题是经典的带负权值的单源最短路问题，可以使用 Bellman_ford 算法解决这类问题。

Bellman_ford 算法的核心思想是对所有边进行松弛 n-1 次操作（n 为节点数量），从而求得目标最短路。

如果通过 A 到 B 这条边可以获得更短的到达 B 节点的路径，即如果 minDist[B] > minDist[A] + value，那么我们就更新 minDist[B] = minDist[A] + value ，这个过程就叫做 “松弛” 。

（其实 Bellman_ford 算法采用了动态规划的思想，即：将一个问题分解成多个决策阶段，通过状态之间的递归关系最后计算出全局最优解。）

对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。对所有边松弛两次可以得到与起点两条边相连的节点的最短距离......

节点数量为 n，那么起点到终点，最多是 n-1 条边相连。那么无论图是什么样的，边是什么样的顺序，我们对所有边松弛 n-1 次就一定能得到起点到达终点的最短距离。同时计算出了，起点到达所有节点的最短距离。

import java.util.*;;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 节点数
        int m = input.nextInt(); // 边数

        // edges存放所有边
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            int s = input.nextInt() - 1;
            int t = input.nextInt() - 1;
            int v = input.nextInt();
            edges[i] = new int[] { s, t, v };
        }
        input.close();

        // minDist存放所有节点到起点的最小权值
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0; // 起点

        // 对所有边进行n-1次松弛
        for (int i = 0; i < n - 1; i++) {
            // 遍历所有边
            for (int j = 0; j < m; j++) {
                int from = edges[j][0];
                int to = edges[j][1];
                int value = edges[j][2];
                if (minDist[from] == Integer.MAX_VALUE) {
                    continue;
                }
                minDist[to] = Math.min(minDist[to], minDist[from] + value);
            }
        }

        if (minDist[n - 1] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            System.out.println(minDist[n - 1]);
        }

    }
}

时间复杂度： O (N * E) , N 为节点数量，E 为图中边的数量

Bellman_ford 队列优化算法 (SPFA)#

Bellman_ford 算法每次都是对所有边进行松弛，其实是多做了一些无用功。只需要对上一次松弛的时候更新过的节点作为出发节点所连接的边进行松弛就够了。

用队列来记录上次松弛的时候更新过的节点。

要知道一个节点作为出发点连接了哪些节点，需要使用邻接表来存储这个图。

import java.util.*;;

class Edge {
    int to, weight;

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 节点数
        int m = input.nextInt(); // 边数

        // 邻接表存放所有边
        List<List<Edge>> grid = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            grid.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int s = input.nextInt() - 1;
            int t = input.nextInt() - 1;
            int v = input.nextInt();
            grid.get(s).add(new Edge(t, v));
        }
        input.close();

        // minDist存放所有节点到起点的最小权值
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0; // 起点

        // 用队列记录上一次被更新的节点
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);

        // visited记录在队列中的元素
        boolean[] visited = new boolean[n];
        visited[0] = true;

        // 对队列中所有节点出发的所有边进行松弛
        while (!queue.isEmpty()) {
            int from = queue.poll();
            visited[from] = false;
            for (Edge edge : grid.get(from)) {
                // 开始松弛
                if (minDist[from] + edge.weight < minDist[edge.to]) {
                    minDist[edge.to] = minDist[from] + edge.weight;
                    if (visited[edge.to] == false) {
                        queue.offer(edge.to);
                        visited[edge.to] = true;
                    }
                }
            }
        }

        if (minDist[n - 1] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            System.out.println(minDist[n - 1]);
        }

    }
}

一般来说，SPFA 的时间复杂度为 O (K * N) K 为不定值，因为节点需要计入几次队列取决于图的稠密度。在最坏的情况下是 O (N * E)

Bellman_ford 之判断负权回路#

负权回路，也就是图中出现环且环上的边总权值为负数的情况。

如果在这样的图中求最短路的话，就会在这个环里无限循环（也是负数 + 负数只会越来越小），无法求出最短路径。所以对于在有负权值的图中求最短路，都需要先看看这个图里有没有负权回路。

在 bellman_ford 算法中，松弛 n-1 次所有的边就可以求得起点到任何节点的最短路径，松弛 n 次以上，minDist 数组（记录起到到其他节点的最短距离）中的结果也不会有改变。

而有负权回路的情况下，一直都会有更短的最短路，所以松弛第 n 次，minDist 数组也会发生改变。

所以，只需要多松弛一次，看 minDist 数组是否发生变化。

import java.util.*;;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 节点数
        int m = input.nextInt(); // 边数

        // edges存放所有边
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            int s = input.nextInt() - 1;
            int t = input.nextInt() - 1;
            int v = input.nextInt();
            edges[i] = new int[] { s, t, v };
        }
        input.close();

        // minDist存放所有节点到起点的最小权值
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0; // 起点

        // 用于记录第n次松弛minDist是否发生变化
        boolean flag = false;

        // 对所有边进行n次松弛
        for (int i = 0; i < n; i++) {
            // 遍历所有边
            for (int j = 0; j < m; j++) {
                int from = edges[j][0];
                int to = edges[j][1];
                int value = edges[j][2];
                if (minDist[from] == Integer.MAX_VALUE) {
                    continue;
                }
                if (minDist[to] > minDist[from] + value) {
                    if (i < n - 1) {
                        minDist[to] = minDist[from] + value;
                    } else {
                        flag = true;
                    }
                }
            }
        }
        if (flag == true) {
            System.out.println("circle");
            return;
        }
        if (minDist[n - 1] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            System.out.println(minDist[n - 1]);
        }

    }
}

也可以使用队列优化版的 bellman_ford（SPFA）

在极端情况下，即：所有节点都与其他节点相连，每个节点的入度为 n-1 （n 为节点数量），所以每个节点最多加入 n-1 次队列。

如果节点加入队列的次数超过了 n-1 次，那么该图就一定有负权回路。

import java.util.*;;

class Edge {
    int to, weight;

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 节点数
        int m = input.nextInt(); // 边数

        // 邻接表存放所有边
        List<List<Edge>> grid = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            grid.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int s = input.nextInt() - 1;
            int t = input.nextInt() - 1;
            int v = input.nextInt();
            grid.get(s).add(new Edge(t, v));
        }
        input.close();

        // minDist存放所有节点到起点的最小权值
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[0] = 0; // 起点

        // 用队列记录上一次被更新的节点
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(0);

        // visited记录在队列中的元素
        boolean[] visited = new boolean[n];
        visited[0] = true;

        // count记录所有节点的入队次数
        int[] count = new int[n];
        count[0]++;

        // 对队列中所有节点出发的所有边进行松弛
        while (!queue.isEmpty()) {
            int from = queue.poll();
            visited[from] = false;
            for (Edge edge : grid.get(from)) {
                // 开始松弛
                if (minDist[from] + edge.weight < minDist[edge.to]) {
                    minDist[edge.to] = minDist[from] + edge.weight;
                    if (visited[edge.to] == false) {
                        queue.offer(edge.to);
                        visited[edge.to] = true;
                        if (count[edge.to]++ == n) {
                            System.out.println("circle");
                            return;
                        }
                    }
                }
            }
        }

        if (minDist[n - 1] == Integer.MAX_VALUE) {
            System.out.println("unconnected");
        } else {
            System.out.println(minDist[n - 1]);
        }

    }
}

Bellman_ford 之单源有限最短路#

回顾 Bellman_ford 算法：

对所有边松弛一次，相当于计算起点到达与起点一条边相连的节点的最短距离。
节点数量为 n，起点到终点，最多是 n-1 条边相连。那么对所有边松弛 n-1 次就一定能得到起点到达终点的最短距离。

若最多经过 k 个城市，那么是 k + 1 条边相连的节点。也就是求：起点最多经过 k + 1 条边到达终点的最短距离。对所有边松弛 k + 1 次即可。

import java.util.*;;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 节点数
        int m = input.nextInt(); // 边数

        // edges存放所有边
        int[][] edges = new int[m][3];
        for (int i = 0; i < m; i++) {
            int s = input.nextInt() - 1;
            int t = input.nextInt() - 1;
            int v = input.nextInt();
            edges[i] = new int[] { s, t, v };
        }

        int src = input.nextInt() - 1;
        int dst = input.nextInt() - 1;
        int k = input.nextInt();
        input.close();

        // minDist存放所有节点到起点的最小权值
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[src] = 0; // 起点

        // 用于记录上一次松弛后minDist的数值
        int[] minDist_copy = new int[n];

        // 对所有边进行k+1次松弛
        for (int i = 0; i < k + 1; i++) {
            for (int j = 0; j < n; j++) {
                minDist_copy[j] = minDist[j];
            }
            // 遍历所有边
            for (int j = 0; j < m; j++) {
                int from = edges[j][0];
                int to = edges[j][1];
                int value = edges[j][2];
                if (minDist_copy[from] == Integer.MAX_VALUE) {
                    continue;
                }
                minDist[to] = Math.min(minDist[to], minDist_copy[from] + value);
            }
        }

        if (minDist[dst] == Integer.MAX_VALUE) {
            System.out.println("unreachable");
        } else {
            System.out.println(minDist[dst]);
        }

    }
}

时间复杂度： O (K * E) , K 为至多经过 K 个节点，E 为图中边的数量

由于负权回路、边的顺序等的影响，可能会造成计算 minDist 数组的时候，基于了本次松弛的 minDist 数值，而不是上一次松弛时候 minDist 的数值。

所以在每次计算 minDist 时候，要基于对所有边上一次松弛的 minDist 数值才行，所以要记录上一次松弛的 minDist。

本题可以有负权回路，说明只要多做松弛，结果是会变的。
本题要求最多经过 k 个节点，对松弛次数是有限制的。

SPFA，如何控制松弛 k 次，可以用一个变量 que_size 记录每一轮松弛入队列的所有节点数量，下一轮松弛的时候，就把队列里 que_size 个节点都弹出来，就是上一轮松弛入队列的节点。

import java.util.*;;

class Edge {
    int to, weight;

    Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }
}

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 节点数
        int m = input.nextInt(); // 边数

        // 邻接表存放所有边
        List<List<Edge>> grid = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            grid.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int s = input.nextInt() - 1;
            int t = input.nextInt() - 1;
            int v = input.nextInt();
            grid.get(s).add(new Edge(t, v));
        }

        int src = input.nextInt() - 1;
        int dst = input.nextInt() - 1;
        int k = input.nextInt();
        input.close();

        // minDist存放所有节点到起点的最小权值
        int[] minDist = new int[n];
        Arrays.fill(minDist, Integer.MAX_VALUE);
        minDist[src] = 0; // 起点

        // 用队列记录上一次被更新的节点
        Queue<Integer> queue = new ArrayDeque<>();
        queue.offer(src);

        // minDist_copy记录上一次松弛后的值
        int[] minDist_copy = new int[n];

        int queue_size;
        k++;

        // 对队列中所有节点出发的所有边进行 k + 1 松弛
        while ((k-- > 0) && !queue.isEmpty()) {

            for (int i = 0; i < n; i++) {
                minDist_copy[i] = minDist[i];
            }

            queue_size = queue.size();

            // visited控制每一轮松弛中队列不加入重复的元素
            boolean[] visited = new boolean[n];

            while ((queue_size--) > 0) {
                int from = queue.poll();
                visited[from] = false;
                for (Edge edge : grid.get(from)) {
                    // 开始松弛
                    if (minDist_copy[from] + edge.weight < minDist[edge.to]) {
                        minDist[edge.to] = minDist_copy[from] + edge.weight;
                        if (visited[edge.to] == false) {
                            queue.offer(edge.to);
                            visited[edge.to] = true;
                        }
                    }
                }
            }
        }

        if (minDist[dst] == Integer.MAX_VALUE) {
            System.out.println("unreachable");
        } else {
            System.out.println(minDist[dst]);
        }

    }
}

Floyd#

多源最短路，即求多个起点到多个终点的多条最短路径。

Floyd 算法核心思想是动态规划。

3 层 for 循环，关键是理解遍历顺序。

import java.util.*;;

public class Main {

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt(); // 节点数量，节点编号从1到N
        int M = input.nextInt(); // 道路的数量
        int[][] grid = new int[N + 1][N + 1]; // 邻接矩阵
        for (int i = 0; i <= N; i++) {
            Arrays.fill(grid[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i < M; i++) {
            int u = input.nextInt();
            int v = input.nextInt();
            int w = input.nextInt();
            grid[u][v] = w;
            grid[v][u] = w; // 双向道路
        }
        int Q = input.nextInt(); // 观景计划的数量
        int[][] plans = new int[Q][2];
        for (int i = 0; i < Q; i++) {
            int start = input.nextInt();
            int end = input.nextInt();
            plans[i][0] = start;
            plans[i][1] = end;
        }
        input.close();

        // Floyd求多源最短路
        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] == Integer.MAX_VALUE || grid[k][j] == Integer.MAX_VALUE) {
                        continue;
                    }
                    grid[i][j] = Math.min(grid[i][j], grid[i][k] + grid[k][j]);
                }
            }
        }

        for (int i = 0; i < Q; i++) {
            int start = plans[i][0];
            int end = plans[i][1];
            if (grid[start][end] == Integer.MAX_VALUE) {
                System.out.println(-1);
            } else {
                System.out.println(grid[start][end]);
            }
        }
    }
}

时间复杂度： O (n^3)

floyd 算法的时间复杂度相对较高，适合稠密图且源点较多的情况。

如果源点少，其实可以多次 dijsktra 求源点到终点。

A * (A star)#

在象棋中，马和象的移动规则分别是 “马走日” 和 “象走田”。现给定骑士的起始坐标和目标坐标，要求根据骑士的移动规则，计算从起点到达目标点所需的最短步数。

广搜：

import java.util.*;;

class Position {
    int x, y;

    Position(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public class Main {
    static int[][] dir = {
            { -2, 1 }, { -2, -1 }, { -1, 2 }, { -1, -2 }, { 1, 2 }, { 1, -2 }, { 2, 1 }, { 2, -1 }
    };

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt(); // 测试用例的数量
        for (int i = 0; i < n; i++) {
            int a1 = input.nextInt();
            int a2 = input.nextInt();
            int b1 = input.nextInt();
            int b2 = input.nextInt();
            bfs(a1, a2, b1, b2);
        }
        input.close();
    }

    public static void bfs(int a1, int a2, int b1, int b2) {
        boolean[][] board = new boolean[1001][1001];
        int count = 0;

        Queue<Position> queue = new ArrayDeque<>();
        queue.offer(new Position(a1, a2));
        board[a1][a2] = true;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                Position pos = queue.poll();

                if (pos.x == b1 && pos.y == b2) {
                    System.out.println(count);
                    return;
                }

                for (int j = 0; j < 8; j++) {
                    int x = pos.x + dir[j][0];
                    int y = pos.y + dir[j][1];
                    if (x > 0 && x < 1001 && y > 0 && y < 1001 && board[x][y] == false) {
                        board[x][y] = true;
                        queue.add(new Position(x, y));
                    }
                }
            }
            count++;
        }
    }
}

广搜中，做了很多无用的遍历，如果能让遍历方向朝着终点的方向去遍历，就可以避免很多无用遍历。

Astar 是一种广搜或 dijkstra 的改良版，关键在于启发式函数，也就是影响广搜或者 dijkstra 从容器（队列）里取元素的优先顺序。

BFS 是没有目的性的一圈一圈去搜索，而 A * 是有方向性的去搜索，可以节省很多没有必要的遍历步骤。

启发式函数要影响的就是队列里元素的排序，对队列里节点进行排序，就需要给每一个节点权值，每个节点的权值为 F，给出公式为：F = G + H，G：起点达到目前遍历节点的距离，F：目前遍历的节点到达终点的距离

起点达到目前遍历节点的距离 + 目前遍历的节点到达终点的距离就是起点到达终点的距离。

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

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

本题，采用欧拉距离才能最大程度体现点与点之间的距离。

import java.util.*;

class Main {
    int[][] dir = {
            { -2, 1 }, { -2, -1 }, { -1, 2 }, { -1, -2 }, { 1, 2 }, { 1, -2 }, { 2, 1 }, { 2, -1 }
    };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Main main = new Main();
        for (int i = 0; i < n; i++) {
            int[][] moves = new int[1001][1001];
            int a1 = sc.nextInt();
            int a2 = sc.nextInt();
            int b1 = sc.nextInt();
            int b2 = sc.nextInt();
            main.aStar(a1, a2, b1, b2, moves);
            System.out.println(moves[b1][b2]);
        }
    }

    public void aStar(int startx, int starty, int endx, int endy, int[][] moves) {
        PriorityQueue<int[]> que = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] a, int[] b) {
                return Integer.compare(a[3], b[3]);
            }
        });
        que.offer(new int[] { startx, starty, 0,
                compute(startx, starty, endx, endy) });
        while (!que.isEmpty()) {
            int[] cur = que.poll();
            int curx = cur[0];
            int cury = cur[1];
            // System.out.println(curx + " " + cury);
            if (curx == endx && cury == endy) {
                break;
            }
            for (int i = 0; i < 8; i++) {
                int nextx = curx + dir[i][0];
                int nexty = cury + dir[i][1];
                if (nextx < 1 || nextx > 1000 || nexty < 1 || nexty > 1000) {
                    continue;
                }
                if (moves[nextx][nexty] != 0) {
                    continue;
                }
                moves[nextx][nexty] = moves[curx][cury] + 1;
                int g = cur[2] + 5; // 马走日，1 * 1 + 2 * 2 = 5
                int h = compute(nextx, nexty, endx, endy);
                que.offer(new int[] { nextx, nexty, g, g + h });
            }
        }
    }

    public int compute(int x1, int y1, int x2, int y2) {
        return (x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2);
    }
}

总结#

20240508121355