Dijkstra算法详解：从原理到代码实现，手把手教你求最短路径

1. 项目概述从一张图到一条最优路径最近在后台和社群里看到不少朋友尤其是刚开始接触数据结构与算法、或者正在准备相关面试的同学都在问一个经典问题“给我一张带权重的图我该怎么一步步找出从A点到B点的最短路径”这个问题背后十有八九指的就是狄杰斯特拉算法Dijkstra‘s Algorithm。这算法名气大但初次接触时看着书上那一串串步骤描述和伪代码很容易懵圈——道理好像懂了但手就是不会动。我自己当年学的时候也踩过不少坑比如“为什么这个点不能回头再更新”、“距离表初始化到底该怎么设”、“用优先队列怎么就比普通遍历快那么多”。今天我就用一个具体的、带权重的有向图作为例子抛开教科书式的定义完全从一个实践者的角度带你手把手、一步步“运行”一遍狄杰斯特拉算法。我们的目标很明确给你一张图你不仅能说出算法步骤更能像调试程序一样在纸上或脑子里清晰地模拟出整个求解过程真正理解每一个决策背后的“为什么”。无论你是为了弄懂原理还是为了在编程面试中稳操胜券这篇都能给你提供可直接复现的“操作手册”。我们先明确一下战场。假设我们要求解下图一个典型的有向带权图中从源点A到其他所有顶点的最短路径。图的邻接关系如下你也可以自己画出来边上的数字代表权重/距离A-B权重 4A-C权重 2B-C权重 1B-D权重 5C-B权重 1C-D权重 8C-E权重 10D-E权重 2D-F权重 6E-F权重 2我们的任务就是找出从A出发到B, C, D, E, F每个点的最短距离并且最好能知道具体走的是哪条路径。2. 算法核心思想与准备工作拆解在直接动手算之前我们必须吃透狄杰斯特拉算法的几个核心思想这能帮你从根本上理解后续所有操作而不是死记硬背步骤。2.1 贪心策略与“已确定”集合狄杰斯特拉算法的核心是一种“贪心”策略。什么叫贪心就是在每一步都做出当前看来最好的选择并且这个选择一旦做出就不再回头更改。对应到最短路径问题它的贪心体现在每次都从“尚未确定最短路径的顶点”中选择一个距离源点最近的顶点然后把它标记为“已确定”。为什么可以贪心这基于一个关键前提图中所有边的权重都必须是非负的。如果有负权边这个“当前最近即全局最近”的假设就不成立了贪心就会出错那时就需要用贝尔曼-福特Bellman-Ford等算法。我们例子里的权重都是正数所以狄杰斯特拉完全适用。为了记录状态我们需要两个核心数据结构dist距离表记录从源点A到每个顶点的当前已知最短距离估计值。初始化时A到自己的距离是0到其他所有顶点的距离初始化为“无穷大”在编程里可以用一个很大的数比如float(‘inf’)表示。visited(或finalized) 集合记录哪些顶点的最短距离已经被最终确定不会再被更新。一旦一个顶点进入这个集合算法关于它的工作就结束了。2.2 松弛操作算法的动力引擎光有贪心选择还不够我们需要一个机制来更新和改进其他顶点的距离估计。这个机制就是“松弛”操作。假设我们刚刚确定了顶点u的最短距离dist[u]。现在我们查看u的所有邻居顶点v。如果存在一条边从u到v权重为w那么我们就可以考虑这条新路径A - ... - u - v。这条路径的总长度是dist[u] w。松弛操作就是比较dist[u] w是否小于dist[v]如果是说明我们找到了一条从A到v的更短路径经过u那么就更新dist[v] dist[u] w。同时通常还需要记录v的前驱节点是u以便最后回溯路径。如果否则保持dist[v]不变。你可以把松弛想象成一根橡皮筋。dist[v]是橡皮筋当前的长度。当你发现一条更近的路dist[u] w时就相当于把橡皮筋放松到更短的长度。这个操作是算法不断优化距离估计的关键。2.3 数据结构选择为什么用优先队列在基础的算法描述中每一步需要“从未确定的顶点中选出距离最小的那个”。如果每次都用线性扫描整个dist数组来找最小值算法的时间复杂度会是 O(V²)其中 V 是顶点数。这在顶点很多时效率很低。一个关键的优化是使用优先队列通常是最小堆。我们把未确定的顶点及其当前距离估计值放入最小堆中。这样每次获取距离最小的顶点其时间复杂度是 O(log V)。结合整个算法流程总复杂度可以优化到 O((VE) log V)其中 E 是边数。对于边比较稠密的图提升非常显著。在手动模拟时我们虽然不真的去建堆但要理解这个思想我们总是在关注“当前距离起点最近的那个未处理点”。下面我们就开始手动模拟我会同时展示如何记录前驱节点以还原完整路径。3. 逐步手动演算像计算机一样思考现在我们开始对开头的图进行逐步演算。请准备好纸笔跟着一步步来。初始化dist距离表A:0, B:inf, C:inf, D:inf, E:inf, F:infvisited集合{}空prev前驱表用于还原路径A:None, B:None, C:None, D:None, E:None, F:None第1步选择当前距离最小的未访问顶点。当前所有顶点中dist[A]0最小且 A 未访问。因此选择顶点A。将其加入visited集合{A}。对 A 进行松弛操作检查 A 的所有邻居B, C。对于 Bdist[A] w(A-B) 0 4 4。这小于dist[B]inf。所以更新dist[B]4同时记录prev[B]A。对于 Cdist[A] w(A-C) 0 2 2。这小于dist[C]inf。所以更新dist[C]2同时记录prev[C]A。更新后状态dist:A:0, B:4, C:2, D:inf, E:inf, F:infvisited:{A}prev:B:A, C:A第2步再次选择当前距离最小的未访问顶点。未访问顶点有 B(4), C(2), D(inf), E(inf), F(inf)。最小的是C(距离为2)。选择 C加入visited{A, C}。对 C 进行松弛操作检查 C 的所有邻居B, D, E。注意C-B 的边权重是1。对于 Bdist[C] w(C-B) 2 1 3。这小于dist[B]4。所以更新dist[B]3同时记录prev[B]C注意B的前驱从A变成了C这意味着我们发现了一条更短的路A-C-B。对于 Ddist[C] w(C-D) 2 8 10。这小于dist[D]inf。所以更新dist[D]10记录prev[D]C。对于 Edist[C] w(C-E) 2 10 12。这小于dist[E]inf。所以更新dist[E]12记录prev[E]C。更新后状态dist:A:0, B:3, C:2, D:10, E:12, F:infvisited:{A, C}prev:B:C, C:A, D:C, E:C第3步选择当前距离最小的未访问顶点。未访问顶点有 B(3), D(10), E(12), F(inf)。最小的是B(距离为3)。选择 B加入visited{A, C, B}。对 B 进行松弛操作检查 B 的所有邻居C, D。注意C 已在访问集合但算法仍然会尝试松弛尽管通常因为C已确定而不会改变结果但检查过程会发生。对于 Cdist[B] w(B-C) 3 1 4。这大于dist[C]2不更新。这是一个关键点即使发现另一条路但只要不比已知最短路径短就不更新。这也体现了“已确定”集合的意义——C的距离已是最优。对于 Ddist[B] w(B-D) 3 5 8。这小于dist[D]10。所以更新dist[D]8记录prev[D]B。更新后状态dist:A:0, B:3, C:2, D:8, E:12, F:infvisited:{A, C, B}prev:B:C, C:A, D:B, E:C第4步选择当前距离最小的未访问顶点。未访问顶点有 D(8), E(12), F(inf)。最小的是D(距离为8)。选择 D加入visited{A, C, B, D}。对 D 进行松弛操作检查 D 的所有邻居E, F。对于 Edist[D] w(D-E) 8 2 10。这小于dist[E]12。所以更新dist[E]10记录prev[E]D。对于 Fdist[D] w(D-F) 8 6 14。这小于dist[F]inf。所以更新dist[F]14记录prev[F]D。更新后状态dist:A:0, B:3, C:2, D:8, E:10, F:14visited:{A, C, B, D}prev:B:C, C:A, D:B, E:D, F:D第5步选择当前距离最小的未访问顶点。未访问顶点有 E(10), F(14)。最小的是E(距离为10)。选择 E加入visited{A, C, B, D, E}。对 E 进行松弛操作检查 E 的唯一邻居 F。对于 Fdist[E] w(E-F) 10 2 12。这小于dist[F]14。所以更新dist[F]12记录prev[F]E。更新后状态dist:A:0, B:3, C:2, D:8, E:10, F:12visited:{A, C, B, D, E}prev:B:C, C:A, D:B, E:D, F:E第6步选择最后一个未访问顶点 F。将其加入visited{A, C, B, D, E, F}。对 F 进行松弛操作F 没有出边无需操作。算法结束。所有顶点都已访问完毕。最终结果从 A 到各点的最短距离A:0, B:3, C:2, D:8, E:10, F:12。通过prev表回溯可以得到具体路径A-B: A-C-B (距离 3)A-C: A-C (距离 2)A-D: A-C-B-D (距离 8)A-E: A-C-B-D-E (距离 10)A-F: A-C-B-D-E-F (距离 12)4. 代码实现与关键细节剖析手动推演让我们理解了过程接下来看代码实现。这里我用 Python 给出两种实现一种是便于理解的 O(V²) 基础版本另一种是使用优先队列的高效版本。我会详细注释关键行。4.1 基础版本邻接矩阵 线性扫描这个版本最贴近我们手动计算的过程适合顶点数不多V 1000的情况或者用于理解算法。def dijkstra_basic(graph, src): 使用邻接矩阵和线性扫描实现Dijkstra算法。 graph: 邻接矩阵graph[i][j]表示从i到j的边的权重若无直接边则为无穷大(inf)。 src: 源点索引。 返回: dist列表最短距离prev列表前驱节点。 V len(graph) # 顶点数 INF float(inf) # 初始化 dist [INF] * V visited [False] * V prev [-1] * V # -1表示无前驱 dist[src] 0 # 主循环每次处理一个顶点 for _ in range(V): # 步骤1在未访问顶点中找到dist最小的顶点u u -1 min_dist INF for v in range(V): if not visited[v] and dist[v] min_dist: min_dist dist[v] u v # 如果所有未访问顶点距离都是inf说明剩下的顶点不可达可以提前结束 if u -1: break visited[u] True # 标记为已访问最短距离已确定 # 步骤2对u的所有邻居v进行松弛操作 for v in range(V): # 如果存在边 u-v if graph[u][v] ! INF and not visited[v]: new_dist dist[u] graph[u][v] if new_dist dist[v]: dist[v] new_dist prev[v] u # 记录路径 return dist, prev # 构建我们例子中的图顶点索引A:0, B:1, C:2, D:3, E:4, F:5 INF float(inf) graph [ [0, 4, 2, INF, INF, INF], # A [INF, 0, 1, 5, INF, INF], # B [INF, 1, 0, 8, 10, INF], # C [INF, INF, INF, 0, 2, 6], # D [INF, INF, INF, INF, 0, 2],# E [INF, INF, INF, INF, INF, 0] # F ] dist, prev dijkstra_basic(graph, 0) # srcA print(最短距离:, dist) print(前驱节点:, prev) # 辅助函数根据prev表打印从src到target的路径 def print_path(prev, target): path [] while target ! -1: path.append(chr(target ord(A))) # 转回字母 target prev[target] path.reverse() print(-.join(path)) print(到F的路径:, end ) print_path(prev, 5) # F的索引是5关键细节剖析visited数组的作用它严格区分了“距离已最终确定”和“距离尚在估计”的顶点。一旦一个顶点被标记为visited[u]Truedist[u]就再也不会被更新。这是算法正确性的基石也解释了为什么算法不能处理负权边负权边可能导致已确定的距离被再次减小。prev数组的记录在更新dist[v]的同时更新prev[v]u这相当于在探索时不断优化到达 v 的最佳“上一站”。最终通过反向回溯就能得到完整的最短路径。提前终止条件在寻找最小dist的顶点u时如果发现所有未访问顶点的dist都是无穷大说明源点无法到达剩下的顶点循环可以提前结束这是一个有用的优化。4.2 高效版本邻接表 优先队列/最小堆当顶点数很多时每次线性扫描找最小值会成为瓶颈。使用优先队列Python 的heapq模块可以大幅提升效率。import heapq def dijkstra_heap(graph_adj, src): 使用邻接表和最小堆实现Dijkstra算法。 graph_adj: 邻接表graph_adj[u]是一个列表元素为 (v, weight) 表示边 u-v。 src: 源点索引。 返回: dist列表。 V len(graph_adj) INF float(inf) dist [INF] * V dist[src] 0 # 优先队列元素为 (当前距离, 顶点) pq [(0, src)] while pq: current_dist, u heapq.heappop(pq) # 重要如果弹出的距离大于当前记录的距离说明是旧数据跳过 if current_dist dist[u]: continue # 遍历u的所有邻居 for v, w in graph_adj[u]: new_dist dist[u] w if new_dist dist[v]: dist[v] new_dist heapq.heappush(pq, (new_dist, v)) # 注意这里没有显式的visited数组因为“旧数据跳过”机制起到了类似作用 return dist # 构建邻接表 graph_adj [ [(1, 4), (2, 2)], # A - B, C [(2, 1), (3, 5)], # B - C, D [(1, 1), (3, 8), (4, 10)], # C - B, D, E [(4, 2), (5, 6)], # D - E, F [(5, 2)], # E - F [] # F ] dist_heap dijkstra_heap(graph_adj, 0) print(使用堆的最短距离:, dist_heap)关键细节剖析“延迟删除”与跳过旧数据这是堆优化版本最精妙也最容易出错的地方。当我们更新一个顶点 v 的距离时我们不是去堆里修改旧条目堆不支持高效修改而是直接将新的更小的距离值(new_dist, v)推入堆中。这意味着堆里可能同时存在同一个顶点的多个不同距离的条目。当从堆顶弹出时我们通过if current_dist dist[u]: continue这条语句来判断如果弹出的距离值大于我们当前记录的最短距离dist[u]说明这个条目是“过时”的是在找到更短路径之前推入的直接忽略它。这个机制巧妙地避免了维护复杂的数据结构来删除旧条目。visited数组的消失在堆优化版本中我们通常不再需要显式的visited数组。因为一个顶点一旦从堆中弹出且其距离未被跳过即current_dist dist[u]我们就对其所有出边进行松弛。之后即使堆中还有该顶点的旧条目也会被上面的“跳过”机制过滤掉。这等效于该顶点已被“访问”并确定。但要注意一个顶点可能会被处理多次如果多次更新距离但只有最后一次距离最短的那次是有效的。时间复杂度每个顶点最多入堆一次实际上可能多次但每条边最多引发一次入堆操作每次堆操作是 O(log V)。因此总时间复杂度约为 O((VE) log V)在稀疏图E ~ V上接近 O(V log V)比 O(V²) 好得多。5. 常见问题、陷阱与实战心得在实际编码和面试中单纯会写算法还不够理解这些边角情况和陷阱才能让你真正过关。5.1 负权边为什么是禁忌这是狄杰斯特拉算法最著名的限制。我们通过一个极简例子来看图中有三个点 A, B, C。边为 A-B (1), A-C (4), B-C (-2)。求 A 到 C 的最短路径。正确路径A-B-C距离 1 (-2) -1。狄杰斯特拉执行选 A松弛得 dist[B]1, dist[C]4。选 B距离1松弛 B-Cnew_dist 1 (-2) -1更新 dist[C]-1。选 C结束。结果 dist[C]-1看起来对了陷阱在于狄杰斯特拉假设“已访问集合中的顶点距离不再改变”。在第2步我们确定了 B 的距离为1。但如果存在负权边从已访问顶点这里是B出发可能通过一个环比如B-C-...-B再回到自己使自己的距离变得更小。这就破坏了贪心选择的基础。在上例中虽然结果碰巧对了但逻辑已不严谨。对于包含负权边的图应使用贝尔曼-福特Bellman-Ford或SPFA算法。注意如果图中所有边的权重都是非负的那么狄杰斯特拉算法找到的路径一定是最短的并且每个顶点的最短距离在第一次被访问从堆中弹出有效条目时就确定了。5.2 路径还原与多条等长最短路径我们的代码记录了prev数组它只保存了“一条”最短路径的前驱。如果存在多条长度相同的最短路径上述代码只会找到其中一条具体是哪条取决于松弛操作的顺序。如果需要找出所有最短路径则需要将prev改为一个列表的数组prev[v] []当new_dist dist[v]时将u也加入prev[v]的列表中。最后通过回溯如DFS来生成所有路径。5.3 初始化与不可达顶点初始化时将源点距离设为0其他点设为无穷大INF。在算法结束后如果某个顶点的dist值仍然是INF则意味着从源点无法到达该顶点。在实际应用中如地图导航需要妥善处理这种情况给用户一个“无法到达”的提示而不是输出一个极大的数字。5.4 堆优化版本中的“距离更新”陷阱在堆优化代码中我写了if new_dist dist[v]:才更新和入堆。有些初学者会写成if new_dist dist[v]:然后在等于时也入堆。这在功能上没错但会向堆中推入大量冗余的、距离相等的条目虽然不影响正确性但会轻微影响性能。严格的小于判断是更标准的写法。5.5 稠密图与稀疏图的实现选择稠密图E ≈ V²例如完全图。此时使用邻接矩阵和 O(V²) 的简单实现可能更简单甚至因为常数小而与堆优化版本性能相差不大。优先队列的 O((VE)logV) 会退化成 O(V² logV)logV 因子可能使速度变慢。稀疏图E V²例如道路网络、社交网络。这是堆优化版本的主场O((VE)logV) 优势明显。务必使用邻接表存储图。一个实战心得在面试或竞赛中除非特别说明如顶点数极少否则默认使用堆优化邻接表的实现。这是最稳妥、最通用的选择。同时一定要能说清楚“延迟删除”和跳过旧数据的原理这是考察你是否真懂的关键。6. 算法扩展与应用场景联想理解了基础的单源最短路径我们可以看看它的变体和应用这能帮你建立更完整的知识图谱。6.1 变体目标点已知的提前终止如果我们只关心从源点s到某一个特定目标点t的最短路径可以在算法中增加一个判断当t被从优先队列中弹出即其最短距离确定时立即终止算法。因为狄杰斯特拉是贪心按距离从小到大确定点的所以当t被弹出时它的距离一定已经是最短的后续的点距离更大不可能出现在 s 到 t 的更短路径上。这可以节省大量计算。6.2 应用场景举例网络路由路由器中使用的 OSPF 协议其核心就是狄杰斯特拉算法用于计算一个路由器到网络中所有其他路由器的最短路径这里“距离”可能是延迟、跳数等。地图导航这是最直观的应用。将交叉口视为顶点道路视为边通行时间或距离视为权重求两点间最快或最短路线。实际的地图引擎如谷歌地图会使用更复杂的变种如 A* 算法它加入了启发式估计来加速但其基础仍是狄杰斯特拉。社交网络“六度空间”可以将人与人之间的关系视为无权图或等权图狄杰斯特拉算法可以找出一个人到另一个人的最短关系链最少中间人。此时权重可视为1。项目关键路径分析在某些 PERT 图或关键路径法分析中经过适当转换如对时间取负也可以利用最短路径算法来求解。6.3 从狄杰斯特拉到其他算法贝尔曼-福特算法可以处理负权边并能检测负权环。时间复杂度 O(VE)比狄杰斯特拉慢但适用范围更广。可以将其理解为对图中所有边进行 V-1 轮松弛操作。弗洛伊德算法用于求所有顶点对之间的最短路径。基于动态规划代码极其简洁三重循环时间复杂度 O(V³)适合顶点数不多的情况。A搜索算法*在狄杰斯特拉的基础上增加了一个启发式函数来预估从当前点到目标点的代价从而优先搜索更有希望的方向。这是地图导航等场景的常用高效算法。手动模拟一遍狄杰斯特拉算法再亲手实现它最后再思考这些边界情况和应用你对它的理解就不再是浮于表面的几个名词而是有了扎实的、可操作的认知。下次再遇到最短路径问题你就能清晰地知道该用什么工具以及如何正确地使用它了。