1. 为什么一个最短路径问题值得单独写一篇详解很多人第一次接触Dijkstra算法是在数据结构课的PPT上——老师画了一张带权图标了几个节点然后说这个算法用来求单源最短路径。考试考完代码一交这事就翻篇了。直到某天你真的要写一个地图导航的简化版、做一个网络路由的模拟、或者在游戏里让NPC自动寻路才发现脑子里只剩下每次选最小的那个这一句模糊的印象具体怎么维护、为什么不能处理负权、复杂度到底怎么算全都不太确定。这篇文章就是写给这个状态的你。不假设你有很强的算法竞赛背景也不打算用一堆数学符号把你劝退。我会从这个算法到底在干什么讲起把每一步的动机说清楚然后给出可以直接运行的代码最后聊聊实际写的时候容易踩的坑。Dijkstra算法本身并不复杂它的核心思想用一句话就能概括从起点出发每次贪心地扩展当前距离最小的那个节点一旦确定就不再回头。但这句话背后藏着几个关键前提不理解这些前提代码写出来就是错的。适合谁看如果你正在准备面试、正在做课设、或者单纯想把图论里这个最经典的算法真正搞懂那这篇内容应该能帮到你。我会尽量用生活化的例子来解释比如把节点想象成城市、边想象成公路、权重想象成油费这样抽象的概念会好理解很多。读完之后你应该能自己手写出一份正确的Dijkstra实现并且知道它在什么情况下会失效。2. 把最短路径翻译成人话Dijkstra到底在解决什么问题2.1 单源最短路径一个起点到所有地方先明确问题定义。给你一张图图里有若干个节点可以理解为城市和若干条边可以理解为连接城市的公路每条边有一个非负的权重可以理解为过路费或者距离。现在指定一个起点问从这个起点出发到图中其他每一个节点的最短路径分别是多少注意这里的关键词是单源也就是只有一个起点。你可能会问那如果我想知道任意两个点之间的最短距离呢那就要对每个点都跑一遍Dijkstra或者用Floyd算法。但大多数实际场景里我们关心的就是从一个固定位置出发到各处的问题比如导航软件里从我当前位置到全城各个地点这就是典型的单源最短路径。Dijkstra算法解决的就是这个问题而且它有一个很好的性质当算法结束时你不仅得到了起点到终点的最短距离还得到了起点到所有其他节点的最短距离。这一点在实现的时候会自然体现出来因为算法本来就是一圈一圈往外扩展的。2.2 贪心策略为什么当前最近的一定是对的Dijkstra的核心是一个贪心策略。用最直白的话说在所有还没确定的节点里挑一个当前距离起点最近的宣布它的最短距离就是现在这个值不会再变了然后用它去更新它的邻居。这个宣布不再变的操作是很多人第一次学的时候最不服气的地方——凭什么你说不变就不变万一后面绕一圈回来更近呢关键在于边权非负这个前提。假设当前未确定的节点里距离起点最近的是节点A距离为10。如果存在一条从起点到A的更短路径那这条路径必然要经过某个还未确定的节点B因为如果只经过已确定的节点那在之前更新的时候就已经算出来了。而B到起点的距离至少是10因为A是当前最小的再加上B到A的边权非负总距离至少是10不可能比10更小。所以A的距离10就是最终答案。这个推理是Dijkstra正确性的基石也是它不能处理负权边的原因。如果存在负权边那么经过一个更远的节点再走一条负权边回来就可能得到更短的距离贪心策略就崩了。这一点后面还会展开讲。2.3 和BFS的区别权重让问题变复杂了如果你学过广度优先搜索BFS可能会觉得Dijkstra和它有点像——都是从起点一层层往外扩展。没错当所有边的权重都相等比如都为1时Dijkstra退化成BFS。但一旦权重不相等BFS就不管用了。举个例子起点S到A的距离是1S到B的距离是5A到B的距离是1。BFS会先访问A再访问B这没问题。但如果S到A的距离是10S到B的距离是1A到B的距离是1呢BFS按层数扩展可能先把A标记为已访问然后从A到B得到距离11但实际上S直接到B只有1。BFS的问题在于它只看经过了几条边不看总共花了多少代价。Dijkstra的改进就是用优先队列或者每次线性扫描来保证每次扩展的都是当前累计代价最小的节点而不是层数最少的节点。这个区别看似微小但它是Dijkstra能处理带权图的关键。3. 手把手拆解算法流程从初始化到输出结果3.1 需要维护哪些数据结构在动手写代码之前先把需要的东西列清楚。Dijkstra算法需要维护以下几个核心数据距离数组dist[]dist[i]表示从起点到节点i的当前已知最短距离。初始时起点到自己的距离为0到其他所有节点的距离为无穷大表示暂时不可达。访问标记visited[]visited[i]表示节点i的最短距离是否已经确定。初始时全部为false。优先队列最小堆用来快速取出当前距离最小的未确定节点。队列里存的是(距离, 节点)这样的二元组。前驱数组prev[]可选用来记录路径。prev[i]表示在最短路径上节点i的前一个节点是谁。如果只需要距离不需要路径这个可以省略。这里重点说一下优先队列的作用。如果不用优先队列每次找最小距离的节点都要遍历一遍所有节点时间复杂度是O(V)总共要找V次所以是O(V²)。用了优先队列二叉堆每次取最小是O(log V)总共是O((VE) log V)。对于稀疏图边数远小于V²优先队列版本明显更快。3.2 初始化起点距离为0其余为无穷初始化的逻辑很直接import heapq def dijkstra(graph, start): # graph是邻接表graph[u] [(v, weight), ...] n len(graph) dist [float(inf)] * n dist[start] 0 prev [-1] * n visited [False] * n # 优先队列存(距离, 节点) pq [(0, start)] while pq: d, u heapq.heappop(pq) # 如果这个节点已经确定过了跳过 if visited[u]: continue visited[u] True # 遍历u的所有邻居 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这段代码不长但每一行都有讲究。dist[start] 0是起点到自己的距离。pq [(0, start)]把起点放进优先队列。主循环里每次弹出当前距离最小的节点如果它已经被确定过就跳过因为优先队列里可能有同一个节点的多个旧记录否则标记为已确定然后尝试用它的距离去松弛relax它的邻居。3.3 松弛操作整个算法的灵魂松弛这个词听起来很学术其实做的事情特别简单如果从起点到u再到v的总距离比目前记录的到v的距离更短那就更新到v的距离。用公式表示就是如果dist[u] w(u,v) dist[v]则dist[v] dist[u] w(u,v)。这个操作之所以叫松弛是因为你可以把dist[v]想象成一根绷紧的橡皮筋原来拉得很长距离大现在发现了一条更短的路橡皮筋就松下来了。每次松弛都意味着我们找到了一条更好的路径。松弛操作是Dijkstra算法真正在干活的地方。初始化只是搭好舞台主循环只是决定处理顺序真正让距离数组逐渐逼近正确答案的就是一次次松弛。理解了这个你就理解了Dijkstra的精髓。3.4 一个完整的走图示例光看代码可能还是有点抽象我们用一个具体的小图走一遍。假设有5个节点编号0到4边和权重如下0到1权重40到2权重12到1权重21到3权重52到3权重83到4权重3起点是0。初始状态dist [0, ∞, ∞, ∞, ∞]优先队列 [(0,0)]。第一步弹出(0,0)标记0已确定。遍历0的邻居到1的距离是044更新dist[1]4到2的距离是011更新dist[2]1。队列变成[(1,2), (4,1)]。第二步弹出(1,2)标记2已确定。遍历2的邻居到1的距离是123比当前的4小更新dist[1]3到3的距离是189更新dist[3]9。队列变成[(3,1), (4,1), (9,3)]。注意这里队列里有两个关于节点1的记录一个是旧的(4,1)一个是新的(3,1)。第三步弹出(3,1)标记1已确定。遍历1的邻居到3的距离是358比当前的9小更新dist[3]8。队列变成[(4,1), (8,3), (9,3)]。第四步弹出(4,1)发现节点1已经确定过了跳过。第五步弹出(8,3)标记3已确定。遍历3的邻居到4的距离是8311更新dist[4]11。队列变成[(9,3), (11,4)]。第六步弹出(9,3)节点3已确定跳过。第七步弹出(11,4)标记4已确定。没有邻居结束。最终dist [0, 3, 1, 8, 11]。从0到1最短是3路径0→2→1到2是1到3是8路径0→2→1→3到4是11。这个例子很好地展示了为什么需要跳过已确定节点这个判断——优先队列里会残留旧的距离记录不跳过的话会重复处理。4. 复杂度分析与不同实现方式的取舍4.1 朴素实现O(V²)的适用场景如果不使用优先队列而是每次线性扫描所有未确定的节点来找最小距离的那个时间复杂度是O(V²)。具体来说外层循环执行V次每次确定一个节点内层找最小需要O(V)松弛所有边总共需要O(E)。所以总复杂度是O(V² E)通常简写为O(V²)。这种实现看起来落后但在稠密图边数接近V²的情况下它反而可能比优先队列版本更快。因为优先队列版本每次松弛都要push一个元素总共push O(E)次每次O(log V)总复杂度是O((VE) log V)。当E接近V²时(VE) log V ≈ V² log V比V²还大。而且优先队列的常数因子比线性扫描大所以在稠密图上朴素版本往往更实用。4.2 优先队列优化O((VE) log V)的细节优先队列版本的核心优势在稀疏图上。大多数实际场景中的图都是稀疏的——比如地图上每个路口平均只连接3到4条路社交网络里每个人的好友数量也远小于总人数。这种时候E和V是同一个量级O((VE) log V)就接近O(V log V)比O(V²)快很多。但优先队列版本有一个容易被忽略的细节同一个节点可能被多次加入队列。每次松弛成功都会push一个新记录所以队列的大小可能达到O(E)而不是O(V)。这就是为什么弹出元素后要检查visited——旧记录对应的距离已经不是最新的了直接跳过。有人会问能不能用 decrease-key操作来避免重复入队理论上可以但大多数标准库的优先队列不提供这个操作自己实现的话反而更麻烦。所以实践中普遍采用允许重复入队弹出时检查的方式简单且效率足够。4.3 不同语言实现的性能差异用Python写Dijkstraheapq是最常用的工具。但Python的heapq是基于列表的二叉堆push和pop都是O(log n)常数因子不算小。如果图特别大比如百万级节点Python可能会比较吃力这时候可以考虑用C的priority_queue或者Java的PriorityQueue性能会好很多。另外如果图的规模非常大但边权范围有限还可以考虑用**桶排序Dial算法**的思想把优先队列换成一组桶每个桶对应一个距离值这样可以把复杂度降到O(VEC)其中C是最大边权。不过这是进阶优化了日常使用优先队列版本完全够用。5. 负权边为什么会让Dijkstra彻底失效5.1 一个反例就能说明问题前面反复强调Dijkstra要求边权非负但很多人只是记住了这个结论没真正理解为什么。我们来看一个具体的反例。假设有三个节点A、B、C。A到B的权重是1A到C的权重是5B到C的权重是-4。起点是A。按照Dijkstra的流程初始dist [0, ∞, ∞]。弹出A更新B为1C为5。队列里有(1,B)和(5,C)。弹出B更新Cdist[B] (-4) 1 - 4 -3比当前的5小所以dist[C]更新为-3。这一步没问题。但如果边的顺序换一下呢假设A到C的权重是5A到B的权重是1B到C的权重是-4但C还有一个到B的边权重是-10。这时候情况就复杂了。更极端的例子是存在一个负权环你可以绕着环一直走距离越来越小永远没有最短路径。5.2 贪心前提被破坏的瞬间回到那个核心推理当我们要确定节点A的距离时我们依赖所有未确定节点的距离都不小于A的距离。但如果存在负权边一个未确定节点B的距离可能看起来比A大但从B出发经过一条负权边到达A总距离可能比A当前的距离小。换句话说负权边让当前最小不再等于最终最小。贪心策略的根基被抽掉了算法自然就错了。那如果图里确实有负权边怎么办可以用Bellman-Ford算法它的思路是对所有边进行V-1轮松弛不依赖贪心所以能处理负权边。如果存在负权环Bellman-Ford还能检测出来。代价是时间复杂度O(VE)比Dijkstra慢不少。5.3 实际场景中如何判断能否用Dijkstra在实际项目中判断能不能用Dijkstra关键看权重代表什么。如果权重是距离、时间、费用这类天然非负的量那放心用。但如果权重是收益变化、温度差、海拔变化这类可能为负的量就要小心了。有一个常见的误区有人觉得只要没有负权环就能用Dijkstra。这是错的。前面那个A→B→C的例子没有负权环但Dijkstra依然会出错。只要存在任何一条负权边Dijkstra的正确性就没有保证。所以最稳妥的做法是用之前先扫一遍所有边确认没有负权再上Dijkstra。6. 从距离到路径如何还原完整的最短路径6.1 prev数组的作用与更新时机前面的代码里有一个prev数组初始全为-1。每次松弛成功时除了更新dist[v]还把prev[v]设为u。这样当算法结束时prev[v]就记录了在最短路径上v的前一个节点是谁。比如前面那个例子里最终prev[1]2prev[2]0prev[3]1prev[4]3。从节点4往回推4的前驱是33的前驱是11的前驱是22的前驱是00是起点。所以路径是0→2→1→3→4。这个回溯过程用代码写就是def get_path(prev, start, end): path [] cur end while cur ! -1: path.append(cur) cur prev[cur] path.reverse() return path注意如果end不可达prev[end]会一直是-1回溯时会在第一步就停住返回的路径只包含end本身。实际使用时要判断一下dist[end]是否为无穷大。6.2 多条最短路径时选哪条有时候从起点到终点可能存在多条距离相同的最短路径。Dijkstra只会记录其中一条具体是哪条取决于遍历邻居的顺序和优先队列的弹出顺序。如果你需要所有最短路径或者需要根据某个次要指标比如经过节点最少来选路径那就需要在松弛时加额外的判断。比如想选经过节点最少的那条可以在dist相等时比较经过的节点数。这需要额外维护一个count数组记录到每个节点的最短路径经过了多少个节点。松弛时如果dist[u]w dist[v]更新dist和count如果相等但count[u]1 count[v]也更新count和prev。这种变体在实际项目中很常见比如导航软件会优先选距离相同但红绿灯少的路线。6.3 路径还原的常见bug路径还原最容易出的bug是忘记判断可达性。如果终点不可达dist[end]是无穷大prev[end]是-1直接回溯会得到一个只有终点的路径看起来像是起点就是终点容易误导。所以用之前一定要检查dist[end]是否小于无穷大。另一个坑是prev数组的初始化。如果初始化为0而不是-1回溯时可能会陷入死循环因为0的前驱是0。所以初始化一定要用-1或者一个不可能作为节点编号的值。还有一个不太容易发现的bug如果图中有自环节点到自己的边松弛时可能会把prev[v]设成v自己回溯时也会死循环。虽然自环在最短路径问题里通常没有意义因为权重非负走自环只会增加距离但代码里最好还是加个判断跳过uv的情况。7. 实际写代码时容易踩的那些坑7.1 优先队列里存什么距离还是节点用Python的heapq时一个常见的困惑是队列里到底存什么如果只存节点编号那弹出的时候怎么知道哪个距离最小如果存(距离, 节点)元组heapq会先比较距离距离相同再比较节点这没问题。但如果距离相同且节点也相同重复入队heapq也能处理。有一种错误的做法是存(节点, 距离)这样heapq会先比较节点编号完全乱套。所以记住距离在前节点在后。另外如果节点编号不是整数而是字符串或者其他不可比较的类型元组比较可能会报错。这时候可以给每个节点分配一个唯一的整数ID或者用一个计数器来打破平局。7.2 重复入队的处理visited还是距离比较前面代码里用的是visited数组来跳过已确定的节点。还有一种做法是不用visited而是在弹出时比较d dist[u]如果弹出的距离比当前记录的距离大说明是旧记录跳过。两种做法效果一样但细节略有不同。用visited的话每个节点只会被处理一次确定后不再处理。用距离比较的话每个节点可能被处理多次每次弹出都检查但只有距离最新的那次会真正执行松弛。从效率上讲visited版本略好因为跳过的判断更简单。从代码简洁性上讲距离比较版本少维护一个数组。我个人习惯用visited因为逻辑更清晰一个节点一旦被确定就再也不碰了。这也符合Dijkstra的贪心本质。7.3 图的存储邻接矩阵还是邻接表邻接矩阵用二维数组存边matrix[u][v]表示u到v的权重。优点是查询任意两点之间的边很快O(1)。缺点是空间复杂度O(V²)对于稀疏图浪费严重。而且遍历一个节点的所有邻居需要O(V)即使实际邻居很少。邻接表用列表的列表或者字典的列表存边graph[u]是一个列表里面是(u的邻居, 权重)的元组。空间复杂度O(VE)遍历邻居的时间正比于实际邻居数量。对于稀疏图邻接表明显更优。Dijkstra算法需要频繁遍历一个节点的所有邻居所以邻接表是更自然的选择。只有在稠密图且需要频繁查询任意两点边权的情况下才考虑邻接矩阵。7.4 一个容易被忽略的细节起点到自己的距离起点到自己的距离是0这个在初始化时设置。但有时候图中可能存在从起点到起点的边自环权重非负。这时候dist[start]会不会被更新成更大的值不会因为松弛条件是dist[u] w dist[v]对于vstartdist[start]0而dist[u]w 0所以不会更新。但如果权重为0呢0 0不成立也不会更新。所以自环不会影响起点的距离这一点可以放心。不过如果图中有重边两个节点之间有多条边邻接表里会存多条记录松弛时每条都会尝试最终保留最小的那条。这也是正确的行为。8. 从理论到落地Dijkstra在真实场景中的样子8.1 地图导航中的分层优化真实的地图导航系统不会直接对全城所有路口跑一遍Dijkstra因为节点数量太大百万级甚至千万级。它们通常会用分层思想把道路分成高速、主干道、次干道、小路几个层级先在高层级上跑一个粗略的最短路径再在低层级上细化。这样可以把搜索空间缩小几个数量级。另一种常见优化是A*算法它在Dijkstra的基础上加了一个启发式函数比如到终点的直线距离优先扩展看起来更有希望的节点。A*在大多数情况下比Dijkstra快得多但前提是启发式函数要满足一定条件不能高估真实距离否则可能找不到最优解。8.2 网络路由中的距离向量与链路状态在网络路由领域Dijkstra被用在链路状态路由协议中。每个路由器收集全网拓扑信息然后以自己为起点跑一遍Dijkstra算出到每个目的地的最短路径据此构建路由表。这种方式的好处是每个路由器都有全局视野不容易出现路由环路。与之相对的是距离向量路由协议它不跑Dijkstra而是每个路由器只和邻居交换距离信息逐步收敛。距离向量的问题是有可能收敛很慢甚至出现计数到无穷的情况。所以现代大型网络更倾向于链路状态方案。8.3 游戏中的寻路网格图上的Dijkstra变体在游戏开发中NPC寻路通常用网格图把地图划分成一个个小格子每个格子是一个节点相邻格子之间有边。这种图的特点是每个节点的邻居数量固定通常是4个或8个边权通常是1或者根据地形有所不同。在网格图上Dijkstra和A都很常用。如果地图不大Dijkstra足够。如果地图很大A配合合适的启发式函数比如曼哈顿距离或欧几里得距离会快很多。还有一种优化叫跳点搜索JPS专门针对网格图通过跳过大量对称路径来加速不过实现起来比Dijkstra复杂不少。9. 几个值得记住的实操心得写Dijkstra写了这么多次有几个心得是每次都会提醒自己的。第一个是先确认边权非负这个检查花不了几秒钟但能避免后面调试半天才发现算法本身就不适用。第二个是优先队列里距离在前这个坑我踩过不止一次每次都是弹出顺序不对导致结果诡异。第三个是路径还原前先判断可达性不然会得到一个看起来合理但实际上错误的路径。还有一个不太起眼但很实用的技巧如果只需要起点到某一个特定终点的最短距离可以在弹出终点时直接返回不用等队列清空。这在图很大的时候能省不少时间。当然如果需要到所有点的距离那就老老实实跑完。最后说一个关于调试的建议。Dijkstra出错的时候结果往往不是完全错误而是某些节点的距离偏大。这种时候最好的调试方式是拿一个小图5到6个节点手动走一遍算法流程把每一步的dist数组和优先队列状态打印出来和你的预期对比。通常很快就能定位到问题——要么是松弛条件写反了要么是visited判断漏了要么是优先队列的元组顺序搞错了。小图上验证通过的代码放到大图上基本不会出问题。
