Dijkstra（迪杰斯特拉）算法详解

目录一、算法核心原理1. 适用场景2. 核心思想贪心策略3. 松弛操作Relaxation4. 两种实现方式对比二、方式一邻接矩阵实现O(n2)入门首选场景说明Java 完整代码 详细注释运行结果三、方式二邻接表 优先队列堆优化工程常用 O(MlogN)思路Java 完整代码堆优化版关键点说明四、面试高频总结一、算法核心原理1. 适用场景单源最短路径算法计算一个起点到图中所有其他节点的最短路径。要求图中边权值必须非负负数权边会导致算法失效图类型有向图 / 无向图均可2. 核心思想贪心策略维护两个集合已确定最短路径集合 S存放已经算出最短距离的节点未确定集合 U剩余节点初始化起点距离为0其余节点距离为无穷大。循环贪心选择从U中选出当前距离起点最近的节点u加入集合S。以u为中转节点松弛操作更新起点到u邻接节点的最短距离。直到所有节点都加入S算法结束。3. 松弛操作Relaxation设dist[v]起点到节点v当前最短距离dist[u]起点到节点u最短距离w(u,v)边u→v的权重公式 dist[v]min(dist[v], dist[u]w(u,v)) 含义走「起点→u→v」是否比原来直接到 v 更近是则更新距离。4. 两种实现方式对比实现方式时间复杂度特点邻接矩阵 暴力遍历找最小节点O(n2)简单直观适合节点数少的稠密图邻接表 优先队列 (堆)O(MlogN)效率更高适合边数多的稀疏图二、方式一邻接矩阵实现O(n2)入门首选场景说明节点数量少用二维数组存储图逻辑最简单便于理解流程。Java 完整代码 详细注释import java.util.Arrays; public class DijkstraMatrix { // 无穷大代表两点不可达 private static final int INF Integer.MAX_VALUE / 2; // 防溢出 /** * param graph 邻接矩阵图 graph[i][j] 表示 i→j 的边权 * param start 起始节点下标 * return 起点到每个节点的最短距离数组 */ public static int[] dijkstra(int[][] graph, int start) { int n graph.length; // dist[]起点到各节点最短距离 int[] dist new int[n]; // visited[]标记节点是否已确定最短路径集合S boolean[] visited new boolean[n]; // 1. 初始化距离数组 Arrays.fill(dist, INF); dist[start] 0; // 起点到自身距离为0 // 遍历 n 轮每轮确定一个节点的最短路径 for (int i 0; i n; i) { // 2. 第一步从未访问节点中找到距离起点最近的节点 u int u -1; int minDist INF; for (int j 0; j n; j) { if (!visited[j] dist[j] minDist) { minDist dist[j]; u j; } } if (u -1) break; // 剩余节点均不可达提前退出 visited[u] true; // 加入已确定集合 // 3. 第二步松弛操作更新 u 所有邻接节点的距离 for (int v 0; v n; v) { // v 未访问 且 u→v 有边 if (!visited[v] graph[u][v] ! INF) { if (dist[v] dist[u] graph[u][v]) { dist[v] dist[u] graph[u][v]; } } } } return dist; } public static void main(String[] args) { // 构建邻接矩阵5个节点 0~4 int[][] graph { {INF, 2, 4, INF, INF}, {2, INF, 1, 7, INF}, {4, 1, INF, 1, 5}, {INF, 7, 1, INF, 2}, {INF, INF, 5, 2, INF} }; int start 0; int[] res dijkstra(graph, start); System.out.println(起点 start 到各节点最短距离); for (int i 0; i res.length; i) { System.out.println(节点 i res[i]); } } }运行结果起点 0 到各节点最短距离 节点00 节点12 节点23 节点34 节点46三、方式二邻接表 优先队列堆优化工程常用 O(MlogN)节点 / 边数量大时暴力找最小节点效率极低用最小堆优先队列快速取出当前距离最小的节点是面试 / 开发主流写法。思路用邻接表ListListEdge存储图节省空间。优先队列小顶堆存放(节点编号, 当前距离)自动按距离升序排序。堆中会存在旧的无效记录同一节点多条距离记录遇到已确定最短路径的节点直接跳过。Java 完整代码堆优化版import java.util.*; public class DijkstraHeap { private static final int INF Integer.MAX_VALUE / 2; // 边类目标节点 边权重 static class Edge { int to; int weight; Edge(int to, int weight) { this.to to; this.weight weight; } } // 堆元素节点 起点到该节点的距离 static class Node implements ComparableNode { int id; int dist; Node(int id, int dist) { this.id id; this.dist dist; } // 小顶堆距离小的排在前面 Override public int compareTo(Node o) { return this.dist - o.dist; } } /** * 堆优化 Dijkstra * param adj 邻接表 * param start 起点 * return 最短距离数组 */ public static int[] dijkstra(ListListEdge adj, int start) { int n adj.size(); int[] dist new int[n]; boolean[] visited new boolean[n]; Arrays.fill(dist, INF); dist[start] 0; // 最小优先队列 PriorityQueueNode heap new PriorityQueue(); heap.add(new Node(start, 0)); while (!heap.isEmpty()) { // 取出当前距离最小的节点 Node cur heap.poll(); int u cur.id; // 该节点已确定最短路径跳过旧数据 if (visited[u]) continue; visited[u] true; // 遍历 u 的所有邻接边执行松弛 for (Edge edge : adj.get(u)) { int v edge.to; int w edge.weight; if (!visited[v] dist[v] dist[u] w) { dist[v] dist[u] w; heap.add(new Node(v, dist[v])); // 新距离入堆 } } } return dist; } public static void main(String[] args) { // 构建邻接表5个节点 0~4 int n 5; ListListEdge adj new ArrayList(); for (int i 0; i n; i) { adj.add(new ArrayList()); } // 添加边无向图双向添加 adj.get(0).add(new Edge(1, 2)); adj.get(0).add(new Edge(2, 4)); adj.get(1).add(new Edge(0, 2)); adj.get(1).add(new Edge(2, 1)); adj.get(1).add(new Edge(3, 7)); adj.get(2).add(new Edge(0, 4)); adj.get(2).add(new Edge(1, 1)); adj.get(2).add(new Edge(3, 1)); adj.get(2).add(new Edge(4, 5)); adj.get(3).add(new Edge(1, 7)); adj.get(3).add(new Edge(2, 1)); adj.get(3).add(new Edge(4, 2)); adj.get(4).add(new Edge(2, 5)); adj.get(4).add(new Edge(3, 2)); int start 0; int[] res dijkstra(adj, start); System.out.println(起点 start 到各节点最短距离); for (int i 0; i res.length; i) { System.out.println(节点 i res[i]); } } }关键点说明为什么不删除堆中旧数据堆不支持高效删除因此重复入队用visited标记过滤失效数据这是标准优化写法。负数权边问题若存在负权边贪心策略不再成立Dijkstra 失效需改用Bellman-Ford / SPFA。不能求负权环负权环会让路径无限变短所有单源最短路径算法都无法处理。四、面试高频总结原理贪心 松弛操作单源最短路径边权非负。两种实现邻接矩阵O(n2)适合小图、稠密图。堆优化 邻接表O(MlogN)工程 / 面试主流适合大图、稀疏图。核心步骤选最近节点 → 标记已确定 → 松弛更新邻接点距离。局限性不支持负权边、负权环。