一、问题定义
给定一张带权有向图（或无向图）和一个源点 ，求从 到其余每个顶点的最短路径长度，这就是单源最短路径问题。
适用前提Dijkstra 算法要求图中所有边的权值非负（）。若存在负权边，需改用 Bellman-Ford 或 SPFA 算法。
二、基本思想
Dijkstra 算法采用贪心策略，结构上与 Prim 最小生成树 高度相似。
将所有顶点分为两组：
- 已敲定集合 ：已经确定了最短路径的顶点。
- 未敲定集合 ：尚未确定最短路径的顶点。
用数组 记录源点 到每个顶点的当前已知最短距离估计值，初始时：
算法的每一轮做两件事：
- 选择顶点：从未敲定集合 中取出 值最小的顶点 ，将它移入已敲定集合 ——此时 即为 到 的真实最短距离。
- 松弛：对于 的每一条出边 ，若 ，则更新 。
重复上述过程，直到所有顶点都被敲定为止。
局部最优推导全局最优关键在于非负权值。当 被选出时，它的估计距离最小，其他未确认顶点 都满足 。由于边权非负，绕到 再回到 只会更远，不可能得到比 更短的路径。因此 可以被安全敲定。
算法整体流程如下：
三、算法执行步骤图解
以如下 6 顶点带权有向图为例（顶点：，源点为 ）：
| 边 | 权值 |
|---|---|
A→B | 4 |
A→C | 2 |
B→C | 1 |
B→D | 5 |
C→B | 1 |
C→D | 8 |
C→E | 10 |
D→E | 2 |
D→F | 6 |
E→F | 3 |
初始状态：，。
第 1 轮：选出 （）
松弛出边 、，，。
第 2 轮：选出 （）
松弛 ， 由 降至 ；松弛 、，，。
第 3 轮：选出 （）
： 已敲定，跳过。， 由 降至 。
第 4 轮：选出 （）
松弛 ， 由 降至 ；松弛 ，。
第 5 轮：选出 （）
松弛 ， 由 降至 。
第 6 轮：选出 （）
无出边，不再松弛。所有顶点敲定，算法结束。
最终结果
源点 到各顶点的最短距离：
最短路径树由 5 条边构成（绿色加粗）：。
四、两种实现方式
4.1 朴素实现（邻接矩阵，）
适合稠密图（边数 ）。每轮线性扫描所有顶点，找出 值最小的未敲定顶点。
import java.util.Arrays;
public class DijkstraMatrix {
private static final int INF = Integer.MAX_VALUE / 2;
/** * 朴素 Dijkstra（邻接矩阵版）。 * @param graph graph[u][v] 表示 u→v 的边权，INF 表示无边 * @param src 源点编号 * @return 源点到各顶点的最短距离数组 */ public static int[] dijkstra(int[][] graph, int src) { int n = graph.length; int[] d = new int[n]; boolean[] settled = new boolean[n];
Arrays.fill(d, INF); d[src] = 0;
for (int iter = 0; iter < n; iter++) { // 1. 从未敲定顶点中选出 d 值最小的顶点 u int u = -1; for (int v = 0; v < n; v++) { if (!settled[v] && (u == -1 || d[v] < d[u])) { u = v; } } if (d[u] == INF) break; // 剩余顶点不可达，提前退出
// 2. 敲定 u，松弛所有出边 settled[u] = true; for (int v = 0; v < n; v++) { if (!settled[v] && graph[u][v] < INF) { d[v] = Math.min(d[v], d[u] + graph[u][v]); } } } return d; }
public static void main(String[] args) { // 顶点编号：A=0, B=1, C=2, D=3, E=4, F=5 int n = 6; int[][] g = new int[n][n]; for (int[] row : g) Arrays.fill(row, INF); for (int i = 0; i < n; i++) g[i][i] = 0;
g[0][1] = 4; // A→B g[0][2] = 2; // A→C g[1][2] = 1; // B→C g[1][3] = 5; // B→D g[2][1] = 1; // C→B g[2][3] = 8; // C→D g[2][4] = 10; // C→E g[3][4] = 2; // D→E g[3][5] = 6; // D→F g[4][5] = 3; // E→F
int[] dist = dijkstra(g, 0); String[] name = {"A", "B", "C", "D", "E", "F"}; System.out.println("从 A 出发的最短距离："); for (int i = 0; i < n; i++) { System.out.println(" A → " + name[i] + " = " + dist[i]); } }}运行输出：
从 A 出发的最短距离： A → A = 0 A → B = 3 A → C = 2 A → D = 8 A → E = 10 A → F = 134.2 堆优化实现（邻接表 + 优先队列，）
适合稀疏图（边数 ）。用最小堆维护 值最小的候选顶点，每次松弛后将新的 压入堆，避免线性扫描。
懒删除策略堆中可能存有同一顶点的多条过期记录。弹出时检查该记录的距离是否等于当前 ；若不等，说明已过期，跳过即可。
import java.util.*;
public class DijkstraHeap {
private static final int INF = Integer.MAX_VALUE / 2;
/** * 堆优化 Dijkstra（邻接表版）。 * @param adj adj[u] 存储所有从 u 出发的边：int[]{v, weight} * @param n 顶点总数 * @param src 源点编号 * @return 源点到各顶点的最短距离数组 */ public static int[] dijkstra(List<int[]>[] adj, int n, int src) { int[] d = new int[n]; Arrays.fill(d, INF); d[src] = 0;
// 最小堆：按距离升序，存储 {dist, vertex} PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0])); pq.offer(new int[]{0, src});
while (!pq.isEmpty()) { int[] top = pq.poll(); int dist = top[0]; int u = top[1];
// 过期记录：跳过 if (dist > d[u]) continue;
// 松弛所有出边 for (int[] edge : adj[u]) { int v = edge[0]; int w = edge[1]; if (d[u] + w < d[v]) { d[v] = d[u] + w; pq.offer(new int[]{d[v], v}); } } } return d; }
@SuppressWarnings("unchecked") public static void main(String[] args) { int n = 6; List<int[]>[] adj = new ArrayList[n]; for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
// 顶点编号：A=0, B=1, C=2, D=3, E=4, F=5 adj[0].add(new int[]{1, 4}); // A→B adj[0].add(new int[]{2, 2}); // A→C adj[1].add(new int[]{2, 1}); // B→C adj[1].add(new int[]{3, 5}); // B→D adj[2].add(new int[]{1, 1}); // C→B adj[2].add(new int[]{3, 8}); // C→D adj[2].add(new int[]{4, 10}); // C→E adj[3].add(new int[]{4, 2}); // D→E adj[3].add(new int[]{5, 6}); // D→F adj[4].add(new int[]{5, 3}); // E→F
int[] dist = dijkstra(adj, n, 0); String[] name = {"A", "B", "C", "D", "E", "F"}; System.out.println("从 A 出发的最短距离："); for (int i = 0; i < n; i++) { System.out.println(" A → " + name[i] + " = " + dist[i]); } }}4.3 如何记录最短路径本身
上面的代码只输出了最短距离。若需要还原完整的最短路径，增加一个 prev[] 数组，在每次松弛成功时记录前驱顶点即可。
int[] prev = new int[n];Arrays.fill(prev, -1);
// 松弛时同步更新前驱if (d[u] + w < d[v]) { d[v] = d[u] + w; prev[v] = u; // 记录：到达 v 的前一跳是 u pq.offer(new int[]{d[v], v});}还原路径（逆序追溯）：
public static List<Integer> getPath(int[] prev, int target) { List<Integer> path = new ArrayList<>(); for (int v = target; v != -1; v = prev[v]) { path.add(v); } Collections.reverse(path); return path;}五、复杂度分析
设顶点数为 ，边数为 。
| 实现方式 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素实现（邻接矩阵） | 稠密图 | ||
| 堆优化（邻接表 + 优先队列） | 稀疏图 |
朴素实现分析：
外层循环执行 轮，每轮做两件事：
- 线性扫描所有未敲定顶点，找出 值最小者，耗时 。
- 遍历 对应的邻接矩阵行，松弛所有出边，耗时 。
因此：
稠密图中 ，此时 。相比堆优化版的 ，矩阵版少一个 因子，且常数更小，实际常常更快。
堆优化分析：
每条边最多触发一次松弛，每次松弛将新记录压入优先队列，耗时 ，因此松弛操作的总代价为：
堆中可能存有同一顶点的多条过期记录，但总记录数不超过 。每次弹出时若发现记录已过期则直接跳过，跳过操作的总次数不超过 ，单次弹出耗时 。
由于图中边数满足 ，可得：
从而在渐进意义下：
因此跳过操作的总代价为 ，与松弛操作同阶。综上，堆优化版的总时间复杂度为 。
与 Prim 算法的对比Dijkstra 与堆优化 Prim 的代码骨架几乎一致，区别在于：
- Prim：松弛时比较的是边权 ，维护的是顶点与已有树的最近距离。
- Dijkstra：松弛时比较的是路径总长 ，维护的是顶点与源点的最短距离。
手算技巧手算 Dijkstra 时，画一张距离表逐轮更新即可：每轮圈出当前 值最小的未敲定顶点，沿其出边更新邻居。顶点一旦敲定，最短距离就不会再变。若剩余未敲定顶点的 值均为 ，说明它们从源点不可达，可以停笔。
六、Dijkstra 与 Bellman-Ford 对比
Dijkstra 并非在所有图上都适用，当图中含负权边时，需要使用 Bellman-Ford 算法。
| 维度 | Dijkstra | Bellman-Ford |
|---|---|---|
| 负权边 | 不支持（需非负权值） | 支持 |
| 负权环检测 | 不支持 | 支持 |
| 时间复杂度 | （堆优化） | |
| 适用场景 | 非负权图，追求速度 | 含负权边，或需要检测负环 |
| 算法策略 | 贪心，顶点逐一敲定 | 动态规划，反复松弛所有边 |
七、总结
Dijkstra 算法可以概括为：
维护一个距离估计数组 ，每次从未敲定的顶点中贪心地选出距源点最近的那个，将其敲定，然后沿其出边松弛邻居的距离估计值，如此往复直到所有顶点敲定为止。
要点梳理：
- 正确性依据：边权非负保证了贪心选择的局部最优即全局最优，已敲定顶点的距离不会再被缩短。
- 两种实现：稠密图用邻接矩阵朴素实现（）；稀疏图用邻接表加最小堆（），两者适用场景不同。
- 路径还原：增加
prev[]数组记录前驱，松弛时同步更新，最后逆序追溯即可。 - 局限性：不支持负权边，遇到负权图需改用 Bellman-Ford 或 SPFA。
口诀记忆：
初始源点距离零，其余顶点无穷大；每轮选出最近点，沿边松弛更新它。
如果这篇文章对你有帮助，欢迎分享给更多人！
部分信息可能已经过时