1. 从一个找路问题说起Dijkstra到底在解决什么很多人第一次接触Dijkstra算法是在数据结构或者图论的课上老师画一张带权重的图然后让你从A点开始一步步标号最后得出到每个点的最短距离。当时觉得好像也不难但真到自己写代码的时候就发现各种问题冒出来了优先队列怎么用为什么不能处理负权边松弛操作到底在干什么路径怎么还原我当初也是这样课本上的伪代码看懂了但一落到实际代码就卡壳。后来做了几个路径规划相关的项目才慢慢把这块吃透。这篇文章就把我对Dijkstra算法的理解完整地梳理一遍从核心思想到代码实现从手算模拟到工程优化尽量做到简单易懂这四个字。Dijkstra算法本质上解决的是单源最短路径问题给定一个带权图和一个起点求出起点到其他所有节点的最短路径长度。它的应用场景非常广比如地图导航中的路线规划、网络路由中的数据包转发、游戏中的AI寻路等等。只要你能把问题抽象成节点带权边的模型Dijkstra就能派上用场。这篇文章适合谁看如果你是正在学算法的学生或者工作中需要用到路径规划的开发者又或者你只是想把Dijkstra彻底搞明白那这篇内容应该能帮到你。我会从最基础的概念讲起逐步深入到代码实现和优化技巧中间穿插我自己踩过的坑和总结的经验。2. 核心思想拆解贪心策略为什么能work2.1 用生活场景理解Dijkstra的贪心逻辑Dijkstra的核心是贪心策略。什么叫贪心就是每一步都选当前看起来最优的那个选项然后基于这个选择继续往下走。举个生活中的例子。假设你要从家出发去城市的各个地方你手里有一张地图上面标了每两个地点之间的距离。你想知道从家到每个地方的最短距离。Dijkstra的做法是这样的一开始你只知道家到自己距离是0到其他地方的距离都未知记为无穷大。你从未确定最短距离的地点中选一个当前已知距离最小的。显然一开始就是家自己。以这个点为跳板看看通过它能不能让其他地点的距离变短。比如家到超市直接走是10公里但家先到学校再超市是6公里那就更新超市的距离为6。重复第2步和第3步直到所有地点的最短距离都确定。这个过程中每次选的都是当前已知距离最小的那个点这就是贪心的体现。那为什么这样做是对的关键在于边权非负这个前提。2.2 为什么边权不能为负一个反例就够了如果图中有负权边Dijkstra的贪心策略就会失效。我举一个具体的例子来说明。假设有三个节点A、B、C。A到B的边权是1A到C的边权是5B到C的边权是-10。按照Dijkstra的流程第一步确定A的最短距离为0。第二步从B和C中选距离最小的。B的距离是1C的距离是5所以选B确定B的最短距离为1。第三步以B为跳板更新C的距离。通过B到C的距离是1(-10)-9比原来的5小所以C的距离更新为-9。第四步确定C的最短距离为-9。看起来没问题但问题在于如果存在一条路径A→C→B而C到B的边权也是负的那B的最短距离可能在确定之后还能被更新这就和确定这个词矛盾了。Dijkstra的核心假设是一旦一个节点被选为当前距离最小并确定下来它的最短距离就不会再变了。这个假设在边权非负时成立因为任何绕路都会增加总距离但有了负权边绕路反而可能减少总距离假设就不成立了。注意如果你的图里存在负权边应该考虑Bellman-Ford算法或者SPFA算法它们能处理负权边但时间复杂度会更高。2.3 松弛操作Dijkstra的心跳Dijkstra算法中最核心的操作叫松弛Relaxation。这个词听起来有点抽象但理解起来很简单。假设我们已知起点到节点u的最短距离是dist[u]u到v有一条边权重是w。那么从起点经过u到v的距离就是dist[u] w。如果这个值比当前记录的dist[v]小我们就更新dist[v]这就叫松弛。你可以把松弛想象成一根绷紧的橡皮筋。dist[v]初始是无穷大相当于橡皮筋拉得很长。每次找到一条更短的路径橡皮筋就松一点直到最后绷到最短的那个位置。松弛操作的伪代码大概是这样if dist[u] w dist[v]: dist[v] dist[u] w prev[v] u # 记录前驱节点用于还原路径这个操作看起来简单但它是整个算法的基石。每一次从优先队列中取出一个节点都要对它所有的邻居尝试松弛。如果松弛成功就把邻居加入优先队列或者更新它在队列中的值。2.4 朴素实现 vs 优先队列优化差距有多大Dijkstra有两种常见的实现方式朴素实现和优先队列优化。朴素实现的思路是用一个数组记录所有未访问节点的距离每次线性扫描找到距离最小的那个。时间复杂度是O(V²)其中V是节点数。这种实现适合稠密图也就是边数接近V²的图。优先队列优化的思路是用一个最小堆来维护未访问节点的距离每次从堆顶取出距离最小的节点。时间复杂度是O((VE)logV)其中E是边数。这种实现适合稀疏图也就是边数远小于V²的图。我实测下来的感受是对于节点数在1000以内的图两种实现的差距不太明显但当节点数上万时优先队列优化的优势就非常明显了。下面这张表可以帮你快速判断该用哪种实现方式时间复杂度适用场景代码复杂度朴素实现O(V²)稠密图节点数少低优先队列优化O((VE)logV)稀疏图节点数多中斐波那契堆优化O(EVlogV)理论最优实际少用高实操心得大多数工程场景下优先队列优化已经足够好了。斐波那契堆虽然理论复杂度更低但常数因子大实际性能未必更好而且实现复杂不建议新手尝试。3. 手把手实现从伪代码到可运行代码3.1 图的存储方式邻接矩阵还是邻接表在写代码之前首先要决定怎么存图。常见的方式有两种邻接矩阵和邻接表。邻接矩阵用一个二维数组graph[i][j]表示节点i到节点j的边权。如果两个节点之间没有边就设为无穷大。这种方式的优点是查询两点之间是否有边非常快O(1)时间缺点是空间复杂度是O(V²)对于稀疏图来说很浪费。邻接表用数组链表或者vector的方式存储每个节点的邻居。graph[i]是一个列表里面存着所有从i出发的边每条边包含目标节点和权重。空间复杂度是O(VE)对于稀疏图非常友好。我个人的选择习惯是如果节点数不超过1000直接用邻接矩阵写起来简单如果节点数很大或者边很稀疏就用邻接表。下面用Python演示邻接表的构建# 邻接表构建示例 n 5 # 节点数 edges [ (0, 1, 10), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 1, 4), (2, 3, 8), (2, 4, 2), (3, 4, 7), (4, 3, 9) ] graph [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w))这段代码构建了一个有5个节点、9条边的有向图。graph[u]里面存的是所有从u出发的边每条边是一个(目标节点, 权重)的元组。3.2 优先队列优化的完整实现下面是一个完整的Dijkstra实现用优先队列优化附带路径还原功能import heapq def dijkstra(graph, start): graph: 邻接表graph[u] [(v, w), ...] start: 起点 返回: dist数组和prev数组 n len(graph) INF float(inf) dist [INF] * n prev [-1] * n dist[start] 0 # 优先队列存储(距离, 节点) pq [(0, start)] visited [False] * n while pq: d, u heapq.heappop(pq) # 如果这个节点已经处理过跳过 if visited[u]: continue visited[u] True # 遍历所有邻居尝试松弛 for v, w in graph[u]: if not visited[v] and dist[u] w dist[v]: dist[v] dist[u] w prev[v] u heapq.heappush(pq, (dist[v], v)) return dist, prev def get_path(prev, start, end): 还原从start到end的路径 path [] cur end while cur ! -1: path.append(cur) cur prev[cur] path.reverse() if path[0] start: return path return [] # 不可达这段代码有几个关键点需要说明第一visited数组的作用是标记已经确定最短距离的节点。为什么需要它因为优先队列中可能存在同一个节点的多个条目每次松弛成功都会push一个新的如果不加判断同一个节点可能被处理多次虽然不影响正确性但会浪费时间。第二heapq是Python内置的最小堆实现。它存储的是(距离, 节点)的元组Python会比较元组的第一个元素所以距离最小的会排在堆顶。第三路径还原通过prev数组实现。每次松弛成功时记录prev[v] u表示v的最短路径是从u过来的。最后从终点往回追溯就能得到完整路径。3.3 手算模拟用一个具体例子走一遍光看代码可能还不够直观我们用一个具体的图来手动模拟一遍Dijkstra的执行过程。假设有5个节点编号0到4边的情况如下0 - 1: 10 0 - 2: 3 1 - 2: 1 1 - 3: 2 2 - 1: 4 2 - 3: 8 2 - 4: 2 3 - 4: 7 4 - 3: 9起点是0。初始化dist [0, ∞, ∞, ∞, ∞]优先队列 [(0, 0)]。第一轮取出(0, 0)标记0为已访问。遍历0的邻居到101010 ∞更新dist[1]10prev[1]0入队(10, 1)到2033 ∞更新dist[2]3prev[2]0入队(3, 2)此时dist [0, 10, 3, ∞, ∞]队列 [(3, 2), (10, 1)]。第二轮取出(3, 2)标记2为已访问。遍历2的邻居到1347 10更新dist[1]7prev[1]2入队(7, 1)到33811 ∞更新dist[3]11prev[3]2入队(11, 3)到4325 ∞更新dist[4]5prev[4]2入队(5, 4)此时dist [0, 7, 3, 11, 5]队列 [(5, 4), (7, 1), (10, 1), (11, 3)]。第三轮取出(5, 4)标记4为已访问。遍历4的邻居到35914 11不更新。此时dist不变队列 [(7, 1), (10, 1), (11, 3)]。第四轮取出(7, 1)标记1为已访问。遍历1的邻居到2已访问跳过到3729 11更新dist[3]9prev[3]1入队(9, 3)此时dist [0, 7, 3, 9, 5]队列 [(9, 3), (10, 1), (11, 3)]。第五轮取出(9, 3)标记3为已访问。遍历3的邻居到4已访问跳过队列中剩下的(10, 1)和(11, 3)对应的节点都已经访问过了会被跳过。最终结果dist [0, 7, 3, 9, 5]。从0到4的最短距离是5路径是0→2→4。这个手算过程建议你自己在纸上画一遍画完之后对Dijkstra的理解会深刻很多。3.4 路径还原的细节与常见错误路径还原看起来简单但有几个容易出错的地方。第一个坑是prev数组的初始化。我习惯初始化为-1表示没有前驱。但在还原路径时如果起点到终点不可达追溯过程中会遇到-1这时候需要判断路径是否有效。第二个坑是路径方向。从终点往回追溯得到的路径是反的需要reverse一下。这个虽然简单但写代码时容易忘。第三个坑是多条最短路径。如果存在多条距离相同的最短路径Dijkstra只会记录其中一条取决于松弛的顺序。如果你需要所有最短路径那就不能只用prev数组需要用列表记录所有可能的前驱。实操心得在实际项目中我通常会把dist和prev封装成一个结果对象返回这样调用方用起来更方便。另外如果只需要最短距离不需要路径可以省掉prev数组节省一点空间。4. 工程实践中的优化与避坑指南4.1 性能优化什么时候该考虑更快的方案虽然优先队列优化的Dijkstra已经能应付大多数场景但在一些极端情况下你可能需要更快的方案。场景一只需要起点到终点的最短路径不需要到所有点的。这时候可以用A算法它引入了一个启发式函数来引导搜索方向通常比Dijkstra快很多。A的核心思想是优先队列的排序依据从dist[u]变成dist[u] h(u)其中h(u)是u到终点的估计距离。只要h(u)不超过真实距离A*就能保证找到最短路径。场景二图非常大但只需要近似最短路径。这时候可以考虑一些近似算法比如Landmark-based的算法或者收缩层次Contraction Hierarchies。这些算法在导航系统中很常用能在毫秒级处理全国级别的路网。场景三需要频繁查询不同起点的最短路径。如果图的结构不变只是查询的起点不同可以预处理一些数据结构比如所有点对的最短路径Floyd-Warshall算法或者建立一些索引来加速查询。不过话说回来大多数业务场景下优先队列优化的Dijkstra已经够用了。我做过一个节点数约5万、边数约20万的路网查询用优先队列优化的Dijkstra单次查询大概在几十毫秒级别完全能满足实时性要求。4.2 常见问题排查速查表在实际写Dijkstra的过程中我遇到过各种各样的问题。下面整理了一个速查表方便你快速定位问题问题现象可能原因排查方法结果偏大松弛条件写反了检查是否用了而不是结果偏小负权边导致检查图中是否有负权边死循环优先队列没有去重加visited数组或判断距离是否过期路径还原为空prev数组没更新检查松弛成功时是否更新了prev内存超限邻接矩阵太大改用邻接表存储运行超时用了朴素实现改用优先队列优化其中最常见的问题是优先队列没有去重导致死循环。这个问题的根源是每次松弛成功都会往队列里push一个新条目如果不加控制同一个节点可能被反复处理。解决方法有两种一是加visited数组处理过的节点直接跳过二是在取出节点时判断if d dist[u]: continue这样过期的条目会被忽略。4.3 边界情况处理空图、单节点、不可达写算法的时候边界情况往往是最容易出bug的地方。Dijkstra也不例外。空图如果图里没有节点直接返回空结果就行。但要注意有些实现会在初始化时访问graph[start]如果start越界就会报错。所以最好先判断一下节点数。单节点如果图里只有一个节点最短距离就是0路径就是它自己。这个情况一般不会出问题但如果你在还原路径时没有处理好可能会返回空列表。不可达节点如果起点到某个节点没有路径dist值会保持为无穷大。在输出结果时需要把无穷大转换成一个可读的表示比如-1或者不可达。起点就是终点这种情况最短距离是0路径是只包含起点的一个列表。有些实现会返回空列表这是不对的需要注意。注意在工程代码中我建议对输入做基本的校验比如检查起点是否在合法范围内图是否为空等。这些校验虽然简单但能避免很多莫名其妙的bug。4.4 与其他最短路径算法的对比选型Dijkstra不是唯一的最短路径算法不同的场景适合不同的算法。下面做一个简单的对比算法适用场景时间复杂度能否处理负权边Dijkstra单源非负权O((VE)logV)否Bellman-Ford单源可负权O(VE)是SPFA单源可负权平均O(E)最坏O(VE)是Floyd-Warshall多源O(V³)是A*单源单终点取决于启发函数否选择建议如果没有负权边优先用Dijkstra如果有负权边用Bellman-Ford或SPFA如果需要所有点对的最短路径且节点数不多用Floyd-Warshall如果只需要起点到终点的路径且能设计出好的启发函数用A*。我个人的经验是Dijkstra是使用频率最高的基本上能覆盖80%以上的场景。剩下的20%里A*和Floyd-Warshall各占一半。Bellman-Ford和SPFA用得比较少主要是因为大多数实际问题的边权都是非负的。4.5 实际项目中的应用案例最后分享一个我在实际项目中的应用案例。之前做过一个物流配送的路径规划系统需要计算配送中心到各个配送点的最短路径。图的结构是节点是配送点和路口边是道路权重是道路长度或者预计通行时间。这个项目的节点数大概在3万左右边数在10万左右。一开始用的是朴素实现单次查询要好几秒完全没法用。后来改成优先队列优化单次查询降到了50毫秒以内。再后来发现很多查询的起点是固定的都是配送中心就做了一些预处理把常用起点的结果缓存起来进一步降到了10毫秒以内。这个项目让我深刻体会到算法本身的优化很重要但结合业务特点做针对性的优化同样重要。有时候一个简单的缓存就能带来数量级的提升。另外一个坑是权重的动态变化。道路的通行时间会随着交通状况变化如果每次变化都重新计算所有路径开销太大。我们的做法是只对受影响的区域重新计算其他区域沿用缓存结果。这个策略虽然不能保证全局最优但在实际业务中已经足够好了。5. 写在最后几个让我少走弯路的小技巧Dijkstra这个算法我前前后后学了三四遍每次都有新的理解。最开始是死记硬背伪代码后来是照着模板写代码再后来是理解背后的贪心思想和松弛操作最后是在实际项目中不断调优。如果你也在学这个算法我建议你不要只停留在能写出来的层面多问问自己为什么这样写是对的、换个场景还适用吗。几个具体的小建议第一手算模拟至少走两遍一遍简单的图一遍稍微复杂的图这样能帮你建立直觉第二代码实现至少写两遍一遍朴素版一遍优先队列版对比一下差异第三找一个实际的小项目练手比如做一个简单的地图寻路Demo把算法用起来比单纯刷题效果好得多。还有一个容易被忽略的点测试用例的设计。很多人写完Dijkstra只测一个简单的图就完事了但实际上边界情况才是最容易出bug的地方。我通常会准备这样几组测试单节点图、两点一边的图、有环的图、不可达的图、多条最短路径的图。这几组测下来基本能覆盖大多数问题。如果你在实现过程中遇到了什么奇怪的问题欢迎一起交流。算法这东西一个人闷头想容易钻牛角尖多和别人讨论讨论往往能豁然开朗。 
长河君 · 2026/10/15 1:19:09 · 阅读 1.2k Dijkstra算法从入门到精通：贪心策略、优先队列优化与工程实践
1. 从一个找路问题说起Dijkstra到底在解决什么很多人第一次接触Dijkstra算法是在数据结构或者图论的课上老师画一张带权重的图然后让你从A点开始一步步标号最后得出到每个点的最短距离。当时觉得好像也不难但真到自己写代码的时候就发现各种问题冒出来了优先队列怎么用为什么不能处理负权边松弛操作到底在干什么路径怎么还原我当初也是这样课本上的伪代码看懂了但一落到实际代码就卡壳。后来做了几个路径规划相关的项目才慢慢把这块吃透。这篇文章就把我对Dijkstra算法的理解完整地梳理一遍从核心思想到代码实现从手算模拟到工程优化尽量做到简单易懂这四个字。Dijkstra算法本质上解决的是单源最短路径问题给定一个带权图和一个起点求出起点到其他所有节点的最短路径长度。它的应用场景非常广比如地图导航中的路线规划、网络路由中的数据包转发、游戏中的AI寻路等等。只要你能把问题抽象成节点带权边的模型Dijkstra就能派上用场。这篇文章适合谁看如果你是正在学算法的学生或者工作中需要用到路径规划的开发者又或者你只是想把Dijkstra彻底搞明白那这篇内容应该能帮到你。我会从最基础的概念讲起逐步深入到代码实现和优化技巧中间穿插我自己踩过的坑和总结的经验。2. 核心思想拆解贪心策略为什么能work2.1 用生活场景理解Dijkstra的贪心逻辑Dijkstra的核心是贪心策略。什么叫贪心就是每一步都选当前看起来最优的那个选项然后基于这个选择继续往下走。举个生活中的例子。假设你要从家出发去城市的各个地方你手里有一张地图上面标了每两个地点之间的距离。你想知道从家到每个地方的最短距离。Dijkstra的做法是这样的一开始你只知道家到自己距离是0到其他地方的距离都未知记为无穷大。你从未确定最短距离的地点中选一个当前已知距离最小的。显然一开始就是家自己。以这个点为跳板看看通过它能不能让其他地点的距离变短。比如家到超市直接走是10公里但家先到学校再超市是6公里那就更新超市的距离为6。重复第2步和第3步直到所有地点的最短距离都确定。这个过程中每次选的都是当前已知距离最小的那个点这就是贪心的体现。那为什么这样做是对的关键在于边权非负这个前提。2.2 为什么边权不能为负一个反例就够了如果图中有负权边Dijkstra的贪心策略就会失效。我举一个具体的例子来说明。假设有三个节点A、B、C。A到B的边权是1A到C的边权是5B到C的边权是-10。按照Dijkstra的流程第一步确定A的最短距离为0。第二步从B和C中选距离最小的。B的距离是1C的距离是5所以选B确定B的最短距离为1。第三步以B为跳板更新C的距离。通过B到C的距离是1(-10)-9比原来的5小所以C的距离更新为-9。第四步确定C的最短距离为-9。看起来没问题但问题在于如果存在一条路径A→C→B而C到B的边权也是负的那B的最短距离可能在确定之后还能被更新这就和确定这个词矛盾了。Dijkstra的核心假设是一旦一个节点被选为当前距离最小并确定下来它的最短距离就不会再变了。这个假设在边权非负时成立因为任何绕路都会增加总距离但有了负权边绕路反而可能减少总距离假设就不成立了。注意如果你的图里存在负权边应该考虑Bellman-Ford算法或者SPFA算法它们能处理负权边但时间复杂度会更高。2.3 松弛操作Dijkstra的心跳Dijkstra算法中最核心的操作叫松弛Relaxation。这个词听起来有点抽象但理解起来很简单。假设我们已知起点到节点u的最短距离是dist[u]u到v有一条边权重是w。那么从起点经过u到v的距离就是dist[u] w。如果这个值比当前记录的dist[v]小我们就更新dist[v]这就叫松弛。你可以把松弛想象成一根绷紧的橡皮筋。dist[v]初始是无穷大相当于橡皮筋拉得很长。每次找到一条更短的路径橡皮筋就松一点直到最后绷到最短的那个位置。松弛操作的伪代码大概是这样if dist[u] w dist[v]: dist[v] dist[u] w prev[v] u # 记录前驱节点用于还原路径这个操作看起来简单但它是整个算法的基石。每一次从优先队列中取出一个节点都要对它所有的邻居尝试松弛。如果松弛成功就把邻居加入优先队列或者更新它在队列中的值。2.4 朴素实现 vs 优先队列优化差距有多大Dijkstra有两种常见的实现方式朴素实现和优先队列优化。朴素实现的思路是用一个数组记录所有未访问节点的距离每次线性扫描找到距离最小的那个。时间复杂度是O(V²)其中V是节点数。这种实现适合稠密图也就是边数接近V²的图。优先队列优化的思路是用一个最小堆来维护未访问节点的距离每次从堆顶取出距离最小的节点。时间复杂度是O((VE)logV)其中E是边数。这种实现适合稀疏图也就是边数远小于V²的图。我实测下来的感受是对于节点数在1000以内的图两种实现的差距不太明显但当节点数上万时优先队列优化的优势就非常明显了。下面这张表可以帮你快速判断该用哪种实现方式时间复杂度适用场景代码复杂度朴素实现O(V²)稠密图节点数少低优先队列优化O((VE)logV)稀疏图节点数多中斐波那契堆优化O(EVlogV)理论最优实际少用高实操心得大多数工程场景下优先队列优化已经足够好了。斐波那契堆虽然理论复杂度更低但常数因子大实际性能未必更好而且实现复杂不建议新手尝试。3. 手把手实现从伪代码到可运行代码3.1 图的存储方式邻接矩阵还是邻接表在写代码之前首先要决定怎么存图。常见的方式有两种邻接矩阵和邻接表。邻接矩阵用一个二维数组graph[i][j]表示节点i到节点j的边权。如果两个节点之间没有边就设为无穷大。这种方式的优点是查询两点之间是否有边非常快O(1)时间缺点是空间复杂度是O(V²)对于稀疏图来说很浪费。邻接表用数组链表或者vector的方式存储每个节点的邻居。graph[i]是一个列表里面存着所有从i出发的边每条边包含目标节点和权重。空间复杂度是O(VE)对于稀疏图非常友好。我个人的选择习惯是如果节点数不超过1000直接用邻接矩阵写起来简单如果节点数很大或者边很稀疏就用邻接表。下面用Python演示邻接表的构建# 邻接表构建示例 n 5 # 节点数 edges [ (0, 1, 10), (0, 2, 3), (1, 2, 1), (1, 3, 2), (2, 1, 4), (2, 3, 8), (2, 4, 2), (3, 4, 7), (4, 3, 9) ] graph [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w))这段代码构建了一个有5个节点、9条边的有向图。graph[u]里面存的是所有从u出发的边每条边是一个(目标节点, 权重)的元组。3.2 优先队列优化的完整实现下面是一个完整的Dijkstra实现用优先队列优化附带路径还原功能import heapq def dijkstra(graph, start): graph: 邻接表graph[u] [(v, w), ...] start: 起点 返回: dist数组和prev数组 n len(graph) INF float(inf) dist [INF] * n prev [-1] * n dist[start] 0 # 优先队列存储(距离, 节点) pq [(0, start)] visited [False] * n while pq: d, u heapq.heappop(pq) # 如果这个节点已经处理过跳过 if visited[u]: continue visited[u] True # 遍历所有邻居尝试松弛 for v, w in graph[u]: if not visited[v] and dist[u] w dist[v]: dist[v] dist[u] w prev[v] u heapq.heappush(pq, (dist[v], v)) return dist, prev def get_path(prev, start, end): 还原从start到end的路径 path [] cur end while cur ! -1: path.append(cur) cur prev[cur] path.reverse() if path[0] start: return path return [] # 不可达这段代码有几个关键点需要说明第一visited数组的作用是标记已经确定最短距离的节点。为什么需要它因为优先队列中可能存在同一个节点的多个条目每次松弛成功都会push一个新的如果不加判断同一个节点可能被处理多次虽然不影响正确性但会浪费时间。第二heapq是Python内置的最小堆实现。它存储的是(距离, 节点)的元组Python会比较元组的第一个元素所以距离最小的会排在堆顶。第三路径还原通过prev数组实现。每次松弛成功时记录prev[v] u表示v的最短路径是从u过来的。最后从终点往回追溯就能得到完整路径。3.3 手算模拟用一个具体例子走一遍光看代码可能还不够直观我们用一个具体的图来手动模拟一遍Dijkstra的执行过程。假设有5个节点编号0到4边的情况如下0 - 1: 10 0 - 2: 3 1 - 2: 1 1 - 3: 2 2 - 1: 4 2 - 3: 8 2 - 4: 2 3 - 4: 7 4 - 3: 9起点是0。初始化dist [0, ∞, ∞, ∞, ∞]优先队列 [(0, 0)]。第一轮取出(0, 0)标记0为已访问。遍历0的邻居到101010 ∞更新dist[1]10prev[1]0入队(10, 1)到2033 ∞更新dist[2]3prev[2]0入队(3, 2)此时dist [0, 10, 3, ∞, ∞]队列 [(3, 2), (10, 1)]。第二轮取出(3, 2)标记2为已访问。遍历2的邻居到1347 10更新dist[1]7prev[1]2入队(7, 1)到33811 ∞更新dist[3]11prev[3]2入队(11, 3)到4325 ∞更新dist[4]5prev[4]2入队(5, 4)此时dist [0, 7, 3, 11, 5]队列 [(5, 4), (7, 1), (10, 1), (11, 3)]。第三轮取出(5, 4)标记4为已访问。遍历4的邻居到35914 11不更新。此时dist不变队列 [(7, 1), (10, 1), (11, 3)]。第四轮取出(7, 1)标记1为已访问。遍历1的邻居到2已访问跳过到3729 11更新dist[3]9prev[3]1入队(9, 3)此时dist [0, 7, 3, 9, 5]队列 [(9, 3), (10, 1), (11, 3)]。第五轮取出(9, 3)标记3为已访问。遍历3的邻居到4已访问跳过队列中剩下的(10, 1)和(11, 3)对应的节点都已经访问过了会被跳过。最终结果dist [0, 7, 3, 9, 5]。从0到4的最短距离是5路径是0→2→4。这个手算过程建议你自己在纸上画一遍画完之后对Dijkstra的理解会深刻很多。3.4 路径还原的细节与常见错误路径还原看起来简单但有几个容易出错的地方。第一个坑是prev数组的初始化。我习惯初始化为-1表示没有前驱。但在还原路径时如果起点到终点不可达追溯过程中会遇到-1这时候需要判断路径是否有效。第二个坑是路径方向。从终点往回追溯得到的路径是反的需要reverse一下。这个虽然简单但写代码时容易忘。第三个坑是多条最短路径。如果存在多条距离相同的最短路径Dijkstra只会记录其中一条取决于松弛的顺序。如果你需要所有最短路径那就不能只用prev数组需要用列表记录所有可能的前驱。实操心得在实际项目中我通常会把dist和prev封装成一个结果对象返回这样调用方用起来更方便。另外如果只需要最短距离不需要路径可以省掉prev数组节省一点空间。4. 工程实践中的优化与避坑指南4.1 性能优化什么时候该考虑更快的方案虽然优先队列优化的Dijkstra已经能应付大多数场景但在一些极端情况下你可能需要更快的方案。场景一只需要起点到终点的最短路径不需要到所有点的。这时候可以用A算法它引入了一个启发式函数来引导搜索方向通常比Dijkstra快很多。A的核心思想是优先队列的排序依据从dist[u]变成dist[u] h(u)其中h(u)是u到终点的估计距离。只要h(u)不超过真实距离A*就能保证找到最短路径。场景二图非常大但只需要近似最短路径。这时候可以考虑一些近似算法比如Landmark-based的算法或者收缩层次Contraction Hierarchies。这些算法在导航系统中很常用能在毫秒级处理全国级别的路网。场景三需要频繁查询不同起点的最短路径。如果图的结构不变只是查询的起点不同可以预处理一些数据结构比如所有点对的最短路径Floyd-Warshall算法或者建立一些索引来加速查询。不过话说回来大多数业务场景下优先队列优化的Dijkstra已经够用了。我做过一个节点数约5万、边数约20万的路网查询用优先队列优化的Dijkstra单次查询大概在几十毫秒级别完全能满足实时性要求。4.2 常见问题排查速查表在实际写Dijkstra的过程中我遇到过各种各样的问题。下面整理了一个速查表方便你快速定位问题问题现象可能原因排查方法结果偏大松弛条件写反了检查是否用了而不是结果偏小负权边导致检查图中是否有负权边死循环优先队列没有去重加visited数组或判断距离是否过期路径还原为空prev数组没更新检查松弛成功时是否更新了prev内存超限邻接矩阵太大改用邻接表存储运行超时用了朴素实现改用优先队列优化其中最常见的问题是优先队列没有去重导致死循环。这个问题的根源是每次松弛成功都会往队列里push一个新条目如果不加控制同一个节点可能被反复处理。解决方法有两种一是加visited数组处理过的节点直接跳过二是在取出节点时判断if d dist[u]: continue这样过期的条目会被忽略。4.3 边界情况处理空图、单节点、不可达写算法的时候边界情况往往是最容易出bug的地方。Dijkstra也不例外。空图如果图里没有节点直接返回空结果就行。但要注意有些实现会在初始化时访问graph[start]如果start越界就会报错。所以最好先判断一下节点数。单节点如果图里只有一个节点最短距离就是0路径就是它自己。这个情况一般不会出问题但如果你在还原路径时没有处理好可能会返回空列表。不可达节点如果起点到某个节点没有路径dist值会保持为无穷大。在输出结果时需要把无穷大转换成一个可读的表示比如-1或者不可达。起点就是终点这种情况最短距离是0路径是只包含起点的一个列表。有些实现会返回空列表这是不对的需要注意。注意在工程代码中我建议对输入做基本的校验比如检查起点是否在合法范围内图是否为空等。这些校验虽然简单但能避免很多莫名其妙的bug。4.4 与其他最短路径算法的对比选型Dijkstra不是唯一的最短路径算法不同的场景适合不同的算法。下面做一个简单的对比算法适用场景时间复杂度能否处理负权边Dijkstra单源非负权O((VE)logV)否Bellman-Ford单源可负权O(VE)是SPFA单源可负权平均O(E)最坏O(VE)是Floyd-Warshall多源O(V³)是A*单源单终点取决于启发函数否选择建议如果没有负权边优先用Dijkstra如果有负权边用Bellman-Ford或SPFA如果需要所有点对的最短路径且节点数不多用Floyd-Warshall如果只需要起点到终点的路径且能设计出好的启发函数用A*。我个人的经验是Dijkstra是使用频率最高的基本上能覆盖80%以上的场景。剩下的20%里A*和Floyd-Warshall各占一半。Bellman-Ford和SPFA用得比较少主要是因为大多数实际问题的边权都是非负的。4.5 实际项目中的应用案例最后分享一个我在实际项目中的应用案例。之前做过一个物流配送的路径规划系统需要计算配送中心到各个配送点的最短路径。图的结构是节点是配送点和路口边是道路权重是道路长度或者预计通行时间。这个项目的节点数大概在3万左右边数在10万左右。一开始用的是朴素实现单次查询要好几秒完全没法用。后来改成优先队列优化单次查询降到了50毫秒以内。再后来发现很多查询的起点是固定的都是配送中心就做了一些预处理把常用起点的结果缓存起来进一步降到了10毫秒以内。这个项目让我深刻体会到算法本身的优化很重要但结合业务特点做针对性的优化同样重要。有时候一个简单的缓存就能带来数量级的提升。另外一个坑是权重的动态变化。道路的通行时间会随着交通状况变化如果每次变化都重新计算所有路径开销太大。我们的做法是只对受影响的区域重新计算其他区域沿用缓存结果。这个策略虽然不能保证全局最优但在实际业务中已经足够好了。5. 写在最后几个让我少走弯路的小技巧Dijkstra这个算法我前前后后学了三四遍每次都有新的理解。最开始是死记硬背伪代码后来是照着模板写代码再后来是理解背后的贪心思想和松弛操作最后是在实际项目中不断调优。如果你也在学这个算法我建议你不要只停留在能写出来的层面多问问自己为什么这样写是对的、换个场景还适用吗。几个具体的小建议第一手算模拟至少走两遍一遍简单的图一遍稍微复杂的图这样能帮你建立直觉第二代码实现至少写两遍一遍朴素版一遍优先队列版对比一下差异第三找一个实际的小项目练手比如做一个简单的地图寻路Demo把算法用起来比单纯刷题效果好得多。还有一个容易被忽略的点测试用例的设计。很多人写完Dijkstra只测一个简单的图就完事了但实际上边界情况才是最容易出bug的地方。我通常会准备这样几组测试单节点图、两点一边的图、有环的图、不可达的图、多条最短路径的图。这几组测下来基本能覆盖大多数问题。如果你在实现过程中遇到了什么奇怪的问题欢迎一起交流。算法这东西一个人闷头想容易钻牛角尖多和别人讨论讨论往往能豁然开朗。