先聊一个问题导航App输入起点和终点它怎么在几秒内算出最优路线剥开外壳底层大多是一个经典算法——单源最短路径而其中应用最广、最适合入门的就是Dijkstra算法。Dijkstra解决的问题非常具体在一张带权图上给定一个源点求它到所有其他节点的最短距离。这里的权可以是时间、距离、成本条件是权重非负。只要满足这个条件Dijkstra就是最优先考虑的方案。这篇文章会从最短路径问题的定义开始拆解Dijkstra的贪心原理给出朴素实现和堆优化两份可直接抄的代码再聊聊我实际刷题和工程里踩过的那些坑。适合刚学完图论基础、想把最短路径彻底吃透的读者。1. 最短路径问题与Dijkstra的定位1.1 图上的最短路径到底在求什么先建立基本概念。图由节点和边组成每条边可能带有一个权重代表从这条边一端到另一端的代价。最短路径问题就是在给定起点和终点之间找一条路径使得路径上所有边的权重之和最小。如果图没有权重也就是每条边代价都是1那最短路就等价于最少经过几条边。这种情况BFS就够了。但一旦边有了权重比如地铁换乘时间、公路里程、运费成本BFS就失效了——它只数边数不看权重哪怕一条路只有两段但每段都很贵BFS依然认为它最短。Dijkstra算法处理的就是这种带权图的单源最短路径。意思是每次只算一个起点一次性得出这个点到所有其他点的最短距离。与之相对的是Floyd这类全源算法一次算所有点对之间的最短路。实际场景中绝大多数是单源需求所以Dijkstra出镜率极高。1.2 所有权重非负这个前提为什么绕不开很多初学者不理解为什么Dijkstra一定要求边权非负负权边到底会出什么问题我用一个极简的反例说明。假设有一个三角形起点A直接到终点B边权是5同时A到中间节点C的边权是1C到B的边权是-3。按真实答案A到B的最短路是A-C-B总代价1 (-3) 2比直连的5更短。然而Dijkstra的贪心策略是每次先锁定当前距离最小的点。第一轮它发现A到B的直连距离是5A到C是1于是它会锁定C第二轮再锁定B这样算出的结果是A-C-B看起来碰巧对了。但换个结构就不行。比如A到B是5A到C是1C到B是-10。Dijkstra第一轮会锁定C然后更新B为1 (-10) -9看起来也还行。问题出在更复杂的图上当C的距离其实还能被其他负边进一步缩小但C已经被锁定后续不会再重新考虑。真正的反例A到C是1C有一条负边连到B比如-5同时A到B直连是3。Dijkstra先锁定C更新B为1-5-4随后锁定B。这看起来好像没问题。但只要有负边让某个已锁定节点的距离可以更小的结构贪心的已锁定则不再修改假设就被击穿。本质上Dijkstra依赖一个关键性质从源点出发已经确定的最短路径不会被后续发现的路径追平或追超。这个性质在高权值下天然成立因为绕路只会增加代价。一旦出现负权边绕路反而可能让总代价变小那先锁定近点、后处理远点的顺序就完全不可靠了。所以结论很简单图里有负权边就别用Dijkstra换Bellman-Ford或者SPFA。这是个模型选择的问题不是代码水平的问题。2. 算法原理拆解贪心、松弛、锁定2.1 每个循环都在做哪几件事Dijkstra的核心可以压缩成三个动作贪心选择、松弛更新、锁定节点。每次循环先从未锁定的节点中找出当前距离源点最近的那个把它标记为已确定。这个已确定的意思是这个距离已经是最终答案后续不会再变得更小。然后拿着这个节点遍历它的所有出边尝试用它更新邻居的距离。更新逻辑很简单如果源点经过当前节点再到邻居的总代价比邻居现有的记录还要小就覆盖邻居的记录。这个过程叫松弛。松弛这三个字理解透了整个算法也就理解了。可以用一个生活场景类比假设你在几个仓库之间转运货物每个仓库都有一个当前估算成本。发现经某个仓库中转可以更省钱就更新这个估算值。每次只挑估算成本最低的仓库来铺路铺过路的仓库就被标记成最终成本以后不再改。松弛不是只做一次而是随着新节点不断被确定而反复进行。每一轮松弛都可能让某个邻居的估算值变小。整个算法终止条件也很简单所有能到达的节点都被锁定优先队列被清空。2.2 一个五节点图的手动推演光看概念容易飘我拿一个具体的图走一遍全过程。这是一个无向图5个节点编号0到4源点是0。边的关系如下0-1: 权重40-2: 权重21-2: 权重11-3: 权重52-3: 权重82-4: 权重103-4: 权重2初始状态dist数组为[0, ∞, ∞, ∞, ∞]0号节点距离是0其他都是无穷大。优先队列放入(0, 0)。第一轮弹出(0, 0)锁定节点0。遍历它的邻居节点1被更新为0 4 4节点2被更新为0 2 2。dist变为[0, 4, 2, ∞, ∞]。第二轮优先队列里最小的是距离2的节点2锁定节点2。用节点2更新邻居节点1经过2是2 1 3比原来的4小更新为3节点3经过2是2 8 10节点4经过2是2 10 12。dist变为[0, 3, 2, 10, 12]。注意这里节点1的距离在第1轮被设为4但在第2轮通过节点2中转反而更短所以被更新成了3。这就是松弛存在的意义最初的距离估算只是临时值随时可能被更优路径替代。第三轮未锁定节点中最小的是距离3的节点1锁定节点1。用节点1更新邻居节点3走1是3 5 8比原来的10小更新为8。dist变为[0, 3, 2, 8, 12]。第四轮未锁定节点中最小的是距离8的节点3锁定节点3。用节点3更新邻居节点4走3是8 2 10比原来的12小更新为10。dist变为[0, 3, 2, 8, 10]。第五轮锁定节点4距离10没有更小的邻居可更新。最终结果dist [0, 3, 2, 8, 10]。也就是说0到4的最短距离是10路径是0-2-1-3-4而不是看起来更直接、但绕远的那条0-2-4总代价12。这个例子值得多看两眼。最短路不一定是边数最少的路径0到4有直连边但代价很高反而是多转几次的路径总代价更小。这也是带权图和无权图的本质区别。2.3 贪心为什么有效一个简明的正确性直觉Dijkstra是典型的贪心算法。贪心算法并不总能保证最优解为什么Dijkstra能保证关键在于下一跳锁定距离最小的点这个策略。直观地理解所有边权都是非负的那么任何一条从源点出发、经过某个未锁定节点再绕回来的路径其总长度一定不会小于这个未锁定节点到源点的当前距离。因为绕路必然还要加上若干条非负的边权只会让总长度更大。所以当从未锁定节点中选出距离最小的节点u时可以确定如果存在一条比dist[u]更短的路到达u这条路上必然第一个遇到某个未锁定节点v。那么v到源点的距离应该比dist[u]更小否则经过v的路径不可能比dist[u]短——这与u是所有未锁定节点中距离最小的矛盾。这个矛盾说明了什么说明dist[u]已经小到不可能再有更优路径了所以放心锁定。非负边权是这个论证的基石任何绕路都不会带来负收益这保证了目前最小就是最终最小。3. 代码实现先朴素再堆优化3.1 朴素实现O(V²)的直白写法朴素版本不借助优先队列每一轮循环手动找最小距离节点。逻辑最简单适合刚学完原理、准备写第一份代码的读者。代码用Python写def dijkstra_naive(n, edges, source): # n: 节点数量节点编号为 0 ~ n-1 # edges: 边列表每个元素是 [u, v, w] adj [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) # 无向图需双向建边有向图去掉这一行 INF 10 ** 18 dist [INF] * n dist[source] 0 visited [False] * n for _ in range(n): # 1. 贪心选择从未锁定的节点里找距离最小的 u -1 best INF for i in range(n): if not visited[i] and dist[i] best: best dist[i] u i if u -1: break # 剩余节点均不可达 # 2. 锁定节点 u visited[u] True # 3. 松弛用 u 更新所有邻居 for v, w in adj[u]: nd dist[u] w if nd dist[v]: dist[v] nd return dist每轮循环通过遍历所有节点来找最小值所以外层循环n次内层找最小值又是O(n)总体复杂度O(n²)。再加上遍历邻居松弛的O(E)整体是O(n² E)在稠密图中E接近n²所以综合说O(n²)。这个版本适合什么场景节点规模在几百到一两千级别。小图频繁做最短路径查询的时候比如地图上的局部路径规划、小规模网络拓扑分析朴素写法完全够用代码明确、不易写错。3.2 堆优化实现标准竞赛与工程写法当节点数到达10⁵级别甚至10⁶朴素实现的O(n²)循环直接超时。此时需要优先队列来快速取出最小距离节点时间复杂度降到O((VE)logV)。import heapq def dijkstra_heap(n, edges, source): adj [[] for _ in range(n)] for u, v, w in edges: adj[u].append((v, w)) adj[v].append((u, w)) # 无向图需双向建边 INF 10 ** 18 dist [INF] * n dist[source] 0 visited [False] * n pq [(0, source)] # 优先队列元素是 (当前距离, 节点编号) while pq: d, u heapq.heappop(pq) if visited[u]: continue visited[u] True for v, w in adj[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist这段代码是工程和竞赛中最常见的版本有几个细节值得仔细讲。优先队列的排序依据是元组第一个元素也就是距离。Python的heapq实现的是最小堆每次弹出的都是当前队列里距离最小的节点。这里非常重要的一个地方为什么弹出后要判断visited因为同一个节点可能被多次加入优先队列。比如节点v先通过一条代价为10的路径被加入队列后来又发现一条代价为5的路径那么v就会入队两次——一次(10, v)一次(5, v)。优先队列按距离排序所以(5, v)会先被弹出v被锁定dist[v]5也已经是最终值。等到(10, v)弹出时v已经visited直接跳过即可。判断visited就是清理这种过期记录。3.3 visited标记时机一个特别容易翻车的细节我刚学Dijkstra时踩过一个大坑在把新距离push进优先队列的同时就把节点标记为visited。后来发现这个写法在某些图上会算错。问题出在哪看刚才那个例子。源点0先通过直连边找到节点1距离是4。如果在push时就标记visited节点1被立即锁定。但稍后节点2被处理发现经过节点2到节点1只需要3本应更新dist[1]为3但由于节点1已经被标记visited这个更新就被跳过了最终答案错误。正确的做法是在弹出节点时才标记visited入队时不标记。这样即使一个节点被push了多次只要最终更优的距离尚未被处理它就还有机会被重新计算和更新。一句话记住visited的含义是此节点的最短距离已经被确定并锁定而只有弹出那一刻才是真正确定的时刻。push时标记等于把还没确定的临时值当成了最终值。4. 复杂度、正确边界与算法选型4.1 两个版本的复杂度差异该怎么选先整理清楚两个版本的开销来源。朴素版本外层n轮找最小节点扫一遍O(n)总复杂度O(n²)。空间上如果使用邻接矩阵是O(n²)使用邻接表则是O(n E)。堆优化版本每个节点可能入队多次但总体上每个节点的入队次数等于它被松弛更新的次数不超过E次所以总的push数量是O(E)。每次push和pop都是O(logV)。总复杂度O((V E)logV)。堆的额外空间是O(E)。选型逻辑我琢磨过之后总结成一个判断表图的特点推荐实现原因节点数≤10³稠密图朴素找最小值的O(n)扫描开销可接受实现简单节点数10⁵~10⁶稀疏图堆优化堆的logV开销远小于O(n)线性扫描节点数10⁵以上只能用堆优化朴素无法在时限内跑完图非常稠密且节点数大堆优化仍可行但可考虑邻接矩阵需要用邻接矩阵存边的权重工程实践里还有个细节因为堆优化需要存储边、堆、距离数组内存开销比朴素更大所以小数据量时用朴素实现反而更稳尤其在一些内存受限的嵌入式环境里。4.2 与其他最短路算法的边界对比Dijkstra不是万能的很多人学完它就不管其他了遇到负权图照样跑然后莫名其妙得出错误结果。我把几个常见算法放在一起对比方便构建全局认知。算法是否允许负权边适用场景时间复杂度特点BFS仅限边权全部为1无权图O(V E)实现最简单Dijkstra不允许单源非负权图O(V²)或O((VE)logV)最快且最常用Bellman-Ford允许无负环单源带负权图O(VE)可以检测负环SPFA允许无负环单源带负权图平均O(E)最坏O(VE)竞赛常用但易被卡Floyd允许无负环全源小图O(V³)代码简单但只适合小图这里我最想强调的是判断一个图能不能用Dijkstra第一件事就是检查负权边。怎么检查像哪里有负权这个问题在实际场景中几乎等于哪里有回扣、补贴、逆向流动这类反常规则。比如物流问题里可能出现空车返程成本为负的情况吗一般情况下不会但如果你在做带奖励的路径规划就要警惕了。4.3 双向Dijkstra让效率再翻一倍在真实导航和大规模图场景中另一个常见的加速思路是双向Dijkstra。从起点和终点同时做Dijkstra两个搜索前沿在中途相遇时就找到了最短路径。这个思路听起来简单但实现时有个关键点不是两个方向分别跑完再拼接而是交替推进每次选择当前队列中距离较小的那个方向扩展。当两个前沿的节点访问集合产生交集时就可以用交点的前后距离和来尝试更新答案。如果方向选择不当最优路径可能被错过。双向Dijkstra的加速效果在稀疏图上非常明显尤其源点与终点距离较远时搜索空间从整张图缩小为两片前沿相交的区域。工程中的地图路径规划往往用这种变种。5. 实战中的常见问题与避坑实录5.1 负权边和负环换了算法就能解决吗前文说过负权边不能用Dijkstra但换Bellman-Ford后还会遇到另一个问题负环。负环是指图中存在一个环环上所有边权之和为负数。如果存在负环最短路就没有意义了——每绕一圈距离就小一点可以无限绕下去得到任意小的距离。实际工程里怎么发现负环Bellman-Ford做V-1轮松弛后如果再进行第V轮还能松弛成功就说明存在负环。实际开发中碰到这种情况往往不是算法问题而是数据建模有问题。我见过一个做运输优化的团队把补贴建模成负权边结果怎么跑都跑不出稳定答案最后发现负环链。正确做法是把这种补贴放进约束条件而不是直接写成负边。所以遇到负权场景先问自己这个负权重是不是合理存在如果只是数据噪声导致个别负值可能修数据更现实如果模型本身允许负向反馈才该上Bellman-Ford。5.2 重边、自环、双向边与INF取值实际建图时重边、自环这些脏数据经常出现。我自己处理过一张上百万边的图数据里相同端点对出现了三四次权值还不一样。处理重边的思路很简单不需要预先合并。堆优化Dijkstra天然处理重边——它会先通过权值较小那条边更新dist权值较大的边即使later入队也会被visited逻辑跳过。唯一需要注意的是如果使用邻接矩阵就要在输入时取最小值覆盖。自环更简单。非负权边的自环dist[u] w dist[u]永远不会松弛成功可以忽略。就算权值为0也是白忙活逻辑上不会出错只是多遍历一次空操作。双向边要注意建图两侧都加。这个口子漏的人特别多我用一个无向图测试数据跑了半天结果最短距离对但路径还原始终不对最后发现读入时只建了单向边。INF取值也值得单独说。不要用float(inf)在需要严格整数比较的场景里硬扛尤其是在计算过程中做dist[u] w时如果dist[u]是float(inf)加上权重依然是infPython里没问题但在C里用INT_MAX就可能溢出成负数。稳妥做法是定义一个足够大的数比如节点数上限乘边权上限再加一点余量。我习惯用10¹⁸因为绝大多数题目的边权和不会超过这个数量级。5.3 从求距离进阶到还原路径大多数讲解止步于求出最短距离但工程里经常还要知道具体路径。还原的实现不复杂在松弛成功时额外记录一下节点v是从哪个节点u更新来的。用一个prev数组初始化为-1每次nd dist[v]时prev[v] u。从终点倒推即可得到完整路径从终点出发沿着prev一路回溯到起点最后反转数组。我写个标准还原代码def get_path(prev, source, target): path [] cur target while cur ! -1: path.append(cur) if cur source: break cur prev[cur] path.reverse() return path # 如果 path[0] ! source说明 target 不可达这个代码有个隐含要求必须保证最短路只有一条。如果存在多条距离相同的路径prev记录的只是其中一条。想求字典序最小的最短路需要在松弛时增加一个比较条件距离更小或者距离相等但节点编号更小才更新prev。路径还原里的另一个坑是如果节点不可达prev链在源点之前就断掉上面代码会死循环因为cur一直回退到-1还找不到source。所以退出条件要写周全我上面的代码用if cur source: break来保障。5.4 常用样例自查清单我开发时习惯准备一组小样例来做回归测试推荐你也这样做。第一组线性图。0-1权重11-2权重1源点0到2应该是2。第二组两个路径对比的图。0直连2权重100-1权重11-2权重1答案应该是2而不是10。这个样例专门测试松弛逻辑。第三组重边图。0-1权重50-1权重1答案应该是1。第四组自环图。0-1含0-0自环加一条权重2的边答案2自环不干扰。第五组不可达节点。0连12孤立dist[2]INF不会进入死循环。这五组样例能在5分钟内覆盖90%的基础错误。每次写完Dijkstra先跑一遍再过数据。6. 应用场景与后续扩展路线6.1 真实世界里的DijkstraDijkstra的应用范围远超想象。最常见的当然是地图导航。地图软件在预处理阶段会把路网抽象成图路口是节点路段是边权重可以是距离、耗时或消耗。用户请求导航时后排一个堆优化的Dijkstra或者双向变种很快就能给出路线。在计算机网络领域链路状态路由协议OSPF内部就使用SPF算法计算最短路径SPF本质就是Dijkstra的工程变形。路由器维护一张全网拓扑的链路状态数据库需要路由时快速计算到所有目标的最短路径。这里图的规模可能达到上万个节点堆优化版本在性能和稳定性上都经得起考验。游戏寻路也是重灾区。很多游戏地图被抽象成网格或路点图每个格子就是节点相邻格子的移动消耗就是边权。当移动消耗取决于地形沼泽、山地、平原时Dijkstra和它的变种A就替代了BFS。A本质是Dijkstra加了一个启发函数比Dijkstra更快地导向目标方向。物流和公共交通调度里也大量使用。我在一个配送路径优化的模拟项目里用Dijkstra计算仓库到各个配送点的最短消耗路径再配合线性规划做车辆分配效果比单纯手工规划稳定得多。6.2 学完Dijkstra下一步还能往哪走Dijkstra是进入图论算法的一个大门。学完它有几个自然的进阶方向。第一个是Johnson算法。它组合了Bellman-Ford和Dijkstra用于解决带负权边的全源最短路径问题。基本思路是先做一次Bellman-Ford做势能重标定把所有边权转成非负再跑V次Dijkstra。在稀疏图上这比Floyd快很多。第二个是层次图最短路径。有些问题把状态扩展成多层比如允许免费一次的路径规划可以把每个节点拆成多个层层间建特定权值的边再用Dijkstra跑。这种建图技巧在竞赛和企业面试里都经常出现。第三个是动态图上的最短路径。真实路网是动态变化的比如堵车导致某条边权实时上涨。这时候跑全量Dijkstra很浪费更好的做法是在原有计算结果上局部更新受影响区域。这个方向叫增量最短路径工程价值很高。第四个是并行化。大规模图的最短路径可以用GPU并行加速每个迭代阶段并行处理多个节点的松弛。比如在已经拥有数亿节点的社交网络图上计算接近中心性就必须考虑并行化的Dijkstra实现。学完这几个方向最短路径这个知识树基本就完整了。7. 最后分享一点个人经验回到开头那个问题一张图、一个起点、若干带权边Dijkstra怎么用才最舒服我自己的习惯是每写一个Dijkstra版本之前先问三个问题图里有负权边吗图是稠密还是稀疏需要路径还原还是只要距离这三个问题的答案直接决定选哪个实现、建什么数据结构、记录哪些额外信息。大多数翻车都不是算法没写对而是没答好这三问。动手验证比看十遍讲解都有效。我建议新手拿到任意一张小图手动画出来按Dijkstra的每轮选择在纸上标一遍强烈推荐配合打印每个轮次的dist数组来观察。你会看到贪心选择如何一步步把临时值变成最终值也会看到松弛操作如何反复纠正之前的粗略估算。有了这种手感再去写代码和debug会顺畅很多。