简介这是一份面向算法学习者与备考者的 Dijkstra 最短路径算法讲解文档围绕算法概述、原理与应用展开帮助读者理解单源最短路径问题的经典解法。文档先交代算法由荷兰计算机科学家 Edsger W. Dijkstra 于1956年提出适用于含非负权重边的有向与无向图随后按初始化、选择未访问节点、更新距离、重复执行四步拆解流程并说明采用最小堆优先队列管理待处理节点后时间复杂度可优化至 O((VE)logV)其中 V 为节点数、E 为边数。应用部分覆盖 GIS 路线规划、网络路由、社交网络分析和城市交通规划并延伸到地图导航、数据包转发、社交距离衡量等典型落地场景。压缩包共含1个PDF文件整体约71KB轻量易读已有99人学习。通过该文档可系统掌握算法思想、关键实现细节与常见应用方向适合课程复习、算法竞赛入门和面试前快速回顾。1. Dijkstra 算法为什么“先选最近的节点”就能一路贪心到底在带权图里一个节点一旦被当作“最短路径终点”确定下来算法就再也不会回头重看它。这在直觉上很冒险万一后来通过另一条绕路发现更短的方案怎么办Dijkstra 算法敢这么做全靠一条苛刻到近乎霸道的假设图里所有边的权重都不能是负数。因为边权非负任何从起点绕一圈再回来的路只会让累计长度不减一旦某个节点以当前最小距离出队后来者无论怎么绕都追不上。这个“贪心永不回头”的性质正是整套算法的正确性根基也是它和其他单源最短路径算法最本质的分界线。理解这一条之后再看初始化、选点、松弛、重复四步流程你看到的就不再是操作步骤而是一个由不等式撑起来的结构。2. 算法四步背后为什么“已访问”节点可以永久封存2.1 初始化、选点、松弛三个操作各司其职Dijkstra 的原始流程只有四句话把除起点外的所有节点距离字段设为无穷大起点设为 0所有节点标记为未访问在未访问节点里选出当前距离最小的那个把它标记为已访问对它的每个邻接节点做松弛更新重复直到没有未访问节点。看起来平平无奇关键在第二步它选的不是“任意节点”而是“当前距离最小的未访问节点”。这个选择是整套算法的引擎。每次把该节点访问掉等于宣告从起点到它的最短路径已经找到之后也不可能再被修改。所以“已访问”在这里不是“处理过了”而是“永久封存”。初始化那句“无穷大或一个较大的数”也很值得琢磨。如果真能用浮点无穷大那一切简单但你去翻工程代码很多地方会用一个大整数当无穷大。这里立刻出现一个坑这个“较大的数”必须大于任何可能的路径总长度。路径最多经过 V-1 条边假设最大边权是 W那真实距离上界最多是 (V-1)W。如果代码里选的数不够大松弛判断就可能在真正不可达的节点上发生错误更新造成假最短路径。这个细节后面在常见问题里还要再展开。第三步被称作“松弛”这个词来自数学优化里的“松弛条件”当你发现一条从起点经过 u 到 v 的路径比已知的 dist[v] 更小时就把 dist[v] 压到更小。注意松弛只会让距离减小不会变大而且它只依赖当前出队节点 u 的已经确定距离 d。整张图就是靠这个动作把“未确定的短距离”一层层传出去的。2.2 一个不等式链条非负权为什么是正确性基石为什么“永久封存”不是武断决定数学上可以构造一个反证链。假设当前已访问节点集合是 S未访问集合是 T算法从 T 里选出了距离 dist 最小的节点 u。反设存在另一条真正更短的路径 P从起点 s 到 u总权重 W 小于 dist[u]。因为终点 u 在 T 里这条路一定在某个地方第一次离开 S、进入 T记这个离开点为 x。那么从 s 到 x 的这一段除 x 外完全在 S 内算法在访问 S 中节点时一定已经对这整段做过松弛所以 dist[x] 不会超过这一段路径的权重。由于所有边权非负x 到 u 的后半段权重也大于等于 0。于是可以推出dist[x] ≤ s 到 x 的路径权重 ≤ s 到 x 的路径权重 x 到 u 的路径权重 W dist[u]这就意味着在 T 里存在另一个未访问节点 x它的 dist[x] 比被算法选中的 u 还要小。这与“u 是 T 中距离最小者”直接矛盾。于是反设不成立u 的 dist 就是真实最短距离。注意这条不等式链条在哪一步用到了“非负权重”就在那个“后半段 ≥ 0”的位置。如果后面有一条很负的边W 可以比 dist[x] 还小矛盾就消失了算法也就可能在做错误封存。这也是为什么 Dijkstra 对负权边如此敏感不是实现细节问题而是证明的根基断了。如果没有非负约束“选当前最近节点”只是一个看起来合理的启发式而不是可以保证最优的算法。很多人踩过“Dijkstra 遇到负权边照样跑出结果”的坑其实它不是跑了而是假答案跑得特别自信。2.3 它和广度优先搜索的关系退化是理解机制的钥匙如果把所有边权都改成 1dist 就等价于“从起点出发最少经过几条边”此时 Dijkstra 每次选最小 dist本质上就是广度优先搜索的逐层扩展。为什么 BFS 用普通队列而 Dijkstra 用优先队列因为权重相同且为正时先进队列的节点距离总是小于等于后进队列的FIFO 天然维护了排序引入大小不一的边权后某个后到的节点可能累计距离反而更小普通队列就不够了堆才开始起作用。这个退化关系也能解释很多问题为什么在有向无环图里做动态规划可以做到线性时间因为拓扑序给了你固定的处理顺序不需要像 Dijkstra 那样每次动态选择。而普通有环图里必须用堆。还有一点值得留意如果给所有边权同时加上同一个常数Dijkstra 的结果可能完全不一样。因为路径每多一条边就多承受一次常数增加边数不同的两条路径受到的影响不同。这提示我们边的权重必须直接反映真实代价不能乱做“平移变换”。3. 源码级实现从邻接表到优先队列复杂度是这样省下来的3.1 图怎么存邻接表、“无穷大”和下标习惯实现前先定数据结构。推荐邻接表的原因稀疏图下省空间遍历邻居时只动当前节点实际有的边。假设节点编号 0 到 n-1Python 里可以写 graph [[] for _ in range(n)]每一条有向边在 graph[u] 里保存一个 (v, w) 元组。如果是无向图就对称地加两条。距离数组 dist 初始化为 float(inf)起点 dist[start] 0visited 数组全 False。下面的代码是一个完整的最小堆实现注释里标出了容易写错的位置import heapq def dijkstra(graph, start): n len(graph) dist [float(inf)] * n visited [False] * n dist[start] 0 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 visited[v]: continue nd d w if nd dist[v]: # 松弛成功才更新距离 dist[v] nd heapq.heappush(pq, (nd, v)) # 允许同一个 v 多次入堆 return dist核心机制是“只更新、不删除”的惰性删除。heapq不支持把某个已经在堆里的元素改小所以代码在发现更短距离时直接 push 一个全新的(nd, v)。旧条目带着更大的 d 留在堆里没有任何坏处因为堆排序会让最小元素最先出堆等旧条目终于浮出来时v 多半已经被出队处理过visited[v]为 True这一行就把它静默丢弃。为什么 visited 要在出队时设而不是入队时设因为入队不意味着这个距离就是最终值。如果入队就标记已访问后续出现的更短版本会被错误挡住。标准实现的顺序必须是pop 出来一个有效版本 → 标记访问 → 处理邻边。另一个常见变体不用 visited而是用if d ! dist[u]: continue做同样的事情其逻辑是堆里弹出的距离如果已经不是当前 dist[u]说明这是过期版本丢弃。二者选一种即可代码里同时写的话d ! dist[u]在 visited 存在时基本永远不会触发但作为防御也不会有错。对于图下标从 1 开始的输入一种稳妥做法是把 dist 和 visited 长度设为 n1graph 也按 n1 初始化这样不用在每次访问时减一读边时直接存(u, v, w)即可。距离数组的大小多开一位不会影响堆里的比较。3.2 优先队列的复杂度O((VE)logV) 是从哪来的堆操作的时间账是这样算的初始化需要 O(V)。主循环里每个节点最多被正式处理一次因为入堆后可能残留多个旧版本但真正从 pop 到设置 visited 的处理只发生一次所以核心循环次数是 O(V)。每个节点出队时遍历它的邻接表所有邻居加起来正好是每条边被看一次所以遍历总代价 O(E)。松弛成功时会 push 一个新元组初始每条边最多导致一次成功的距离更新——一旦某条边让 dist[v] 变小v 的距离之后不会再由这条边产生更小值因此总 push 次数不超过 E。每次 push 或 pop 是二叉堆的 O(logV)。于是总复杂度O(V) O(E) 的邻居遍历 O( (V E) log V ) 的堆操作 O((VE)logV)这里有个容易被忽略的地方虽然“处理节点”是 O(V)但每次 pop 一个过期条目也是 O(logV) 的成本只不过它的总次数同样受 push 次数约束不会超过 E。所以过期条目多只会让常数变大不会改变复杂度级别。如果 E 很小稀疏图logV 项是主要开销如果 E 接近 V²稠密图O((VE)logV) ≈ O(V²logV)反而比朴素数组实现的 O(V²) 更慢。所以工程里没有绝对最优稠密图用邻接矩阵加朴素找最小稀疏图用邻接表加堆是教科书很少明说、但很实际的取舍。3.3 如何用一个小样例验证实现方向、重边和越界写完之后光看“能跑通”不够建议跑一组手工可验证的输入起点 0三条边 (0→1, 4)、(0→2, 1)、(2→1, 2)。真实最短路径到节点 1 是 123而不是直连的 4。如果实现正确dist[1] 应该等于 3并且堆里先 pop 出节点 2再由节点 2 松弛节点 1。这个样例专门用来检查“松弛是否真的发生”能拦截大量方向写反的 bug。再跑一个无向图用例两条边 (0,1,2)、(1,2,3)起点 0终点 2。无向图必须把 (0,1)、(1,0)、(1,2)、(2,1) 四条有向边都建出来。如果漏了一条边算法会表现为从 0 到 2 不可达。这是最常见的低级翻车原因但排查起来比算法本身的 bug 更隐蔽——因为你看代码看不出来只在结果里发现距离是无穷大。另一个边界是起点编号越界graph 长度是 n但 start 可能等于 n 或负数Python 会在 dist[start] 赋值时报 IndexError。好的实践是在函数入口断言0 start n。这种做法能帮你把图数据的 bug 提前暴露而不是让算法算出一堆错误距离。4. 踩坑排查负权边、重边和堆里的幽灵节点4.1 负权边不崩溃但答案自信地错下去现象图上有一条负权边程序正常终止dist 数组也填满了但是某个节点的结果比手工推演的最短路径更长。甚至可能出现荒谬结果一条经过负权边的路径总权重比 0 还小起点自己的距离都比不过绕路版本。原因Dijkstra 的“出队即永久”证明在最核心的“后半段 ≥ 0”处断了。负权边可以让一条路径先长后短算法在某个节点还没被更短路径发现前就提前把它封存之后即使有一条更短的路经过它也会因为 visited 而拒绝访问。程序没有任何异常机制能感知这个错误所以它是算法级的逻辑错误而不是运行时错误。解决如果输入图可能含负权边就不要用 Dijkstra。改成 Bellman-Ford 对每条边做 V-1 轮松弛能容忍负权但要求没有负环或者用 SPFA在大部分实际稀疏图上表现很好但要小心构造数据把它拖到指数级。如果一定要保留 Dijkstra 的高效率可以先用势能变换把权重视为非负给每个节点算一个势然后对边权做w w h[u] - h[v]这样新边权非负且最短路径解不变。代价是要先跑一次 Bellman-Ford适合多次查询的预处理场景。注意网上有些说法是“Dijkstra 不能处理负权边所以遇到负权边应该用 A* 或交通工程模型”这混淆了概念。A* 同样依赖非负启发式并不能解决负权正确分类是Dijkstra 用于非负Bellman-Ford 用于负权但无负环SPFA 是 Bellman-Ford 的队列优化。4.2 重边和自我环你到底有没有把最优边保留下来现象同一对节点之间有多条不同权重的边程序输出的路径绕了远路明明有条直连边更短却没被用上。原因不同输入格式的“读入”策略不同。如果使用邻接矩阵且读边时直接weight[u][v] w后读入的边会覆盖先读入的边。当输入里先出现大权重、后出现小权重时覆盖掉的是小权重还是大权重取决于输入顺序结果就不稳定。邻接表不会覆盖但如果你在一开始做了“只保留最后一条”的去重逻辑同样会把最优边丢掉。无向图漏加反向边更隐蔽所有测试都是从左往右的路径一旦目标反过来距离数组立刻报无穷大。解决最稳妥的建图规则是“邻接表保留全部边让松弛自己选最优如果要压空间同一条有向边取最小权重而不是最后读入的那条”。自环可以直接跳过在非负权下dist[u] w dist[u]永远不会触发松弛留着只会浪费邻居遍历。无向图在加边时写一眼就能看到双向的辅助函数别手写两次很多工程 bug 都出在“这次是无向图但只 add 了一次”的低级疏忽上。4.3 堆里的幽灵节点为什么代码不慢但内存涨得飞快现象同样规模的图用优先队列的实现跑的比朴素扫描还慢内存占用高出好几个量级但结果正确。检查代码发现每次松弛成功就 push同一个节点在堆里可能有七八个版本。原因这就是惰性删除的自然代价。标准堆没有 decrease-key或者说实现 decrease-key 要有额外索引结构。为了简化代码牺牲了一部分空间来换取逻辑简单旧节点条目不删堆大小最多会被撑到 O(E)。当图里节点更新频繁、边数又多时过期条目占比可能变得很高每次 pop 都在清垃圾。解决三个层面。第一先确认 visited 拦截逻辑真的生效后面排着队的过期条目只 pop 不处理这是最基本的。第二如果堆过大影响性能可以对堆做重建当堆中的元素数量超过某个阈值比如 E/2时把当前有效节点和距离重新建堆这个操作是 O(V) 的换回后续 O(logV) 的干净堆。第三如果对常数特别敏感用索引堆或者手写带 decrease-key 的二叉堆但代码复杂度会明显上升。大多数竞赛和工程场景惰性删除加 visited 已经够用属于“拿空间换实现简单”的合理设计。4.4 无穷大选的不好溢出、误差和假的不可达现象在 C/Java 里设INF 2147483647某个可达节点加上一条边权后溢出成负数松弛条件nd dist[v]反而成立于是一堆节点被更新成负距离整个 dist 数组像中了毒。Python 里 int 无溢出但如果把距离设成 float(inf)边权却用整数比较时也没问题一旦某处用 Decimal 或高精度类型反而会出现类型不一致的 TypeError。原因原文里的“无穷大或一个较大的数”到了工程里必须落地为具体数字。这个数字不仅要“大”还要满足INF 加上最大边权后不溢出且仍然大于任何真实路径长度。INT_MAX 加上正数马上溢出有符号数回绕表现可能就是负值。另一个隐患是最大路径长度上界估算错误如果图有 V 个节点不管走多少条边最短路径不会经过重复节点所以上界是(V - 1) * max_weight这个数本身可能超过 INF 的选择。解决推荐优先用真正的无穷大Python 的float(inf)Java 用Long.MAX_VALUE / 2C 常用0x3f3f3f3f因为两个这样的数相加还在 int 范围内并且它比绝大多数输入权重都大。同时在每个节点的松弛处理前加一行if dist[u] INF: continue直接跳过不可达节点既省时间又避免在不可达节点上做无意义加法。浮点权重场景下把严格小于改成nd dist[v] - 1e-9可以避免由舍入误差导致的反向更新如果数据本来就是整数不要转浮点。5. 应用场景拆解地图导航、网络路由和社交距离为什么都选它5.1 地图导航最短路径本质上是最小代价路径在地理信息系统里道路网被抽象成一张有向或带权图路口是节点路段是边边的权重可以是物理距离、预计行驶时间、燃油消耗甚至实时拥堵指数。Dijkstra 在这样一个图上算出的“最短路径”准确说是“总权重最小路径”。导航产品不会真的在整个国家路网上每次都跑一遍常见优化是把路网分块预处理或先用估值函数做 A* 搜索但最有代表性的底层核心仍是 Dijkstra。这里有一个非常工程化的扩展如果边权代表行驶时间且交通信息每五分钟更新一次你不可能每次都重新全局扫描而是希望做增量维护只重算受影响的那个子区域。理解了这个你就明白为什么城市级导航会有“区域级”“路径级”缓存分层。另一个需要建模的细节是道路单向约束。现实中的高架桥、单行道让导航图天然是有向图如果把它错误建模成无向图Dijkstra 会给出一些实际上无法行驶的“抄近路”方案。反向边只存在允许双向通行的路段上。这一点和社交网络很不一样社交网络中的“好友”关系如果对称就适合无向但关注关系是单向的必须显式建模成有向边。图模型的选择直接决定了算法能不能反映真实约束。5.2 网络路由路由器每人都跑一棵最短路径树链路状态路由协议是 Dijkstra 的经典生产级使用场景。每个路由器通过链路状态通告收集全网拓扑形成自己的链路状态数据库然后以自己为根运行 Dijkstra得到一张到网内所有节点的最短路径树路由表里“下一跳”字段正是由这棵树产生。链路权重是人为设定的度量通常是带宽的反比或者管理距离但协议明确规定链路代价必须是非负整数区间这等于给 Dijkstra 的正确性前提做了人工背书。这个场景对我们理解算法有两个启发第一一旦某条链路状态变化需要立刻重算所以最坏情况下 Dijkstra 的 O((VE)logV) 直接决定网络收敛时间第二路由器内存和 CPU 是受限的所以工业实现往往用斐波那契堆甚至数组优化来降低常系数。把算法从“能用”到“好用”差距基本都在这些代价敏感的实现选择上。而且链路状态数据库要求全网同步如果某个路由器收到的通告不完整Dijkstra 算出的树就是残缺的数据包会被黑洞。所以工程上每个路由器会先做“信息年龄”检查超期通告直接丢弃然后触发全量重计算。这说明算法本身可靠但喂给算法的拓扑数据必须同样可靠。5.3 社交网络最短路径作为“社交距离”的度量社交网络分析里两个用户之间的距离可以被定义为“至少经过多少次关系链才能建立连接”。如果每条关系链的权重都是 1这就是无权图上的最短路径BFS 就够了但如果关系强度被打分比如“好友之间的互动强度”作为边权Dijkstra 就能算出一个带权重的社交距离。越是密集的社交网络越不适合直接跑全局 Dijkstra节点几亿、边几十亿内存都放不下。实际通常做采样或并行分区但算法原理仍然出现在各类图计算框架的单机子图处理里。更有用的一个技巧是提前终止如果你只关心一个人到另一个人的社交距离可以不用等所有节点都访问完一旦目标节点被标记为已访问它的距离就是最终答案直接返回。这个优化在交通和地图导航里同样成立实现起来只需要在 while 循环里判断目标节点是否已访问。很多初学实现会坚持跑完全部节点把 O((VE)logV) 白白浪费在无关区域。提前终止还有一个推论如果只求单点对堆里可能保留了大量比目标更大距离的节点它们永远不会被处理。这个特性让 Dijkstra 非常适合同时刻画“从某个枢纽辐射出去的前 K 近节点”社交媒体中的“身边的人”推荐就可以这么做。5.4 城市交通规划换乘惩罚和多目标权衡城市交通中站点是节点班次或线路是边权重是乘车耗时。直接套 Dijkstra 会得到一条“时间最短但换乘十次”的路线因为每次换乘在图上表现为进入新线路的边其权重可能只有几分钟但人的体感比坐车二十分钟还难受。工程师的常见操作是给换乘边加上一个惩罚权重比如 5 分钟代表换乘步行和等待的机会成本。调整惩罚值会改变整条最短路径的形态这就是“权重设计”对算法结果的影响比算法本身更容易被忽视。多目标问题也可以这样处理距离和时间是两个互相矛盾的指标Dijkstra 只支持一个标量排序所以工程上把两个目标做加权和变成一个综合代价。如果你要在两个指标下得到帕累托前沿Dijkstra 就不够用需要多目标扩展。明白这个边界是理解算法应用场景的前提不是算法不行是它天生只解决单标量最短路问题。站在规划者的角度Dijkstra 还能用来做“可达性分析”改变某个公交站的位置会对哪些区域的可达性造成最大影响可以在原图上删除节点或降低边权后重新计算观察受影响范围。这也是城市规划中比较常见的定量分析手法本质上是把最短路算法当作一个“模拟器”反复调用。6. 设计取舍为什么 O((VE)logV) 是那个“够好”的答案Dijkstra 的成立建立在“非负权”和“贪心封存”两个强假设上。表面上它放弃了负权图的通用性换来的是几乎线性的时间这个交易被整个工业界接受了近七十年。Bellman-Ford 能处理负权但复杂度 O(VE)在稠密图上约等于 O(V³)和 Dijkstra 不在一个量级SPFA 常数小但在最坏情况下不稳定。Dijkstra 之所以成为默认选项不是因为它更聪明而是因为它把“可用的计算代价”放在了一个足够低的位置。如果进一步观察整个算法就是一个排序问题堆只是维护“当前距离最小的未访问节点”这一动态顺序的数据结构。换成数组扫描是 O(V²)换成二叉堆是 O((VE)logV)换成斐波那契堆是 O(EVlogV)。你会看到复杂度并不是一个固定值而是数据结构选择决定的。二叉堆之所以最流行是因为实现只有几十行、常数小、且对大多数图的实测表现足够好斐波那契堆虽然理论更漂亮常数和实现复杂度让它沦为理论工具。这种“理论最优不是工程最优”的取舍比其他算法更能说明问题。我一般会用一个很笨的验证方法随机生成一张 N2000、E20000 的非负权稀疏图分别跑朴素数组版和堆版然后逐步增大 N 观察耗时曲线。两条曲线会有一个明显的交叉点。这个交叉点告诉你教科书上的复杂度只是渐近意义常数在真实数据集上可能让你换实现。如果你也想深入这套机制这份 PDF 里的概述、原理和应用三节已经把算法主干讲完了真正的深度来自你自己动手把代码跑起来在负权、重边和幽灵节点上各翻一次车比任何讲解都来得快。从那以后我每次写带权图最短路都强制先做三件事确认所有边权非负、检查图的重边和双向边、在堆实现里保留 visited 数组。这三条预防性检查帮我拦下了至少十次莫名其妙的翻车。希望帮到你。本文还有配套的精品资源点击获取