1. 为什么一个快七十岁的老算法还值得反复讲但凡接触过路径规划、网络路由、地图导航这类场景的人几乎都绕不开 Dijkstra 算法。它诞生于 1956 年由荷兰计算机科学家 Edsger W. Dijkstra 在咖啡馆里花了二十分钟设计出来原本是为了演示一台新型计算机的运算能力结果成了图论里最经典的单源最短路径算法。我做了十多年后端和算法相关的工作面试过不少人也带过不少新人发现一个很有意思的现象几乎所有人都说“我会 Dijkstra”但真正能把它讲清楚、写对、用对的人比例低得惊人。这篇文章想做的事情很朴素——把 Dijkstra 算法从头到尾拆一遍。不是那种贴一段伪代码就完事的“详解”而是把它到底在解决什么问题、为什么这么设计、每一步在干什么、代码怎么写才不出错、什么场景下不该用它这些真正卡人的地方讲透。适合的读者范围也很宽刚学数据结构与算法的大学生、准备技术面试的求职者、工作中需要做路径规划或资源调度的工程师甚至只是想搞明白“导航软件怎么算出最短路线”的普通技术爱好者都能从里面拿到东西。我尽量不用那种教科书式的腔调而是像一个踩过坑的人坐在你旁边把当年自己绕过的弯路、写崩过的代码、理解错的概念一个个摊开来讲。你会发现Dijkstra 本身的思想其实非常符合直觉真正难的是那些边界条件和实现细节——而这些恰恰是大多数教程一笔带过的地方。2. 先把问题定义清楚Dijkstra 到底在算什么2.1 从一个生活场景说起假设你在一张城市地图上要从家出发去公司地图上每条路都有一个通行时间。你想知道从家到公司最快需要多久以及具体走哪条路。这就是最典型的单源最短路径问题给定一个起点源点求它到图中所有其他节点的最短距离。注意这里有两个关键词。第一是“单源”意思是只从一个起点出发而不是算任意两点之间的距离那是多源或者全源问题得用 Floyd 之类的算法。第二是“最短路径”在带权图里路径的长度不是经过几条边而是边权之和。这个区别很关键很多初学者会把“边数最少”和“权重最小”搞混。Dijkstra 算法解决的正是这个问题在一个边权非负的图中从一个源点出发计算出它到所有其他节点的最短距离同时还能还原出具体路径。2.2 它和 BFS、Floyd 的区别在哪很多人学完 BFS 之后会问BFS 不也能求最短路径吗答案是能但仅限于无权图也就是每条边权重都相等可以看作都为 1的情况。一旦边权不一样BFS 按层扩展的逻辑就失效了因为它假设“先到达的节点距离一定更短”而这个假设在带权图里不成立。Floyd 算法则是另一个极端它能算出图中任意两点之间的最短距离时间复杂度是 O(n³)适合节点数量不多但需要频繁查询任意两点距离的场景。Dijkstra 处在中间只算一个源点但效率高得多配合优先队列可以做到 O((VE)logV) 的级别。我用一个表格把三者的定位摆清楚方便你按场景选算法解决的问题边权要求典型时间复杂度适用场景BFS单源最短路径无权或等权O(VE)迷宫、社交网络跳数Dijkstra单源最短路径非负O((VE)logV)地图导航、路由Floyd全源最短路径可负无负环O(n³)小图、任意两点查询选型逻辑其实很简单先看边权有没有负数再看你要算一个源还是所有源。有负权边Dijkstra 直接出局得换 Bellman-Ford 或者 SPFA只算一个源就别上 Floyd 那种重型武器。2.3 为什么边权不能为负这是 Dijkstra 最核心的约束也是面试高频考点。原因在于它的贪心策略算法每次从“未确定”的节点里挑出当前距离最小的那个然后断言它的最短距离已经确定不会再被更新。这个断言成立的前提是如果所有边权都非负那么从源点绕一圈再回到某个节点距离只会增加不会减少。所以当前距离最小的那个节点不可能通过其他还没确定的节点绕路变得更短。但一旦存在负权边这个逻辑就崩了——你可能先确定了一个距离为 5 的节点结果后面发现通过一条负权边能绕到距离 3那前面的“确定”就成了错误。我见过有人试图给 Dijkstra 打补丁来支持负权比如加个判断“如果发现更短就重新入队”。这么改之后它其实已经变成了 SPFA 的变体不再是 Dijkstra 了而且复杂度也没了保证。所以我的建议很直接有负权边老老实实换算法别硬改。3. 核心思想拆解贪心加松弛两步走天下3.1 松弛操作整个算法的灵魂如果只能用一个词概括 Dijkstra我会选“松弛”Relaxation。这个词听起来玄乎其实特别简单。假设你现在知道从源点到节点 u 的最短距离是 dist[u]而 u 到 v 有一条权重为 w 的边。那么从源点经过 u 到 v 的距离就是 dist[u] w。如果这个值比目前记录的 dist[v] 还小说明我们找到了一条到 v 的更短的路于是更新 dist[v] dist[u] w。用一句话说松弛就是“看看能不能抄近道”。每次发现一条更短的路就更新一下记录。整个 Dijkstra 的过程本质上就是不断地做松弛直到所有节点的距离都稳定下来。这里有个细节值得强调松弛的时候我们不仅更新距离通常还会记录一个“前驱节点”数组 prev[v] u。这样最后算完从终点一路往回倒推就能还原出完整路径。很多人只算距离不记前驱等到需要输出路径时就抓瞎了。3.2 贪心选择为什么每次挑最小的就对了Dijkstra 的第二个支柱是贪心。算法维护两个集合已确定最短距离的节点集合我们叫它 settled和还没确定的节点集合。每一轮从没确定的里面挑出 dist 值最小的那个节点把它移进 settled然后用它去松弛它的所有邻居。为什么挑最小的就对了前面讲负权的时候其实已经埋了伏笔。因为边权非负当前 dist 最小的那个节点不可能再通过其他未确定节点绕路变得更短——任何绕路都要加上非负的边权只会更大。所以它的最短距离此刻就可以“盖章确认”。这个贪心策略的正确性是 Dijkstra 能成立的根本。理解了这一点你就能明白为什么它不能处理负权也能明白为什么用优先队列优化是自然的——因为我们反复需要“取出当前最小的”。3.3 一个手算例子把过程走一遍光说理论容易飘我们拿一个具体的小图走一遍。假设有 5 个节点编号 A 到 E边和权重如下A→B 权重 4A→C 权重 2C→B 权重 1C→D 权重 5B→D 权重 2D→E 权重 3源点是 A。初始化dist[A]0其余都是无穷大。第一轮未确定集合里 dist 最小的是 A0。把 A 确定松弛它的邻居dist[B] 更新为 4dist[C] 更新为 2。第二轮未确定里最小的是 C2。确定 C松弛邻居C→B 让 dist[B] 从 4 变成 213更新C→D 让 dist[D] 变成 257。第三轮未确定里最小的是 B3。确定 B松弛邻居B→D 让 dist[D] 从 7 变成 325更新。第四轮未确定里最小的是 D5。确定 D松弛邻居D→E 让 dist[E] 变成 538。第五轮确定 E8。结束。最终 A 到各点的最短距离B3C2D5E8。你可以自己验算一下比如 A 到 D走 A→C→B→D 是 2125确实比直接 A→C→D 的 7 要短。这个例子虽小但把松弛和贪心的配合体现得很清楚。4. 代码实现从朴素版到优先队列优化4.1 朴素实现适合稠密图最朴素的 Dijkstra 用邻接矩阵存图每一轮用线性扫描找最小 dist 的节点。时间复杂度是 O(V²)。在节点数量不多比如几百个但边很密的图里这个版本反而有优势因为邻接矩阵访问快常数小。下面是一个 Python 版本的朴素实现我加了详细注释def dijkstra_naive(graph, src): # graph 是邻接矩阵graph[i][j] 表示 i 到 j 的边权 # 不相连用 float(inf) 表示 n len(graph) dist [float(inf)] * n visited [False] * n prev [-1] * n # 记录前驱用于还原路径 dist[src] 0 for _ in range(n): # 第一步找未访问节点中 dist 最小的 u -1 min_dist float(inf) for i in range(n): if not visited[i] and dist[i] min_dist: min_dist dist[i] u i if u -1: break # 剩下的节点都不可达 visited[u] True # 第二步用 u 松弛它的邻居 for v in range(n): if not visited[v] and graph[u][v] ! float(inf): new_dist dist[u] graph[u][v] if new_dist dist[v]: dist[v] new_dist prev[v] u return dist, prev这段代码有两个地方新手容易写错。第一是找最小节点时如果 u 最终是 -1说明剩下的节点都不可达必须 break否则会拿 -1 去索引数组报错。第二是松弛时一定要判断not visited[v]虽然不判断结果也对因为已确定的节点距离不会再变小但判断了能省一些无谓的计算。4.2 优先队列优化稀疏图的首选实际工程里图往往是稀疏的——节点成千上万但每个节点的邻居没几个。这时候 O(V²) 就太慢了得用优先队列最小堆来加速“找最小”这一步。优化后的复杂度是 O((VE)logV)。Python 里用heapq实现注意 Python 的堆是小顶堆直接存 (距离, 节点) 元组即可import heapq def dijkstra_heap(graph, src): # graph 是邻接表graph[u] [(v, w), ...] n len(graph) dist [float(inf)] * n prev [-1] * n dist[src] 0 heap [(0, src)] # (当前距离, 节点) while heap: d, u heapq.heappop(heap) # 关键如果这个距离已经过时直接跳过 if d dist[u]: continue for v, w in graph[u]: new_dist d w if new_dist dist[v]: dist[v] new_dist prev[v] u heapq.heappush(heap, (new_dist, v)) return dist, prev这里有个极其重要的细节if d dist[u]: continue这一行。因为同一个节点可能被多次压入堆中每次距离更新都会压一次堆里会有很多过时的记录。如果不跳过虽然结果仍然正确但会做大量无用功性能大打折扣。这个“惰性删除”的技巧是优先队列版 Dijkstra 的精髓很多教程不讲导致读者写出来的代码慢得莫名其妙。4.3 两种实现的选型对比到底用哪个版本不能拍脑袋得看图的特点。我整理了一个对照表维度朴素版邻接矩阵优先队列版邻接表时间复杂度O(V²)O((VE)logV)空间复杂度O(V²)O(VE)适合图类型稠密图稀疏图实现难度低中常数因子小略大判断稠密还是稀疏看边数 E 和 V² 的关系。如果 E 接近 V²就是稠密图朴素版可能更快如果 E 远小于 V²比如 E 和 V 一个量级优先队列版优势明显。我个人的经验是除非确定是稠密图否则默认上优先队列版因为实际数据大多是稀疏的。5. 实操中的坑与排查技巧5.1 路径还原别只会算距离很多人写完 Dijkstra 只输出了距离数组一到需要输出具体路径就卡壳。其实只要在松弛成功时记录prev[v] u最后从终点往回倒推就行def get_path(prev, src, dst): path [] cur dst while cur ! -1: path.append(cur) cur prev[cur] path.reverse() # 如果 path[0] 不是 src说明不可达 if path[0] ! src: return [] return path这里有个坑如果终点不可达倒推会一路走到 -1 然后停此时 path 的第一个元素不是源点。所以必须加一个判断否则会返回一条错误的路径。我见过线上事故就是因为没做这个判断把不可达当成了可达。5.2 常见问题速查表下面这张表是我这些年踩坑和帮别人排查时总结的基本覆盖了 90% 的出错场景现象可能原因排查方向结果距离偏大漏了某次松弛检查是否遍历了所有邻居结果距离偏小边权为负确认图是否含负权边程序死循环堆里过时元素没跳过加if d dist[u]: continue路径还原为空终点不可达或前驱没更新检查 prev 数组和可达性性能极慢用了朴素版跑稀疏大图换优先队列版内存爆掉邻接矩阵开太大改用邻接表5.3 几个容易被忽略的实操心得第一距离数组的初始值别用整数最大值。用float(inf)更安全因为整数最大值加上边权可能溢出变成负数导致判断出错。这个坑在 C 里尤其常见用INT_MAX做初始值一加就溢出。第二多源问题可以加一个虚拟源点。如果要从多个起点同时算最短路径不用跑多次 Dijkstra而是新建一个虚拟节点让它到所有真实起点的边权为 0然后从这个虚拟源点跑一次即可。这个技巧在“多个仓库到客户的最短配送距离”这类场景里特别好用。第三记录路径时注意内存。如果图很大又需要还原很多条路径prev 数组是 O(V) 的没问题但如果要存所有路径可能爆内存。这时候可以考虑只存 prev需要时再倒推用时间换空间。第四优先队列里存元组时把距离放前面。Python 的堆比较元组时先比第一个元素距离放前面才能保证按距离排序。如果放反了会按节点编号排序结果就全乱了。这个错误我见过不止一次。6. 它到底用在哪真实场景与影响范围6.1 地图导航与路径规划这是 Dijkstra 最广为人知的应用。导航软件要在路网图上算出从起点到终点的最快路线路网就是典型的带权图权重可以是距离、时间或者综合成本。不过实际导航系统很少直接用裸的 Dijkstra因为全国路网动辄几千万节点跑一次太慢。工程上会用 A* 算法Dijkstra 加启发式函数或者分层收缩等技术来加速但底层的核心思想仍然是 Dijkstra 那一套。6.2 网络路由与数据转发在计算机网络里路由协议需要计算数据包从源到目的地的最优转发路径。经典的 OSPF 协议内部就用 Dijkstra 算法计算最短路径树。每个路由器把自己看作源点算出到网络中其他所有路由器的最短路径据此建立路由表。这里的“距离”通常是链路开销可能和带宽、延迟相关。6.3 资源调度与任务编排这个场景可能很多人没想到。比如在一个任务依赖图里每个任务有执行耗时要找出从开始到结束的关键路径最长路径把边权取负再跑 Dijkstra 是一种思路当然有负权就得换算法。再比如游戏里的 AI 寻路、物流里的配送路线优化、社交网络里的最短关系链本质上都是单源最短路径问题的变体。6.4 它的影响范围有多大从 1956 年到现在Dijkstra 算法一直是图论和算法教学里的必修内容也是技术面试的常客。它的影响力早就超出了学术圈渗透到了几乎所有需要“找最优路径”的工程领域。更值得一提的是它体现的贪心加松弛思想影响了后来一大批算法设计——很多问题都可以归结为“不断做出当前最优选择并维护一个可更新的状态”这正是 Dijkstra 留给我们的思维范式。我个人的体会是学好 Dijkstra 不只是掌握一个算法而是理解了一类问题的通用解法。当你在工作中遇到“从一堆选项里逐步逼近最优解”的场景时Dijkstra 的思路往往能给你启发。它简单但绝不简陋它古老但依然活跃在最前沿的系统里。这大概就是一个算法能拥有的最好的生命力。