在计算机科学领域，图论算法一直占据着重要地位，其中 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 算法，并在实际项目中发挥其优势。谢谢阅读！

---

希望这份博客能够帮助到你。如果有其他需要修改或添加的地方，请随时告诉我。