图论入门：Dijkstra最短路径算法详解

前言在现实生活中我们经常会遇到这样的问题从A地到B地哪条路最近在计算机网络中数据包从源节点到目标节点走哪条路径最快这些问题本质上都是最短路径问题。而Dijkstra算法就是解决这类问题最经典、最常用的算法之一。一、什么是Dijkstra算法Dijkstra算法又称迪杰斯特拉算法是由荷兰计算机科学家Edsger W. Dijkstra在1956年提出、于1959年公开发表的一种经典算法。它用于解决单源最短路径问题——即从一个起点出发找到该起点到图中所有其他顶点的最短路径。简单来说给定一个起点Dijkstra算法能告诉你到图中每一个其他点最短要走多远。单源的意思是只有一个起点。如果你想求任意两点之间的最短路径可以多次运行Dijkstra算法每个点作为起点跑一次算法的适用条件Dijkstra算法有一个重要的前提图中所有边的权重必须是非负数。如果存在负权边Dijkstra算法可能会得到错误的结果。对于含负权边的情况可以使用Bellman-Ford算法。二、核心思想贪心策略Dijkstra算法的核心思想是贪心——每一步都选择当前看来最优的节点。具体来说算法将图中的顶点分为两组已确定最短路径的顶点集合S这些顶点的最短距离已经最终确定不会再改变未确定最短路径的顶点集合U这些顶点的最短距离还在更新中算法每次从集合U中选出距离起点最近的那个顶点将其移入集合S然后尝试通过这个顶点去松弛更新其他顶点的距离。松弛操作Relaxation如果通过当前节点u能到达邻居v且起点到u的距离 u到v的边的权重 起点到v的当前距离那么就更新v的距离。简单说就是走u这条路会不会更近三、算法步骤Dijkstra算法的执行流程可以分为以下几个步骤第一步初始化创建一个距离数组dist[]记录起点到每个顶点的当前最短距离将起点的距离设为0其他所有顶点的距离设为无穷大∞创建一个集合或数组记录哪些顶点已经被处理已确定最短路径第二步选择当前距离最小的未处理顶点从所有未处理的顶点中选出dist[]值最小的那个顶点 u。第三步松弛更新遍历顶点 u 的所有邻居 v如果dist[u] weight(u, v) dist[v]则更新dist[v] dist[u] weight(u, v)这表示通过 u 走到 v 比之前记录的路径更短第四步标记已处理将顶点 u 标记为已处理已确定最短路径之后不再更新它。第五步重复重复步骤二到步骤四直到所有顶点都被处理完毕。四、图解示例4.1 示例图本次使用的图包含 6 个顶点A, B, C, D, E, F所有边均为无向边即可以双向通行边上的数字代表权重距离/成本。对应的边列表起点终点权重AB3AC1AE1BC2BD4BE3CD1CF1DE6DF3EF64.2 算法执行过程我们的起点为A。初始状态顶点ABCDEF距离0∞∞∞∞∞已处理✅❌❌❌❌❌第 1 轮处理 A从 A 出发查看 A 的所有邻居到B距离 0 3 3到C距离 0 1 1到E距离 0 1 1更新距离表顶点ABCDEF距离031∞1∞已处理✅❌❌❌❌❌此时未处理顶点中距离最小的是C距离 1和E距离 1。我们以此来处理。第 2 轮处理 C当前节点 C 的距离为 1。查看 C 的所有邻居A, B, D, F到B1 2 3不大于现有的 3不更新到D1 1 2更新 D 2到F1 1 2更新 F 2顶点ABCDEF距离031212已处理✅❌✅❌❌❌第 3 轮处理 E当前节点 E 的距离为 1。查看 E 的所有邻居A, B, D, F到B1 3 4大于现有的 3不更新到D1 6 7大于现有的 2不更新到F1 6 7大于现有的 2不更新顶点ABCDEF距离031212已处理✅❌✅❌✅❌第 4 轮处理 D当前节点 D 的距离为 2。查看 D 的所有邻居B, C, E, F到B2 4 6大于现有的 3不更新到F2 3 5大于现有的 2不更新顶点ABCDEF距离031212已处理✅❌✅✅✅❌第 5 轮处理 F当前节点 F 的距离为 2。查看 F 的所有邻居C, D, E到 C213大于1不更新到 D235大于2不更新到 E268大于1不更新顶点ABCDEF距离031212已处理✅❌✅✅✅✅第 6 轮处理 B当前节点 B 的距离为 3。查看 B 的所有邻居A, C, D, E均不满足更新条件算法结束。4.3 最终结果从 A 到各顶点的最短距离为顶点ABCDEF最短距离031212验证A→D 的最短路径是A → C → D权重 112而不是走 A→E→D167。✅五、Java 代码实现在实际应用中我们通常使用优先队列最小堆来优化每次找距离最小的未处理顶点这一操作将时间复杂度从 O(V²) 降到 O((VE)logV)。5.1 完整代码public class Dijkstra { /** * Dijkstra 算法优先队列优化版 * param n 顶点个数 * param graph 邻接表graph.get(u) 返回 int[]{v, w} 数组v是邻居w是权重 * param start 起点编号 * return 从起点到各顶点的最短距离数组 */ public static int[] dijkstra(int n, ListListint[] graph, int start) { // 1. 距离数组初始化为无穷大 int[] dist new int[n]; Arrays.fill(dist, Integer.MAX_VALUE); dist[start] 0; // 2. 优先队列最小堆存储 [节点编号, 当前距离] PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1])); //队列里的所有包裹节点谁离起点的距离a[1]小谁就排在队头优先被弹出 pq.offer(new int[]{start, 0}); // 3. 标记数组记录顶点是否已确定最短路径 boolean[] visited new boolean[n]; while (!pq.isEmpty()) { // 弹出距离最小的节点 int[] cur pq.poll(); int u cur[0];//u是当前节点编号 // 如果已经处理过跳过避免重复处理过时数据 if (visited[u]) continue; visited[u] true; // 4. 遍历所有邻居进行松弛操作 for (int[] edge : graph.get(u)) { int v edge[0]; // 邻居顶点 int w edge[1]; // 边权重 // 如果通过 u 到 v 更短则更新 if (dist[u] w dist[v]) { dist[v] dist[u] w; pq.offer(new int[]{v, dist[v]}); } } } return dist; } // 辅助方法添加无向边双向添加 private static void addEdge(ListListint[] graph, int u, int v, int w) { graph.get(u).add(new int[]{v, w}); graph.get(v).add(new int[]{u, w}); } public static void main(String[] args) { // 顶点编号A0, B1, C2, D3, E4, F5 int n 6; // 初始化邻接表 ListListint[] graph new ArrayList(); for (int i 0; i n; i) { graph.add(new ArrayList()); } // 添加边对应示例图 addEdge(graph, 0, 1, 3); // A-B addEdge(graph, 0, 2, 1); // A-C addEdge(graph, 0, 4, 1); // A-E addEdge(graph, 1, 2, 2); // B-C addEdge(graph, 1, 3, 4); // B-D addEdge(graph, 1, 4, 3); // B-E addEdge(graph, 2, 3, 1); // C-D addEdge(graph, 2, 5, 1); // C-F addEdge(graph, 3, 4, 6); // D-E addEdge(graph, 3, 5, 3); // D-F addEdge(graph, 4, 5, 6); // E-F // 运行算法起点为 A(0) int[] result dijkstra(n, graph, 0); // 打印结果 char[] names {A, B, C, D, E, F}; for (int i 0; i n; i) { System.out.println(到 names[i] 的最短距离为: result[i]); } // 输出 // 到 A 的最短距离为: 0 // 到 B 的最短距离为: 3 // 到 C 的最短距离为: 1 // 到 D 的最短距离为: 2 // 到 E 的最短距离为: 1 // 到 F 的最短距离为: 2 } }5.2 代码逐行解读① 为什么用Integer.MAX_VALUE表示无穷大因为起点到其他点一开始未知看作无穷远方便后面被更小的值替换。② 优先队列里放int[]它怎么排序的PriorityQueueint[] pq new PriorityQueue(Comparator.comparingInt(a - a[1]));这行代码的意思是队列里放的是{节点, 距离}按照距离a[1]从小到大每次pq.poll()拿到的都是距离最短的那个节点。③visited数组是干什么的当某个节点的最短距离确定后后面可能还会因为别的路径产生一个较大的距离被丢进队列过时数据。visited确保每个节点只处理一次一旦确定最短距离就不再理它。④ 核心三行松弛操作javaif (dist[u] w dist[v]) { dist[v] dist[u] w; pq.offer(new int[]{v, dist[v]}); }当前站在 u走到 u 已经花了dist[u]的距离如果从 u 再到 v总花费dist[u] w比之前记录的dist[v]更小说明找到近路了赶紧更新dist[v]并把 v 丢进队列等着用 v 去更新它的邻居六、时间复杂度分析Dijkstra算法有两种常见的实现方式实现方式时间复杂度适用场景朴素实现数组遍历O(V²)稠密图边多优先队列优化二叉堆O((VE)logV)稀疏图边少其中 V 是顶点数E 是边数。因为边少时优先队列省掉了朴素算法每次遍历全部顶点找最小值的巨额固定开销O(V²)而边多时优先队列需要为每条边支付一次昂贵的堆调整费用O(logV)累计成本E·logV超过了朴素算法仅做简单数组扫描和赋值的代价所以边少用堆省扫描费边多用朴素省堆调整费。对于大多数实际应用场景如地图导航、网络路由图通常是稀疏的因此优先队列优化版本更为常用。七、实际应用场景Dijkstra算法的应用非常广泛几乎涉及到所有需要找最短/最快路径的场景地图导航GPS设备使用Dijkstra算法计算从当前位置到目的地的最短或最快路线网络路由OSPF开放最短路径优先协议就是基于Dijkstra算法来计算数据包的最优传输路径通信网络设计规划基站、光纤等网络设施的最优布局机器人路径规划让机器人在有障碍物的环境中找到从起点到终点的最优路径游戏AI计算游戏中角色移动到目标位置的最短路径物流运输优化规划配送路线节省时间和成本八、算法局限性在使用Dijkstra算法之前有几个重要的限制需要了解不能处理负权边如果图中存在权重为负的边Dijkstra算法可能给出错误的结果。对于这种情况应该使用Bellman-Ford算法。只能求单源最短路径Dijkstra算法只能从一个起点出发求到其他所有点的最短路径。不能处理大规模动态图如果图的结构频繁变化如实时路况每次重新运行Dijkstra算法的开销可能很大需要考虑其他动态算法。九、总结让我们用一张流程图来回顾Dijkstra算法的核心流程text初始化 (起点0, 其他∞) ↓ 从未处理节点中 选出距离最小的u ↓ 通过u松弛更新邻居 ↓ 标记u为已处理 ↓ 所有节点已处理 ↙ ↘ 否 是 ↖ ↓ ───── 结束记住三个关键词单源从一个起点出发贪心每次都选当前最近的节点松弛通过已选节点去更新其他节点的距离Dijkstra算法是图论中最基础也最重要的算法之一。掌握了它你就拿到了解决最短路径问题的钥匙。无论是在算法竞赛、面试还是实际项目中它都是一个高频出现的工具。