教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载本指南以「算法通关手册AlgoNote」单源最短路径一章节为核心系统讲解单源最短路径问题的定义与适用场景并深入拆解Dijkstra 算法的朴素实现与堆优化实现两套完整可运行的 Python 代码。读完本文你将掌握如何在带权图中正确选择最短路径算法、推导两种实现的时间复杂度并结合仓库内的 LeetCode 实战题解完成从理论到刷题的闭环。1. 单源最短路径问题概述单源最短路径Single Source Shortest Path在一个带权图 $G (V, E)$ 中给定一个起点源点$v$找到从这个源点出发到图中其他所有顶点的最短路径长度。这里的「最短路径」指的是路径上所有边的权重之和最小。简单来说单源最短路径问题就是从一个点出发如何走到其他所有点并且让每条路径的总权重最小。这个问题在实际生活中非常常见比如地图导航如何从一个城市到其他城市距离最短网络路由数据包如何选择最快的路径传输通信网络优化等常用的单源最短路径算法有以下三种算法适用场景核心思路Dijkstra 算法所有边权都为非负数贪心策略每次选择当前距离源点最近的未处理节点并用它更新其它节点的最短距离Bellman-Ford 算法可处理有负权边的图多次遍历所有边不断用更短的路径更新节点距离逐步逼近最短路径SPFA 算法负权图Bellman-Ford 的队列优化每次只处理那些距离被更新过的节点通常效率更高不同算法适用于不同类型的图。根据实际问题的特点选择合适的算法才能高效地求解单源最短路径问题。本文重点展开第一种Dijkstra其余两种算法的细节在后续章节 单源最短路径二 中详细讲解。2. 朴素 Dijkstra 算法2.1 Dijkstra 算法的核心思想Dijkstra 算法核心思想每次选出距离起点最近、最短路尚未确定的节点用它去尝试更新其它节点的最短距离逐步扩展直到所有节点的最短路径都确定。Dijkstra 算法是解决单源最短路径的经典方法适用于所有边权为非负数的图。它的流程很简单每次从未确定最短路的节点中选出距离起点最近的那个把它的最短距离「锁定」并用它去更新其它节点的距离。重复这个过程直到所有节点的最短路径都被确定。本质上Dijkstra 算法是一种贪心策略每一步都相信当前能确定的最短距离认为已经确定的节点最短路不会再被更优路径更新。这样一步步扩展最终得到从起点到所有节点的最短路径。需要注意的是Dijkstra 算法不能处理有负权边的图。如果图中存在负权边最短路径可能会被后续的负权边更新导致算法失效。这种情况下应使用 Bellman-Ford 或 SPFA 算法。2.2 Dijkstra 算法的实现步骤初始化距离数组 $dist$将起点 $source$ 的距离设为 $0$其余所有节点的距离设为无穷大。准备一个访问集合 $visited$用于记录哪些节点的最短路径已经确定。每次从未访问的节点中选出距离起点最近的节点将其加入 $visited$。用这个节点尝试更新所有相邻节点的最短距离。重复步骤 3 和 4直到所有节点都被访问。最终距离数组中即为起点到所有节点的最短路径长度。如果某些节点无法到达距离仍为无穷大。2.3 朴素 Dijkstra 算法实现代码class Solution: def dijkstra(self, graph, n, source): Dijkstra 算法求解单源最短路径 :param graph: 邻接表表示的有向图graph[u] {v: w, ...} :param n: 节点总数节点编号从 1 到 n :param source: 源点编号 :return: dist 数组dist[i] 表示源点到 i 的最短距离 # 距离数组初始化为无穷大 dist [float(inf)] * (n 1) dist[source] 0 # 源点到自身距离为 0 visited set() # 已确定最短路的节点集合 while len(visited) n: # 在所有未访问的节点中选择距离源点最近的节点 current_node -1 min_distance float(inf) for i in range(1, n 1): if i not in visited and dist[i] min_distance: min_distance dist[i] current_node i # 如果没有可处理的节点说明剩下的节点不可达提前结束 if current_node -1: break visited.add(current_node) # 标记当前节点为已访问 # 遍历当前节点的所有邻居尝试更新最短距离 for neighbor, weight in graph.get(current_node, {}).items(): if neighbor not in visited: if dist[current_node] weight dist[neighbor]: dist[neighbor] dist[current_node] weight return dist # 使用示例 # 构建一个有向图邻接表表示 graph { 1: {2: 2, 3: 4}, 2: {3: 1, 4: 7}, 3: {4: 3}, 4: {} } n 4 # 节点数量 source 1 # 源点 dist Solution().dijkstra(graph, n, source) print(从节点, source, 到其他节点的最短距离) for i in range(1, n 1): if dist[i] float(inf): print(f到节点 {i} 的距离不可达) else: print(f到节点 {i} 的距离{dist[i]})2.4 朴素 Dijkstra 算法复杂度分析时间复杂度$O(V^2)$。外层循环每次选择一个未访问且距离最小的节点共进行 $O(V)$ 次。每次选择最小距离节点时需要遍历所有未访问节点复杂度为 $O(V)$。因此整体时间复杂度为 $O(V^2)$。空间复杂度$O(V)$。主要空间消耗在距离数组 $dist$ 和访问集合 $visited$各占 $O(V)$。总空间复杂度为 $O(V)$。朴素实现的瓶颈在于「每次都要线性扫描全部未访问节点来寻找距离最小者」。当图中节点规模较大例如 LeetCode 中 $n \le 100$ 的稠密图场景时$O(V^2)$ 尚可接受一旦节点数上升到 $10^4 \sim 10^5$ 量级就需要引入堆优化。3. 堆优化 Dijkstra 算法3.1 堆优化 Dijkstra 算法思想堆优化 Dijkstra 算法利用优先队列小根堆高效选取当前距离最小的节点将原本 $O(V^2)$ 的查找过程优化为 $O(\log V)$显著提升算法效率。传统 Dijkstra 算法每次都要遍历所有未访问节点以找到距离最小者时间复杂度为 $O(V)$。堆优化后借助优先队列动态维护所有待处理节点的最短距离每次取出最小值仅需 $O(\log V)$。堆优化 Dijkstra 算法的核心思想如下用优先队列实时维护所有待处理节点的最短距离每次弹出距离最小的节点进行松弛操作如果发现更短路径则更新距离并将新距离入队依靠堆的性质始终保证每次处理的都是当前距离最小的节点。3.2 堆优化 Dijkstra 算法实现步骤初始化距离数组源点距离设为 $0$其余节点设为无穷大。创建优先队列将源节点及其距离 $(0, source)$ 入队。当优先队列非空时重复以下操作弹出队首距离最小节点如果该节点的距离已大于当前最短距离跳过否则遍历其所有邻居尝试松弛如果通过当前节点到邻居的距离更短则更新距离并将新距离入队。队列为空时结束返回所有节点的最短距离数组。3.3 堆优化 Dijkstra 算法实现代码import heapq class Solution: def dijkstra(self, graph, n, source): 堆优化 Dijkstra 算法计算单源最短路径 :param graph: 邻接表graph[u] {v: w, ...} :param n: 节点总数节点编号从 1 到 n :param source: 源点编号 :return: dist[i] 表示源点到 i 的最短距离 # 距离数组初始化为无穷大 dist [float(inf)] * (n 1) dist[source] 0 # 源点到自身距离为 0 # 小根堆存储 (距离, 节点) 元组 priority_queue [(0, source)] while priority_queue: current_distance, current_node heapq.heappop(priority_queue) # 如果弹出的节点距离不是最短的说明已被更新跳过 if current_distance dist[current_node]: continue # 遍历当前节点的所有邻居 for neighbor, weight in graph.get(current_node, {}).items(): new_distance current_distance weight # 如果找到更短路径则更新并入堆 if new_distance dist[neighbor]: dist[neighbor] new_distance heapq.heappush(priority_queue, (new_distance, neighbor)) return dist # 使用示例 # 构建一个有向图邻接表表示 graph { 1: {2: 2, 3: 4}, 2: {3: 1, 4: 7}, 3: {4: 3}, 4: {} } n 4 # 节点数量 source 1 # 源点编号 dist Solution().dijkstra(graph, n, source) print(从节点, source, 到其他节点的最短距离) for i in range(1, n 1): if dist[i] float(inf): print(f到节点 {i} 的距离不可达) else: print(f到节点 {i} 的距离{dist[i]})3.4 堆优化 Dijkstra 算法复杂度分析时间复杂度$O((V E) \log V)$。堆优化 Dijkstra 算法中每个节点最多会被弹出优先队列一次每次弹出操作的复杂度为 $O(\log V)$。每条边在松弛操作时最多会导致一次入堆入堆操作的复杂度同样为 $O(\log V)$。因此总体时间复杂度为 $O((V E) \log V)$其中 $V$ 为节点数$E$ 为边数。空间复杂度$O(V)$。主要空间消耗在距离数组和优先队列二者最坏情况下均为 $O(V)$ 级别。两种实现的差异对比如下维度朴素 Dijkstra堆优化 Dijkstra选最小距离节点线性扫描$O(V)$小根堆弹出$O(\log V)$时间复杂度$O(V^2)$$O((V E) \log V)$空间复杂度$O(V)$$O(V)$适用规模稠密图、$n$ 较小稀疏图、$n$ 较大4. 结合仓库源码图结构与 Bellman-Ford 佐证4.1 邻接表结构算法代码依赖的底层表示上述两段 Dijkstra 代码的入参graph均为「邻接表」形式graph[u] {v: w, ...}即一个节点u到其所有邻居节点v及其边权w的映射。仓库中 Graph-Adjacency-List.py 给出了邻接表的经典实现EdgeNode类记录边的终点vj与权值valVertexNode类持有该顶点的邻接边链表头head通过add_edge(vi, vj, val)向邻接表插入边通过get_edge(vi, vj)查询两点间边的权值。理解了这种「点 — 边链表」的映射关系就能明白 Dijkstra 松弛时遍历graph[current_node]的每一步都是在沿着出边扩散。4.2 Bellman-Ford 源码负权边场景的仓库级实现Dijkstra 无法处理负权边此时应改用 Bellman-Ford。仓库源码 Graph-Bellman-Ford.py 给出了完整实现先执行size - 1轮「对所有边进行松弛」再额外遍历一遍所有边检测负权环若仍能松弛则返回None。其测试用例刻意构造了含负权边的图graph { a: {b: -1, c: 4}, b: {c: 2, d: 3, e: 2}, c: {}, d: {b: 3, c: 5}, e: {d: -3} }其中a - b的边权为 $-1$、e - d的边权为 $-3$这正是 Dijkstra 会失效、而 Bellman-Ford 能正确求出最短距离的典型输入。从源码结构看该实现与上一节 Dijkstra 共享同样的「邻接表 距离数组」骨架区别仅在于松弛策略Dijkstra 按贪心顺序每节点确定一次Bellman-Ford 则循环遍历全部边 $V - 1$ 轮。SPFA 作为 Bellman-Ford 的队列优化版本只入队距离被更新过的节点其完整推导与代码见 单源最短路径二。5. 实战演练三道 LeetCode 经典题目本章节在原文「练习题目」基础上结合仓库对应题解展开帮助你把这些算法直接迁移到真实题目中。5.1 0743. 网络延迟时间题目要点$n$ 个节点、$n \le 100$、边权 $0 \le w_i \le 100$从节点 $k$ 发出信号求所有节点都收到信号所需时间若有节点不可达返回 $-1$。解法选择由于边权非负朴素 Dijkstra$O(V^2 E)$、堆优化 Dijkstra$O(E \log V)$均可直接使用仓库题解还给出了 Bellman-Ford 与 SPFA 共四种解法并在实现中演示了「用哈希表构建邻接表」「以max(dist[1:])求最大延迟、以float(inf)判不可达」等关键细节。堆优化版本的松弛代码与本文第 3 节完全同构可对照学习。5.2 0787. K 站中转内最便宜的航班题目要点限制「最多 $k$ 次中转」求 $src$ 到 $dst$ 的最便宜票价。这是 Dijkstra 的贪心策略失效的场景——最便宜路径可能绕远路但受到中转次数限制。解法选择仓库题解采用「动态规划 / Bellman-Ford」思路定义 $dp[k][i]$ 为最多 $k$ 次中转到达城市 $i$ 的最小花费状态转移 $dp[k][i] \min(dp[k][i], dp[k-1][j] price_{j \to i})$初始化 $dp[0][src] 0$外层循环 $k 1$ 次$k$ 次中转对应 $k 1$ 段航班并使用new_dp dp[:]临时数组避免同轮状态覆盖。该解法时间复杂度 $O(k \times m)$空间复杂度 $O(n)$。5.3 1631. 最小体力消耗路径题目要点在网格中找一条从左上角到右下角的路径使「路径上相邻格子的最大高度差绝对值」最小。解法选择仓库题解将其抽象为「带权无向图 并查集」把网格每个格子编号为点相邻格子的高度差绝对值作为边权将所有边按权值从小到大排序后依次加入并查集每次加入后检查起点 $(0,0)$ 与终点是否连通首次连通时的那条边权即为答案。这道题展示了最短路径思想的另一面——在「瓶颈最小化」型问题中边权排序 连通性判断往往比直接跑 Dijkstra 更直观。5.4 更多训练完整的「单源最短路径」分类题单见 单源最短路径题目列表可结合 题目列表与题解索引 持续刷题巩固。6. 小结本文围绕「单源最短路径」展开给出了三个核心结论选对算法边权非负优先 Dijkstra稠密图用朴素 $O(V^2)$稀疏图用堆优化 $O((VE)\log V)$存在负权边必须改用 Bellman-Ford 或 SPFA。吃透模板朴素与堆优化 Dijkstra 的代码模板可直接复用于绝大多数非负权最短路径题堆优化版的核心是「小根堆 距离过期判断current_distance dist[current_node]跳过」。迁移应用带中转次数限制、瓶颈最小化等变体问题需要跳出 Dijkstra 模板灵活结合动态规划或并查集仓库题解提供了完整可运行的参考实现。如需继续深入负权边处理与 SPFA 的队列优化细节请接着阅读 单源最短路径二。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐图解单源最短路径算法Dijkstra与堆优化详解图解单源最短路径算法Dijkstra与堆优化详解 一、单源最短路径问题概述 单源最短路径Single Source Shortest Path是图论中的经教程文档知识库最短路径算法终极指南从Dijkstra到实战应用最短路径算法终极指南从Dijkstra到实战应用 GitHub 加速计划 / alg / algo 项目提供了数据结构和算法必知必会的50个代码实现其中包含示例工程上一篇视频播放错误提示Kazumi 用户友好信息设计与解决方案下一篇Bilibili-EvolvedAPI请求优先级确保关键数据优先加载创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考