在計算機科學領域，圖論算法一直占據著重要地位，其中 Dijkstra 算法作為求解單源最短路徑問題的經典算法，被廣泛應用于路徑規劃、網絡路由等多個場景。無論是算法競賽、實際項目開發，還是計算機考研 408 的備考，Dijkstra 算法都是必須掌握的核心內容。

一、Dijkstra 算法的基本概念

Dijkstra 算法是由荷蘭計算機科學家 Edsger W. Dijkstra 在 1956 年提出的，用于解決帶權有向圖或無向圖中，從一個源點到其余各頂點的最短路徑問題，即單源最短路徑問題。

假設我們有一個帶權圖，圖中的節點表示不同的位置，邊表示位置之間的連接，邊上的權值代表從一個節點到另一個節點的距離或代價。Dijkstra 算法的目標就是找到從給定的源節點出發，到圖中其他所有節點的最短路徑。

若以節點 A 為源點，Dijkstra 算法會計算出從 A 到 B、C、D、E 各節點的最短路徑。

二、Dijkstra 算法的思想

Dijkstra 算法采用貪心策略，其核心思想是：從源點開始，每次從未確定最短路徑的節點中，選擇距離源點最近的節點，并確定該節點的最短路徑，然后以該節點為中間點，更新其他節點到源點的距離。不斷重復這個過程，直到所有節點的最短路徑都被確定。

具體來說，Dijkstra 算法在執行過程中維護兩個集合：

1. 已確定最短路徑的節點集合：初始時，該集合僅包含源節點。

1. 未確定最短路徑的節點集合：包含圖中除源節點外的所有其他節點。

算法通過不斷從 “未確定最短路徑的節點集合” 中選取距離源點最近的節點，將其加入 “已確定最短路徑的節點集合”，并更新該節點鄰接節點到源點的距離。

以下是 Dijkstra 算法的詳細步驟：

1. 初始化：

• • 將源節點到自身的距離設為 0，即dist[source] = 0，其他節點到源點的距離設為無窮大，即dist[i] = ∞（i ≠ source）。

• • 初始化 “已確定最短路徑的節點集合” 為空，“未確定最短路徑的節點集合” 包含圖中所有節點。

1. 循環迭代：

• • 從 “未確定最短路徑的節點集合” 中選擇距離源點最近的節點u，將其加入 “已確定最短路徑的節點集合”。

• • 遍歷節點u的所有鄰接節點v，如果通過節點u到達節點v的距離比當前記錄的dist[v]更小，則更新dist[v]，即dist[v] = dist[u] + weight(u, v)，其中weight(u, v)表示邊(u, v)的權值。

1. 重復步驟 2，直到 “未確定最短路徑的節點集合” 為空，此時dist數組中記錄的就是從源點到各個節點的最短路徑距離。

在初始狀態下，源點 S 到自身距離為 0，到其他節點距離為無窮大。第一輪選擇距離 S 最近的節點 B，更新 B 的鄰接節點 C 和 D 的距離。第二輪選擇距離 S 最近的節點 A，更新 A 的鄰接節點 D 的距離。第三輪選擇節點 D，此時所有節點的最短路徑都已確定。

三、Dijkstra 算法的解題思路

在實際應用中，使用 Dijkstra 算法解決問題時，通常需要以下幾個步驟：

1. 構建圖模型：根據題目描述，將問題抽象為帶權圖，確定節點和邊，并為邊賦予相應的權值。

1. 選擇源點：明確問題中指定的源節點，作為算法計算最短路徑的起點。

1. 執行 Dijkstra 算法：按照上述算法步驟，計算從源點到其他所有節點的最短路徑。

1. 處理結果：根據題目要求，對計算得到的最短路徑距離進行處理，例如返回特定節點的最短路徑、統計最短路徑的數量等。

四、LeetCode 例題及 Java 代碼實現

例題：網絡延遲時間（LeetCode 743）

有 n 個網絡節點，標記為 1 到 n。

給你一個列表 times，表示信號經過 有向 邊的傳遞時間。times[i] = (ui, vi, wi)，其中 ui 是源節點，vi 是目標節點， wi 是一個信號從源節點傳遞到目標節點的時間。

現在，從某個節點 K 發出一個信號。需要多久才能使所有節點都收到信號？如果不能使所有節點收到信號，返回 -1 。

解題思路

本題可以將網絡節點抽象為圖的節點，邊的傳遞時間作為邊的權值，問題就轉化為求從節點K出發，到所有節點的最短路徑中最長的那個時間。如果存在某個節點無法到達，則返回-1。使用 Dijkstra 算法計算從節點K到其他節點的最短路徑距離，然后找出最大的距離值即可。

Java 代碼實現

import java.util .*;public class NetworkDelayTime {public int networkDelayTime(int[][] times, int n, int k) {// 構建鄰接表存儲圖List<List<int[]>> graph = new ArrayList<>();for (int i = 0; i <= n; i++) {graph.add(new ArrayList<>());}for (int[] time : times) {graph.get(time[0]).add(new int[]{time[1], time[2]});}// 初始化距離數組，將所有距離設為無窮大int[] dist = new int[n + 1];Arrays.fill(dist, Integer.MAX_VALUE);dist[k] = 0;// 標記節點是否已確定最短路徑boolean[] visited = new boolean[n + 1];// 優先隊列用于存儲未確定最短路徑的節點，按距離源點的距離排序PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);pq.offer(new int[]{k, 0});while (!pq.isEmpty()) {int[] node = pq.poll();int u = node[0];if (visited[u]) {continue;}visited[u] = true;for (int[] neighbor : graph.get(u)) {int v = neighbor[0];int w = neighbor[1];if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {dist[v] = dist[u] + w;pq.offer(new int[]{v, dist[v]});}}}int maxTime = 0;for (int i = 1; i <= n; i++) {if (dist[i] == Integer.MAX_VALUE) {return -1;}maxTime = Math.max(maxTime, dist[i]);}return maxTime;}}

例題：解救人質（LeetCode 1306）

在一個 n x n 的網格中，每個單元格有兩種狀態：0 表示空單元格，1 表示人質押點。網格中有一個警衛，他的初始位置在 (0, 0)，并且只能向下或向右移動。

警衛想要到達一個人質押點，然后再回到 (0, 0)。他每次移動一個單元格需要花費 1 單位時間。請你返回警衛從 (0, 0) 出發，到達任意一個人質押點并返回 (0, 0) 所需的最短時間。如果沒有可到達的人質押點，則返回 -1。

解題思路

本題可以將網格中的每個單元格看作圖的節點，相鄰單元格之間的邊權值為 1。由于警衛只能向下或向右移動，我們可以使用 Dijkstra 算法從起點(0, 0)出發，計算到所有人質押點的最短距離，再加上從人質押點返回起點的距離，取最小值作為結果。如果不存在人質押點，則返回-1。

Java 代碼實現

import java.util.PriorityQueue;public class MinimumTimeVisitingAllPoints {public int minimumTime(int[][] grid) {int n = grid.length;int[][] dist = new int[n][n];for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {dist[i][j] = Integer.MAX_VALUE;}}dist[0][0] = 0;PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[2] - b[2]);pq.offer(new int[]{0, 0, 0});int[][] directions = {{0, 1}, {1, 0}};while (!pq.isEmpty()) {int[] node = pq.poll();int x = node[0];int y = node[1];int d = node[2];if (d > dist[x][y]) {continue;}for (int[] dir : directions) {int newX = x + dir[0];int newY = y + dir[1];if (newX >= 0 && newX < n && newY >= 0 && newY < n) {int newDist = d + 1;if (newDist < dist[newX][newY]) {dist[newX][newY] = newDist;pq.offer(new int[]{newX, newY, newDist});}}}}int minTime = Integer.MAX_VALUE;boolean hasTarget = false;for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (grid[i][j] == 1 && dist[i][j] != Integer.MAX_VALUE) {hasTarget = true;minTime = Math.min(minTime, dist[i][j] * 2);}}}return hasTarget ? minTime : -1;}}

五、Dijkstra 算法與考研 408

在計算機考研 408 中，Dijkstra 算法是數據結構和算法部分的重要考點，主要涉及以下幾個方面：

1. 圖的存儲結構：Dijkstra 算法的實現依賴于圖的存儲結構，常見的有鄰接矩陣和鄰接表。考研 408 中可能會考查不同存儲結構下 Dijkstra 算法的實現細節、空間復雜度和時間復雜度分析。例如，鄰接矩陣存儲圖時，Dijkstra 算法的時間復雜度為\(O(V^2)\)（\(V\)為節點數），而鄰接表存儲圖時，借助優先隊列優化后，時間復雜度可以降低到\(O((V + E) \log V)\)（\(E\)為邊數）。

1. 貪心算法思想：Dijkstra 算法是貪心算法的典型應用，考研 408 中對貪心算法的理解和應用是考查重點。考生需要掌握貪心算法的設計要素，如貪心選擇性質和最優子結構性質，并能夠分析 Dijkstra 算法如何滿足這些性質，從而正確求解單源最短路徑問題。

1. 算法正確性證明：雖然考研 408 中較少直接考查算法的正確性證明，但理解 Dijkstra 算法的正確性證明過程有助于深入掌握算法思想。證明過程通常基于數學歸納法，通過歸納假設和貪心選擇來逐步推導算法的正確性。

1. 算法應用與變形：考研 408 中可能會出現基于 Dijkstra 算法的變形題目，例如在有負權邊的圖中（Dijkstra 算法不適用于有負權邊的圖，此時需使用 Bellman-Ford 算法或 Floyd 算法）進行拓展，或者結合其他知識點（如拓撲排序、動態規劃等）綜合考查。考生需要靈活運用 Dijkstra 算法的思想，分析和解決這類問題。

在備考過程中，建議考生通過做大量的練習題來鞏固對 Dijkstra 算法的理解，熟悉不同題型的解題思路，同時結合圖的存儲結構、貪心算法等相關知識點進行系統復習，提高綜合解題能力。

六、總結

Dijkstra 算法作為求解單源最短路徑問題的經典算法，無論是在實際應用還是計算機學科的學習中都具有重要意義。本文通過詳細介紹 Dijkstra 算法的基本概念、算法思想、解題思路，結合 LeetCode 例題與 Java 代碼實現，以及考研 408 的考點分析，幫助大家全面深入地理解和掌握該算法。

希望本文能夠幫助讀者更深入地理解Dijkstra 算法，并在實際項目中發揮其優勢。謝謝閱讀！

---

希望這份博客能夠幫助到你。如果有其他需要修改或添加的地方，請隨時告訴我。