代碼隨想錄第六十二天| Floyd 算法精講 A * 算法精講（A star算法）最短路算法總結篇

Floyd 算法精講

題目描述

小明希望在公園散步時找到從一個景點到另一個景點的最短路徑。給定公園的景點圖，包含 N 個景點和 M 條雙向道路，每條道路有已知的長度。小明有 Q 個觀景計劃，每個計劃包含一個起點和終點，求每個計劃的最短路徑長度。

輸入包含景點數量 N、道路數量 M，接著 M 行每行三個整數 u、v、w 表示景點 u 和 v 之間的雙向道路長度為 w。然后輸入觀景計劃數量 Q，接著 Q 行每行兩個整數 start 和 end。輸出每個計劃的最短路徑長度，若無路徑則輸出 -1。

輸入輸出示例

輸入：

7 3 1 2 4 2 5 6 3 6 8 2 1 2 2 3

輸出：

4 -1

解題思路

算法原理

Floyd 算法是一種多源最短路徑算法，基于動態規劃思想。通過引入中間節點逐步更新所有節點對之間的最短距離，最終得到全局最優解。該算法可以處理帶負權的圖。

動態規劃思想

狀態定義：grid[i][j][k] 表示從節點 i 到節點 j，只能經過節點 1 到 k 的最短距離。
狀態轉移：grid[i][j][k] = min(grid[i][j][k-1], grid[i][k][k-1] + grid[k][j][k-1])，即不經過節點 k 或經過節點 k 的最小值。
初始化：初始時，grid[i][j][0] 為直接連接的邊的權值，其他為無窮大。
遍歷順序：按 k、i、j 的順序遍歷，確保每一步都基于之前的結果。

空間優化

由于每次計算只依賴前一次的結果，可以將三維數組優化為二維數組，減少空間復雜度。

代碼實現

import java.util.Scanner;public class FloydAlgorithm {public static final int MAX_VAL = 10005; // 邊的最大距離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];for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {grid[i][j] = MAX_VAL; // 初始化為最大值}}// 輸入道路信息for (int i = 0; i < m; i++) {int u = sc.nextInt();int v = sc.nextInt();int w = sc.nextInt();grid[u][v] = w; // 雙向道路grid[v][u] = w;}// Floyd 算法核心部分for (int k = 1; k <= n; k++) {for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {// 更新 i 到 j 的最短路徑if (grid[i][k] + grid[k][j] < grid[i][j]) {grid[i][j] = grid[i][k] + grid[k][j];}}}}// 處理觀景計劃int q = sc.nextInt(); // 計劃數量for (int i = 0; i < q; i++) {int start = sc.nextInt();int end = sc.nextInt();if (grid[start][end] == MAX_VAL) {System.out.println(-1); // 無路徑} else {System.out.println(grid[start][end]); // 最短路徑長度}}}
}

代碼注釋

初始化距離矩陣：grid[i][j] 初始化為最大值，表示初始時無路徑。
輸入道路信息：讀取每條道路并更新距離矩陣，雙向道路需兩邊更新。
Floyd 算法核心：三重循環，逐步引入中間節點 k，更新所有節點對的最短路徑。
處理觀景計劃：對每個計劃查詢最短路徑，若仍為最大值則輸出 -1，否則輸出路徑長度。

總結

Floyd 算法通過動態規劃思想，利用三維數組逐步更新節點間的最短路徑。空間優化后使用二維數組，時間復雜度為 O(n^3)，適合稠密圖或多源最短路徑問題。理解動態規劃的狀態轉移和遍歷順序是掌握該算法的關鍵。

A* 算法精講

題目描述

在象棋中，騎士（馬）按照“日”字形移動。給定騎士的起始坐標和目標坐標，計算從起點到達目標點所需的最短步數。棋盤大小為 1000x1000。

輸入包含多個測試用例，每行給出起點和目標點的坐標。輸出每個測試用例的最短步數。

輸入輸出示例

輸入：

輸出：

解題思路

算法原理

A* 算法是一種啟發式搜索算法，結合了廣度優先搜索（BFS）和迪杰斯特拉算法（Dijkstra）的優點，通過引入啟發式函數來指導搜索方向，從而提高搜索效率。

關鍵點

啟發式函數：用于估計當前節點到目標節點的距離，指導搜索方向。常見的啟發式函數包括曼哈頓距離、歐氏距離和切比雪夫距離。本題采用歐氏距離。
優先級隊列：根據啟發式函數計算的值（F = G + H）對節點進行排序，優先擴展最有可能接近目標的節點。
節點狀態記錄：記錄已訪問節點的步數，避免重復訪問。

代碼實現

import java.util.*;
import java.awt.Point;
import java.util.PriorityQueue;public class KnightAttack {// 定義騎士的8個可能移動方向private static final int[][] MOVES = {{-2, -1}, {-2, 1}, {-1, -2}, {-1, 2},{1, -2}, {1, 2}, {2, -1}, {2, 1}};public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();for (int i = 0; i < n; i++) {int a1 = scanner.nextInt();int a2 = scanner.nextInt();int b1 = scanner.nextInt();int b2 = scanner.nextInt();System.out.println(astar(new Point(a1, a2), new Point(b1, b2)));}}private static int astar(Point start, Point end) {// 優先級隊列，存儲 (總代價, 當前位置, 已走步數)PriorityQueue<Node> heap = new PriorityQueue<>((a, b) -> Double.compare(a.f, b.f));heap.add(new Node(start, 0, heuristic(start, end)));// 記錄訪問過的節點及其步數Map<Point, Integer> visited = new HashMap<>();visited.put(start, 0);while (!heap.isEmpty()) {Node current = heap.poll();// 檢查是否到達目標if (current.point.equals(end)) {return current.steps;}// 生成下一個可能的移動位置for (int[] move : MOVES) {Point nextPoint = new Point(current.point.x + move[0], current.point.y + move[1]);// 檢查是否在棋盤范圍內if (nextPoint.x >= 1 && nextPoint.x <= 1000 && nextPoint.y >= 1 && nextPoint.y <= 1000) {int newSteps = current.steps + 1;// 如果該位置未被訪問或有更短路徑if (!visited.containsKey(nextPoint) || newSteps < visited.get(nextPoint)) {visited.put(nextPoint, newSteps);double f = newSteps + heuristic(nextPoint, end);heap.add(new Node(nextPoint, newSteps, f));}}}}// 如果無法到達目標return -1;}private static double heuristic(Point start, Point end) {// 歐氏距離啟發式函數double dx = start.x - end.x;double dy = start.y - end.y;return Math.sqrt(dx * dx + dy * dy);}private static class Node {Point point;int steps;double f; // 總代價：f = steps + heuristicNode(Point point, int steps, double f) {this.point = point;this.steps = steps;this.f = f;}}
}

代碼注釋

移動方向定義：騎士有8個可能的移動方向，用 moves 數組表示。
啟發式函數：heuristic 函數計算兩個點之間的歐氏距離，作為估計距離。
A 搜索函數*：astar 函數使用優先級隊列進行搜索，每次擴展最有可能接近目標的節點。
優先級隊列：隊列中存儲元組 (總代價, 當前位置x, 當前位置y, 已走步數)，按總代價排序。
訪問記錄：visited 字典記錄已訪問節點及其最小步數，避免重復訪問。
輸入處理：讀取多個測試用例，對每個用例調用 astar 函數計算最短步數。

總結

A* 算法通過引入啟發式函數，能夠在大規模地圖上高效地找到最短路徑。相比傳統的廣度優先搜索（BFS），A* 算法通過優先擴展接近目標的節點，減少了不必要的搜索，提高了效率。選擇合適的啟發式函數對算法性能至關重要。

最短路算法總結

至此已經講解了四大最短路算法，分別是 Dijkstra、Bellman-Ford、SPFA 和 Floyd。

針對這四大最短路算法，我用了七篇長文才徹底講清楚，分別是：

Dijkstra 樸素版
Dijkstra 堆優化版
Bellman-Ford
Bellman-Ford 隊列優化算法（又名 SPFA）
Bellman-Ford 算法判斷負權回路
Bellman-Ford 之單源有限最短路
Floyd 算法精講
啟發式搜索：A * 算法

最短路算法比較復雜，而且各自有各自的應用場景。以下是講過的最短路算法的使用場景對比表：

算法	適用場景	特點
Dijkstra	單源且邊為正數	效率高，適合稀疏圖和稠密圖的不同版本
SPFA	單源邊可為負數	一般情況下比 Bellman-Ford 效率高，適合大部分場景
Bellman-Ford	單源邊可為負數，需判斷負權回路	可以檢測負權回路，代碼實現相對簡單
Floyd	多源點求最短路	適合節點數量較少的情況，實現簡單

（因為 A * 屬于啟發式搜索，和上面最短路算法并不是一類，不適合一起對比，所以沒有放在一起）

可能有同學感覺：這個表太復雜了，我記也記不住。

其實記不住的原因還是對這幾個最短路算法沒有深刻的理解。這里給大家一個大體使用場景的分析：

如果遇到單源且邊為正數，直接 Dijkstra。至于使用樸素版還是堆優化版，還是取決于圖的稠密度。多少節點多少邊算是稠密圖，多少算是稀疏圖，這個沒有量化。如果想量化，只能寫出兩個版本然后做實驗去測試，不同的判題機得出的結果還不太一樣。一般情況下，可以直接用堆優化版本。
如果遇到單源邊可為負數，直接 Bellman-Ford。同樣 SPFA 還是 Bellman-Ford 取決于圖的稠密度。一般情況下，直接用 SPFA。
如果有負權回路，優先 Bellman-Ford。如果是有限節點最短路，也優先 Bellman-Ford，理由是寫代碼比較方便。
如果是遇到多源點求最短路，直接 Floyd。除非源點特別少，且邊都是正數，那可以多次 Dijkstra 求出最短路徑，但這種情況很少。一般出現多個源點了，就是想讓你用 Floyd 了。
對于 A *，由于其高效性，在實際工程應用中使用最為廣泛。由于其結果的不唯一性，也就是可能是次短路的特性，一般不適合作為算法題。游戲開發、地圖導航、數據包路由等都廣泛使用 A * 算法。