最短路問題刷題筆記

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