简介这份PDF围绕Dijkstra算法展开系统讲解其概念、原理与典型应用适合算法初学者、备考数据结构与算法的学生及需要快速回顾单源最短路径的开发者。内容以优先队列实现为线索清晰拆解初始化、节点选择、距离更新与重复迭代四个关键步骤并给出时间复杂度O((VE)logV)的推导说明同时结合路线规划、网络路由、社交网络分析和城市交通规划等场景帮助理解贪心策略的落地方式。资源为单个PDF文件压缩包仅71KB内容精炼便携。目前已有99人学习下载可作为入门第一份资料或考前速查手册。阅读后可掌握Dijkstra算法的完整流程、适用条件与边界限制学会在实际问题中正确选择并使用该算法。1. Dijkstra算法为什么「只看眼前」的贪心反而能证明全局最优Dijkstra算法有一个反直觉的地方它每一步都只挑「当前看起来最近」的节点下手完全不考虑这条最近的路会不会在下一步走进死胡同。这种鼠目寸光的贪心策略放到别的场景里大概率翻车但放在单源最短路径问题上它却被数学证明是全局最优的。很多人十分钟就能背下它的四步流程——初始化、选最近、松弛邻居、重复——但一被追问「为什么贪心不会错过真正的最短路径」「为什么负权边一进来就出问题」就卡壳。这份PDF只讲了三件事算法概述、原理、应用。我沿着这三层往里拆把背后的状态机设计、堆优化和现实建模机制逐一扒开。搞懂这套机制之后你再看A*、看链路状态路由都会顺畅很多。2. 从初始到闭环Dijkstra的状态机设计与松弛机制的单调性2.1 四个关键状态dist数组、visited标记、候选集合与松弛条件Dijkstra维护的数据结构其实非常克制只有四样东西一个dist数组一个visited标记集合一个候选节点集合工程上常用优先队列承载以及一条「松弛」规则。这四样不是随便凑的它们恰好对应了算法能收敛的四个前提有界初值、单调更新、选取策略、终止条件。dist数组的初始值很有讲究。除了源点设为 0其余全部设为无穷大代码里常用float(inf)。这个「无穷」不是摆设它表达的是「尚未发现任何可行路径」的信息边界。visited标记则区分了两类节点一类是「最短路径已被锁死」的已确认节点另一类是「还在待定区」的候选节点。注意Dijkstra 从不会回头去修改一个已确认节点的dist——这是它与 Bellman-Ford 最本质的差别后者每一轮都可能刷新所有节点的距离。候选集合是这个状态机的引擎。每轮从候选集中取出「当前dist最小」的节点 u把 u 标记为已访问然后检查 u 的每一条出边如果经过 u 到达邻居 v 的路径长度比 v 当前记录的dist更短就更新 v 的dist。这个操作就是「松弛」英文叫 relax因为你可以把它想象成把一根绷紧的绳子放松到更短的位置。这里有一个常见的误解很多人以为 Dijkstra 是「从起点开始一圈圈往外扩」像 BFS 那样按层推进。实际上 BFS 是等距扩散而 Dijkstra 是按「累计权重」扩散扩散顺序和几何距离完全没有关系。某个节点可能拓扑上离源点很远但因为路径权重小反而比近邻节点更早被确认。2.2 松弛的单调性为什么「先选最近」不会错过更优解Dijkstra 能work的核心在于一个关键论证当节点 u 被从优先队列中弹出时它当前的dist[u]就已经是全局最短路径长度不会再被任何后续操作更新。「贪心不翻车」这个结论完全建立在边的权重非负之上我们来推一遍。假设 u 刚被弹出此刻它的dist[u] d。反设真正的最短路径比 d 更短记这条真实最优路径为 P。P 一定从源点出发一路延伸最终到达 u。考察 P 上第一次从「已确认节点集合」跨到「未确认节点集合」的那条边 (x, y)因为在 P 中源点到 y 的累计长度是「源点到 x 的累计长度 w(x,y)」而源点到 x 的那一段本身就是已确认的最短距离。所以 P 在到达 y 时其累计长度已经 dist[y]。但 y 是一个未确认节点既然 u 是从候选集中弹出的最小距离节点那么dist[y] d。又因为边的权重非负P 从 y 到 u 的剩余路径长度必然 0。于是整条 P 的长度 dist[y] 剩余长度 d。这和「P 比 d 更短」矛盾。所以弹出时 u 的dist就是最终答案。这个证明的命门在哪就在「剩余路径长度必然 0」这句话上。如果存在负权边P 剩余部分的长度可以是负数前面的不等式链就断了。这就是为什么 Dijkstra 一遇到负权边就会给出看似合理的错误答案——它不是崩溃而是悄悄算错这是比报错更难排查的坑。2.3 收敛条件为什么必须「重复直到全部访问」才算完Dijkstra 是逐点确认的每次从堆里弹出一个节点就永久锁死一个节点的最短路径。这意味着整个算法的过程就是一次一次的「弹出 锁死」直到所有节点都被标记为已访问。中间任何时候停下来都只拿到一张残缺的确认表部分节点是最终答案剩下的还停留在「当前已知最短」的待定状态。这份PDF把循环终止条件描述为「重复步骤2和3直到所有节点都被访问过」这在逻辑上是准确的。但工程实现里有一个非常实用的等价变体如果只需要从 s 到 t 的单终点最短路径可以在 t 被弹出的那一刻直接返回因为 t 一旦被确认它的dist就已经是最终答案后面再松弛别的节点也不会改变它。这个「提前退出」优化在导航场景中能把计算范围限制在一个以 s 为中心的局部区域而不是算完整张图。还有一个循环不变式值得一提每次迭代开始时所有已访问节点的dist都已经是全局最优所有未访问节点的dist都是「经由已访问区域所能达到的当前最优」。整个算法的过程就是把这个「已确认区域」一圈圈扩大直到覆盖全部节点。这个过程和拓扑排序没有关系它不要求图是有向无环的只要所有权重非负有环也能正确收敛。3. 从朴素扫描到二叉堆O((V E)logV) 的实现跃迁3.1 朴素实现为什么邻接矩阵版本会卡在 O(V²)如果完全不带任何数据结构Dijkstra 每轮要从「未访问节点」里找dist最小的那个最直接的做法就是线性扫描一遍复杂度 O(V)。总共要选 V 次所以光是「找最小」这一步就是 O(V²)。再加上遍历所有边进行松弛的 O(E)整体复杂度 O(V² E)。这个版本在稠密图上其实不算差。所谓稠密图就是边数 E 接近 V² 的图此时 O(V² E) 基本就是 O(V²)没法更好了。邻接矩阵配合 O(V²) 的朴素实现代码极短逻辑直白不太容易写错。很多算法教材和竞赛初学者都用这个版本入门它最大的问题不是时间复杂度而是空间邻接矩阵要存 V×V 个数V 到一万以上就直接内存爆炸。而当图变稀疏E 远小于 V²每轮线性扫描的代价就变得不可接受了。想象一张有 10000 个节点、12000 条边的稀疏图V² 是一亿真正需要处理的边只有一万多条绝大多数扫描都浪费在「比较一堆仍然为无穷大的 dist」上。稀疏图在真实世界才是常态道路网络的每个路口只连接周边几条路社交网络里一个人的好友数远小于全网用户数。于是有了堆优化版本。3.2 二叉堆介入把「反复找最小」从 O(V) 压到 O(logV)优先队列通常就是二叉最小堆解决的核心问题只有一个动态维护候选集里的最小值。Dijkstra 的「找最小」不是一次性的而是每轮都要做且每轮之后还要不断把新的候选(距离, 节点)插进去。堆这个结构正好两个操作都是 O(logV)弹出最小值插入新元素。为什么整体是 O((V E)logV)拆开看每个节点最多被弹出一次确认后不再入堆所以弹出操作总代价是 V 次 * O(logV) O(VlogV)每条边最多触发一次成功松弛一旦松弛成功就会入堆所以插入操作总数不超过 E 次每次 O(logV)合计 O(ElogV)。两相加起来就是 O((V E)logV)。注意一个细节一个节点可能被重复入堆。比如节点 v 先被路径 A 松弛到距离 10入堆后来又有一条更短的路径 B 把它松弛到 6再次入堆。堆里会同时存在 (10, v) 和 (6, v) 两条记录。弹出时先遇到哪条是「不确定」的所以实现里必须有「过期记录跳过」机制。最常见也最干净的做法维护一个visited集合或者弹出时比较d dist[u]就 continue。如果忘了这个判断程序不会报错但堆里会堆积大量永远不处理的垃圾记录性能在稀疏大图上会肉眼可见地劣化。3.3 带注释的 heapd 实现每一行都在做什么下面这份实现是工程中最常见的写法逻辑先看不带任何封装import heapq def dijkstra(graph, start): # graph: {节点: [(邻居, 权重), ...]}邻接表 dist {node: float(inf) for node in graph} dist[start] 0 # 优先队列元素是 (当前最短距离, 节点) pq [(0, start)] visited set() while pq: d, u heapq.heappop(pq) # 弹出当前距离最小的候选 if u in visited: # 过期记录u 已被更短路径确认过了 continue visited.add(u) # 锁死 u 的最短路径 for v, w in graph[u]: # 松弛 u 的所有出边 new_d d w if new_d dist[v]: # 只有更短才更新保证 dist 单调下降 dist[v] new_d heapq.heappush(pq, (new_d, v)) return dist机制上有三个关键决策值得展开说。第一visited的检查位置。它会保证每个节点只被「确认」一次配合堆顶取最小就实现了前面证明过的「弹出即最优」性质。如果你把visited.add(u)挪到heappush之前做也就是在松弛时发现某节点还没访问就立刻标记那算法会直接错掉因为松弛时的new_d不一定是该节点的最终最短距离后面可能出现更短路径把它的距离再次刷新而它已经被锁死了。第二if new_d dist[v]这个条件。它保证了只有「真正变短」的路径才会被记录和入堆这是dist数组单调递减的来源。有些实现会写成允许重复松弛相同的距离后果只是堆里多些无用的相等记录不影响正确性但拖慢速度属于典型的「正确但低效」。第三为什么用邻接表而不是邻接矩阵。堆优化版本的复杂度里E 只在「遍历边」时出现一次这就要求你能高效拿到每个节点的邻居列表。邻接表的空间是 O(V E)与边数线性相关这也是它成为稀疏图默认选择的原因。4. 现实建模路线规划、路由协议与社交距离背后的 Dijkstra4.1 路线规划把城市道路变成一张带权图地图导航是最直观的 Dijkstra 落地场景。路口是节点路段是边权重可以是物理距离、预计行驶时间甚至可以是「考虑拥堵后的综合代价」。为什么这种场景天然适用 Dijkstra因为道路权重几乎总是非负的——你不可能开一条路让路程「倒欠」几公里。这个前提在地理世界里永远不会被破坏。但导航软件会在此基础上叠加两个工程优化。第一个就是我们前面提过的「目标点提前退出」导航只需要一条从当前位置到目的地的路径不需要跑完整张城市图。当目的地节点从堆中被弹出时算法直接停止。第二个是方向性剪枝以起点和终点做一个椭圆包络超出这个范围的节点根本不需要入图。这也是为什么你开着导航时它能快速响应而不用等上几十秒——它算的从来不是全城最短路而是一个受限范围内的局部最短路。值得注意的是导航中的「最短」未必是距离最短而是「代价最小」。给每条边设权重为当前时段的平均车速的倒数Dijkstra 算出来的就是「预计最快路径」。这是一种建模的选择图算法不关心权重的物理含义它只要求权重非负且可加。理解了这一点你就明白为什么同一套算法既能算公里数又能算时间还能算油耗。4.2 网络路由链路状态协议家族的核心计算组件计算机网络里的距离向量和链路状态两大路由思路后者直接内嵌了 Dijkstra。链路状态路由协议的工作方式可以拆成三个阶段每台路由器都向全网泛洪自己的链路状态通告LSA宣告「我连了谁、到每个邻居的代价是多少」每台路由器收齐这些通告后就能在本地拼出全网的拓扑视图然后对这张视图运行 Dijkstra路由领域常叫 SPF 计算Shortest Path First算出以自己为根的到所有目标的最短路径树。这里的权重取什么常见的是接口带宽相关的度量值带宽越大代价值越小。这样算出来的「最短路径」实际上是「最快路径」能让流量优先走高速链路。这个场景对 Dijkstra 的依赖是刚性的拓扑变化时要快速重新计算而 Dijkstra 堆优化版本V E)logV 的复杂度足以应付骨干网络的规模。但路由器场景还有一个朴素版本不做的事它需要的不只是距离值还要完整的下一跳信息。所以路由器在运行 Dijkstra 时不仅维护dist数组还要在每次松弛成功时记录「到达 v 的上一个节点是谁」。算法结束后顺着这些前驱指针回溯就得到了一棵以自己为根的最短路径树。这棵树被装进转发表后续数据包只需查表即可转发不用每次重新计算。4.3 社交网络中的最短路径从「好友链」到「社交距离」社交网络分析用 Dijkstra 的动机很有意思把人和人之间的关系看作边边的权重表示「互动的成本」或「距离」。互动频繁的两个人之间权重小几乎不互动但认识的人之间权重大。那么两人之间的最短路径就可以解读为他们之间的「社交距离」——这个值越小说明通过社交关系链接触彼此的代价越低。在实际计算中这类应用通常不会直接跑完整 Dijkstra。因为社交图的规模动辄上亿节点全量跑一遍不现实所以工程上更爱用双向搜索从起点和终点各跑一层 Dijkstra两个搜索前沿相遇时合并结果。这让搜索空间从指数级扩散变成两棵较浅的树代价是必须额外处理双向搜索的终止条件和路径拼接逻辑。这个变体本质上是在「算得准」和「算得快」之间取平衡而平衡点完全取决于图的真实直径。4.4 变体与扩展从单源到多源、从最短路到割裂度如果需求是「从多个起点出发找到每个节点最近的起点」朴素的思路是对每个起点各跑一遍 Dijkstra复杂度成倍增长。更聪明的做法是引入「超级源点」创建一个虚拟节点用 0 权边连到所有真实起点然后对这张新图只跑一遍 Dijkstra。这样算出来的dist[v]自动就是「v 距所有起点最近的那个距离」。这个技巧在交通规划中很常用比如计算一个城市里所有居民点到最近医院或最近地铁站的距离分布。再往外延伸Dijkstra 还能当作评估网络脆弱性的工具。如果把某几个节点删掉重跑一遍比较前后各点距离的变化就能量化出「这个节点对保持网络连通有多重要」。这种玩法在电力网络、物流配送网络的规划里都有应用。下表把这几个应用场景的建模参数做一个横向对比方便看出同一套算法的不同「皮肤」应用场景节点含义边的权重Dijkstra 的特殊处理地图导航路口距离/行驶时间目标点提前退出、区域剪枝路由器 SPF路由器带宽倒数/时延记录前驱构建最短路径树社交距离用户互动成本双向搜索控制规模多源可达居民点/设施点实际距离超级源点归约成单源5. 避坑手册负权边、重复入堆与稠密图的经典翻车现场5.1 负权边算法不报错但结果悄悄变错现象图里存在一条负权边Dijkstra 跑完程序正常退出给出的路径看着也挺合理但和暴力枚举对比后发现不是最短的那条。原因前文证明贪心成立时依赖「剩余路径长度 0」这个前提。负权边出现后一个已经被确认的节点可能在后续被一条「先经过远处节点、再通过负权边绕回来」的路径刷新得更短但 Dijkstra 的visited标记早就把它锁死了不会回头更新。问题在于这类错误没有任何运行期信号它输出的是一个合法的、但并非最优的路径。解决图里有负权边时直接放弃 Dijkstra改用 Bellman-Ford适合稠密图、能检测负环或 SPFA负权边的稀疏图上通常更快。判断标准很简单建模时如果任何边的权重可能小于 0就别用 Dijkstra这是设计层面的取舍而不是调参能修好的问题。5.2 堆里的过期记录正确但性能崩坏现象小规模图上测试没问题换到几万节点的大图后内存飙高、运行时间比朴素实现还慢但结果依然是正确的。原因一个节点 v 可能被多次松弛、多次入堆。如果弹出时不判断记录是否过期堆里会越积越多无效记录堆操作的对数复杂度还是对的但 V 和 E 的常数被放大了几倍甚至几十倍。最坏情况下堆里可能堆积 O(E) 条记录空间复杂度从理想的 O(V) 退化到 O(E)。解决在弹出后立即检查d dist[u]则直接 continue或者在松弛时维护一个visited集合做去重。二者取其一即可。这个坑很难通过单元测试发现因为结果完全正确只有压测大图才会露出马脚。很多血泪经验都来自这里明明用的堆优化速度却感人最后发现是过期记录没处理。5.3 稠密图硬上堆优化优化反而成了负优化现象一个节点四五百个、几乎全连通的图堆优化版本跑得比朴素的 O(V²) 版本还慢。有人开始怀疑 Python 的heapq有问题但实际上问题出在复杂度本身。原因时间复杂度分析要看主导项。稠密图里 E ≈ V²堆版本的 O(ElogV) 约等于 O(V²logV)反而不如朴素版本的 O(V²)。堆优化只在稀疏图上优势明显在稠密图上它多出来的 logV 因子是纯开销还附带堆操作的常数。解决稠密图用邻接矩阵加朴素扫描的实现每轮线性找最小总复杂度稳定 O(V²)稀疏图再用堆优化版。实践中可以简单估算如果 E 接近 V² 的数量级别用堆如果 E 和 V 同数量级堆是必须的。判断错了性能就反过来了。5.4 只求单终点却跑完全图白白浪费算力现象只需要从 A 到 B 的最短路径代码却把整张图所有节点的最短距离都算出来了。图很大时这个浪费非常明显。原因对 Dijkstra 的理解停留在「所有节点都被访问过才算结束」。实际上终点一旦被弹出它的最短距离就已经被确认继续跑后续节点不会改变结果。解决主循环里加一个提前退出条件如果u target直接返回dist[u]。很多地图导航的响应速度都来自这个简单的优化。别忘了附带处理另一种「翻车」如果终点在图上根本不连通堆会弹空此时应返回「不可达」而不是报错。6. 从 Dijkstra 到 A*贪心策略的极限与下一步取舍如果只记住一件事那就是 Dijkstra 的最优性来自「无信息贪心」它不知道目标在哪只是忠实地按距离从小到大扩展。这种无差别扩散保证了正确性但也意味着在单终点场景下它会向各个方向均衡推进白白浪费大量计算在一些和目标毫不相关的区域。A* 的思路就是在 Dijkstra 的排序键里加一个启发项从优先队列弹出时比较的不再是dist[u]而是dist[u] h(u)其中h(u)是「估计从 u 到终点的剩余代价」。当h(u)恒为 0 时A* 就退化成了 Dijkstra。而当h(u)是一个可采纳的、且尽量接近真实代价的估计时A* 能大幅压缩搜索范围。地图导航里常用的欧几里得距离、曼哈顿距离都是天然可采纳的启发函数因为「直线距离永远不会超过实际路径长度」。这就是 Dijkstra 留下的最大设计遗产它把「最短路问题」抽象成了「用非负权重图 单调距离更新 最小值优先扩展」三个组件的组合。任何一种算法只要调整其中一个组件就能派生出新的行为。A* 改了扩展顺序双向搜索改了图的方向多源 Dijkstra 改了初始化方式。理解这三个旋钮你几乎可以把这套机制改造成任何你需要的形状。这些取舍也解释了为什么 Dijkstra 至今没有被淘汰它不要启发函数就要求更少的前提它不能处理负权就换来更强的稳定性保证它每步都算全局更新就显得更容易被并行化。算法没有绝对的好与坏只有「在什么约束下选择什么代价」。从我用 Dijkstra 建模路线规划、再到改造它计算多源可达性的经历来看现在每次动手前我都会强制自己先回答三个问题图里有负权边吗图是稠密还是稀疏我需要全量结果还是单终点结果这三个答案直接决定用哪个版本、要不要堆、能不能提前终止。你自己上手时也先问完这三个问题再写代码。希望帮到你。本文还有配套的精品资源点击获取