《图算法与计算机网络》系列 · 第 2 篇本文将深入讲解两个基于贪心策略的最短路径算法Dijkstra 和 A*。从基础的路由协议到游戏寻路理解算法如何从盲目搜索进化到智能搜索。系列文章导航篇目标题第 1 篇计算机网络与图算法从理论到实践第 2 篇从 Dijkstra 到 A*贪心策略与启发式搜索第 3 篇Bellman-Ford、SPFA 与 Floyd-Warshall动态规划的力量第 4 篇构建最优网络Prim 与 Kruskal 算法第 5 篇探索网络结构BFS、DFS 与拓扑排序第 6 篇流量优化之道Ford-Fulkerson 最大流算法文章目录系列文章导航引言从盲目到智能的路径搜索1. 最短路径问题概述1.1 问题定义1.2 网络中的实际应用1.3 算法分类2. Dijkstra 算法详解2.1 核心思想贪心策略2.2 算法原理图解2.3 数据结构设计2.4 完整代码实现2.5 时间复杂度分析基础版本无堆优化堆优化版本基于 Python heapq 实现2.6 网络应用OSPF 协议OSPF 简介OSPF 工作原理OSPF 示例为什么 OSPF 选择 Dijkstra3. A\* 算法详解3.1 核心思想启发式搜索3.2 启发式函数设计常见启发式函数启发式函数的性质3.3 数据结构设计3.4 完整代码实现4. 算法对比与选择4.1 相同点4.2 不同点4.3 选择决策树5. 本章总结核心要点Dijkstra 算法A\* 算法算法选择引言从盲目到智能的路径搜索想象你在一个迷宫中寻找出口方法 1盲目搜索从起点开始向所有方向均匀探索每到一个新位置继续向四周扩散最终能找到出口但可能走了很多弯路方法 2智能搜索从起点开始优先朝出口方向探索利用对出口位置的直觉启发式信息更快找到出口少走很多弯路这就是Dijkstra和A*的区别1. 最短路径问题概述1.1 问题定义给定一个图 G (V, E) 和起点 s找到从 s 到其他所有节点的最短路径。起点 s / | \ / | \ ● ● ● 哪条路径最短 \ | / \| / 终点 t1.2 网络中的实际应用场景节点边权重目标路由选择路由器链路延迟/跳数最小延迟导航系统路口道路距离/时间最快到达游戏寻路位置可行路径移动成本最短路径网络优化服务器连接带宽成本最小成本1.3 算法分类根据算法思想最短路径算法可分为贪心策略Dijkstra、A*动态规划Bellman-Ford、Floyd-Warshall队列优化SPFA本篇聚焦贪心策略的两个代表算法2. Dijkstra 算法详解2.1 核心思想贪心策略贪心思想每一步都选择当前最优的解。初始状态 distance[s] 0 (起点到自身距离为 0) distance[其他] ∞ (未知距离设为无穷大) 重复以下步骤直到所有节点都被访问 1. 选择 distance 最小的未访问节点 u 2. 标记 u 为已访问 3. 更新 u 的所有邻居 v 的 distance 如果 distance[u] weight(u,v) distance[v] 则 distance[v] distance[u] weight(u,v)2.2 算法原理图解让我们通过一个实例来理解网络拓扑路由器延迟 0 / \ 4/ \1 / 2 \ 1 — — 2 \ / 1\ / 5 \ / 3执行过程初始 distance [0, ∞, ∞, ∞] visited {} 优先队列 [(0, 0)] # (距离节点) 第 1 轮 - 弹出节点 0 (距离最小) - 更新邻居 * 节点 1: distance[1] min(∞, 04) 4 * 节点 2: distance[2] min(∞, 01) 1 - visited {0} - distance [0, 4, 1, ∞] - 优先队列 [(1, 2), (4, 1)] 第 2 轮 - 弹出节点 2 (距离 1最小) - 更新邻居 * 节点 1: distance[1] min(4, 12) 3 ✓ 更新 * 节点 3: distance[3] min(∞, 15) 6 - visited {0, 2} - distance [0, 3, 1, 6] - 优先队列 [(3, 1), (4, 1), (6, 3)] 第 3 轮 - 弹出节点 1 (距离 3最小) - 更新邻居 * 节点 3: distance[3] min(6, 31) 4 ✓ 更新 - visited {0, 2, 1} - distance [0, 3, 1, 4] - 优先队列 [(4, 1), (4, 3), (6, 3)] 第 4 轮 - 弹出节点 3 (距离 4最小) - 无邻居需要更新 - visited {0, 2, 1, 3} - distance [0, 3, 1, 4] 完成最终结果 distance [0, 3, 1, 4] 路径 0→1: 0→2→1 (延迟 3ms) 0→2: 0→2 (延迟 1ms) 0→3: 0→2→1→3 (延迟 4ms)2.3 数据结构设计Dijkstra 算法需要以下数据结构# 1. 图的表示邻接表graph{0:[(1,4),(2,1)],# 节点 0 的邻居(邻居节点权重)1:[(3,1)],2:[(1,2),(3,5)],3:[]}# 2. distance 字典记录起点到各点的最短距离distance{0:0,1:4,2:1,3:6}# 3. visited 集合标记已访问的节点visited{0,2,1,3}# 4. priority_queue优先队列最小堆# 存储 (distance, node) 元组importheapq pq[(0,0),(1,2),(4,1),(6,3)]# 5. predecessor 字典记录路径前驱用于重构路径predecessor{0:None,1:2,2:0,3:1}# 路径重构3 ← 1 ← 2 ← 02.4 完整代码实现 Dijkstra 算法 时间复杂度O((V E) log V) - 使用最小堆优化 空间复杂度O(V) importheapqfromtypingimportDict,List,Tuple,Optionaldefdijkstra(graph:Dict[int,List[Tuple[int,float]]],start:int)-Tuple[Dict[int,float],Dict[int,Optional[int]]]: Dijkstra 最短路径算法 Args: graph: 邻接表 {node: [(neighbor, weight), ...]} start: 起点 Returns: (distance, predecessor) - distance: 起点到各点的最短距离 - predecessor: 各点的前驱节点用于重构路径 # 1. 初始化distance{node:float(inf)fornodeingraph}distance[start]0predecessor{node:Nonefornodeingraph}# 2. 优先队列最小堆# 存储 (distance, node) 元组pq[(0,start)]# 3. 已访问集合visitedset()# 4. 主循环whilepq:# 4.1 弹出距离最小的节点curr_dist,curr_nodeheapq.heappop(pq)# 4.2 如果已访问跳过避免重复处理ifcurr_nodeinvisited:continue# 4.3 标记为已访问visited.add(curr_node)# 4.4 更新邻居节点forneighbor,weightingraph.get(curr_node,[]):ifneighborinvisited:continue# 4.5 松弛操作new_distcurr_distweightifnew_distdistance[neighbor]:distance[neighbor]new_dist predecessor[neighbor]curr_node heapq.heappush(pq,(new_dist,neighbor))returndistance,predecessordefreconstruct_path(predecessor:Dict[int,Optional[int]],start:int,end:int)-List[int]: 重构从 start 到 end 的路径 Args: predecessor: 前驱节点字典 start: 起点 end: 终点 Returns: 路径节点列表 path[]currentendwhilecurrentisnotNone:path.append(current)currentpredecessor[current]path.reverse()# 反转路径# 检查路径是否有效ifpathandpath[0]start:returnpathelse:return[]# 无法到达# 使用示例if__name____main__:# 定义图网络拓扑graph{0:[(1,4),(2,1)],1:[(3,1)],2:[(1,2),(3,5)],3:[]}# 运行 Dijkstradistance,predecessordijkstra(graph,start0)# 输出结果print(从节点 0 出发的最短距离)fornodeinsorted(distance.keys()):print(f 到节点{node}:{distance[node]})# 重构路径print(\n路径重构)fortargetin[1,2,3]:pathreconstruct_path(predecessor,0,target)ifpath:path_str → .join(map(str,path))print(f 0→{target}:{path_str})else:print(f 0→{target}: 不可达)运行结果从节点 0 出发的最短距离 到节点 0: 0 到节点 1: 3 到节点 2: 1 到节点 3: 4 路径重构 0→1: 0 → 2 → 1 0→2: 0 → 2 0→3: 0 → 2 → 1 → 32.5 时间复杂度分析基础版本无堆优化# 每次选择最小 distance 需要 O(V)# 总共 V 轮# 时间复杂度O(V²)堆优化版本基于 Python heapq 实现重要说明本文代码使用 Python 标准库heapq它不支持高效的decrease_key操作。因此采用惰性删除Lazy Deletion策略# 代码实现ifnew_distdistance[neighbor]:distance[neighbor]new_dist heapq.heappush(pq,(new_dist,neighbor))# 直接 push 新元组旧元组留在堆中时间复杂度分析# 入队次数分析 # - 理论模型支持 decrease_key每个节点入队一次共 O(V) 次 # - 本文实现heapq惰性删除每个节点可能多次入队 # # 最坏情况下每条边都可能触发一次 heappush堆中元素可达 O(E) # 每次堆操作O(log E) # 总时间复杂度O(E log E) # 由于 log E ≤ 2 log V因为 E ≤ V² # 渐近意义上O(E log V) # 加上初始化O((V E) log V)空间复杂度分析# 理论最优O(V) - 如果支持 decrease_key # 本文实现O(V E) - 堆中可能残留旧的历史记录 # 具体分析 # - distance 字典O(V) # - predecessor 字典O(V) # - visited 集合O(V) # - 优先队列最坏情况O(E) ← 注意由于惰性删除堆中可能累积大量旧记录 # 总空间复杂度O(V E)对比不同实现实现方式时间复杂度空间复杂度入队次数本文实现heapq惰性删除O(E log V)O(V E)最多 E 次理论实现支持 decrease_keyO((VE) log V)O(V)最多 V 次斐波那契堆O(E V log V)O(V)V 次工程建议Python 标准库heapq虽然理论复杂度稍差但实际性能良好对于稀疏图E V²E ≈ V两者差异不大如需严格 O(V) 空间需自定义支持decrease_key的堆结构2.6 网络应用OSPF 协议OSPF 简介OSPFOpen Shortest Path First开放式最短路径优先协议类型链路状态路由协议算法Dijkstra 算法标准RFC 2328应用企业网、数据中心、ISPOSPF 工作原理1. 发现邻居 路由器发送 Hello 包发现直连的邻居路由器 2. 交换链路状态信息 路由器之间交换 LSA链路状态通告 3. 构建链路状态数据库LSDB 每个路由器都有完整的网络拓扑图 4. 运行 Dijkstra 算法 以自己为根计算到所有网络的最短路径 5. 生成路由表 根据计算结果填充路由表OSPF 示例网络拓扑 R0 (本路由器) / \ 2/ \5 / \ R1 R2 \ / \ 3\ /1 \4 \ / \ R3 R4 OSPF 计算过程 1. R0 收集所有 LSA构建完整拓扑 2. R0 运行 Dijkstra 算法 3. 计算结果 - R0→R1: 2 (直接) - R0→R2: 5 (直接) - R0→R3: 5 (R0→R1→R3) - R0→R4: 9 (R0→R2→R4) 4. 生成路由表 目标网络 下一跳 成本 R1 网络 R1 2 R2 网络 R2 5 R3 网络 R1 5 R4 网络 R2 9为什么 OSPF 选择 Dijkstra收敛快网络变化后快速重新计算无环路Dijkstra 保证无环路支持多路径可以计算等价多路径可扩展支持分层设计区域划分3. A* 算法详解3.1 核心思想启发式搜索评估函数f(n) g(n) h(n) 其中 - g(n)从起点到节点 n 的实际代价已知 - h(n)从节点 n 到目标的估计代价启发式 - f(n)经过节点 n 的总代价估计选择策略每次选择 f(n) 最小的节点扩展平衡已走路径和预估剩余路径3.2 启发式函数设计启发式函数 h(n) 是 A* 的灵魂常见启发式函数defeuclidean_distance(a,b): 欧几里得距离直线距离 适用可以自由移动的场景如无人机 return((a[0]-b[0])**2**(a[1]-b[1])2)**0.5defmanhattan_distance(a,b): 曼哈顿距离城市街区距离 适用只能上下左右移动如网格地图 returnabs(a[0]-b[0])abs(a[1]-b[1])defchebyshev_distance(a,b): 切比雪夫距离八方向移动 适用可以八个方向移动如国际象棋中的国王 returnmax(abs(a[0]-b[0]),abs(a[1]-b[1]))defdiagonal_distance(a,b): 对角线距离允许对角移动 适用网格地图允许对角移动 dxabs(a[0]-b[0])dyabs(a[1]-b[1])returnmax(dx,dy)(min(dx,dy)*(1.414-1))启发式函数的性质可采纳性Admissibilityh(n) ≤ 实际代价保证找到最优解例如欧几里得距离 ≤ 实际路径距离一致性Consistencyh(n) ≤ cost(n, neighbor) h(neighbor)保证 f(n) 单调不减更强的条件启发式函数对性能的影响h(n) 0 A* 退化为 Dijkstra 保证最优但慢 h(n) 很小但0 接近 Dijkstra 保证最优较慢 h(n) 接近实际值 理想情况 保证最优快 h(n) 很大超过实际值 接近贪心最佳优先搜索 快但不保证最优3.3 数据结构设计# 1. 图的表示邻接表graph{(0,0):[((0,1),1),((1,0),1)],# 网格坐标}# 2. g_score 字典起点到各点的实际代价g_score{node:float(inf)fornodeingraph}g_score[start]0# 3. f_score 字典估计总代价f_score{node:float(inf)fornodeingraph}f_score[start]heuristic(start,goal)# 4. open_set待扩展节点集合优先队列open_set[(f_score[start],start)]# 5. closed_set已处理节点集合closed_setset()# 6. came_from 字典路径重构came_from{start:None}3.4 完整代码实现 A* 寻路算法 时间复杂度分析 - 最坏情况h(n)0退化为 DijkstraO(E log V) - 平均情况有限图 一致性启发式O(E log V) - 注意 * 以上分析基于显式图如路由拓扑、固定网格的最坏情况 * 在状态空间无限或路径长度无界的情况下时间复杂度可能是指数级的 O(b^d) b 为分支因子d 为解的深度 * 本文讨论的计算机网络和网格寻路属于有限图场景因此 O(E log V) 成立 空间复杂度分析 - 本文实现heapq惰性删除O(V E) - 理论最优支持 decrease_keyO(V) - 实际工程中A* 的内存压力通常高于 Dijkstra 原因 * 需要同时存储 open_set 和 closed_set * 在大规模地图中O(V) 的空间占用可能导致内存溢出 * Dijkstra 在某些优化下可以更早释放节点而 A* 需要保留更多节点信息 importheapqfromtypingimportDict,List,Tuple,Optional,Callabledefastar(graph:Dict[int,List[Tuple[int,float]]],start:int,goal:int,heuristic:Callable[[int,int],float])-Tuple[float,List[int]]: A* 最短路径算法 Args: graph: 邻接表 {node: [(neighbor, weight), ...]} start: 起点 goal: 目标 heuristic: 启发式函数 h(n) Returns: (cost, path) - cost: 最短路径的总代价 - path: 路径节点列表 # 1. 初始化g_score{node:float(inf)fornodeingraph}g_score[start]0f_score{node:float(inf)fornodeingraph}f_score[start]heuristic(start,goal)# 2. open_set优先队列open_set[(f_score[start],start)]# 3. closed_setclosed_setset()# 4. came_from 字典came_from{start:None}# 5. 主循环whileopen_set:# 5.1 弹出 f_score 最小的节点_,currentheapq.heappop(open_set)# 5.2 到达目标ifcurrentgoal:# 重构路径path[]nodegoalwhilenodeisnotNone:path.append(node)nodecame_from[node]path.reverse()returng_score[goal],path# 5.3 已处理过跳过ifcurrentinclosed_set:continue# 5.4 标记为已处理closed_set.add(current)# 5.5 扩展邻居forneighbor,weightingraph.get(current,[]):ifneighborinclosed_set:continue# 5.6 计算新的 g_scoretentative_gg_score[current]weightiftentative_gg_score[neighbor]:# 找到更好的路径came_from[neighbor]current g_score[neighbor]tentative_g f_score[neighbor]tentative_gheuristic(neighbor,goal)heapq.heappush(open_set,(f_score[neighbor],neighbor))# 无法到达目标returnfloat(inf),[]# 使用示例if__name____main__:# 定义图graph{0:[(1,4),(2,1)],1:[(3,1)],2:[(1,2),(3,5)],3:[]}# 定义启发式函数这里用简单的估计defheuristic(a,b):# 实际应用中应该用更精确的启发式returnabs(a-b)*2# 简单估计# 运行 A*cost,pathastar(graph,start0,goal3,heuristicheuristic)# 输出结果print(f最短路径代价{cost})print(f路径{ → .join(map(str,path))})4. 算法对比与选择4.1 相同点特性DijkstraA*算法思想贪心策略贪心策略 启发式数据结构优先队列优先队列最优性保证最优保证最优可采纳启发式时间复杂度O((VE)logV)O((VE)logV)有限图 一致性启发式空间复杂度O(V E)本文 heapq 实现O(V E)本文 heapq 实现内存压力更高负权边不支持不支持4.2 不同点特性DijkstraA*搜索方向无向扩散有向搜索扩展节点数多少好启发式搜索范围全向定向实际运行时间较慢较快需要启发式❌✅适用场景单源到所有点单源到单目标4.3 选择决策树需要计算最短路径 │ ├─ 存在负权边 │ ├─ 是 → 使用 Bellman-Ford/SPFA见第 3 篇 │ └─ 否 → 继续判断 │ ├─ 需要到所有点的最短路径 │ ├─ 是 → 使用 Dijkstra │ └─ 否 → 继续判断 │ ├─ 只需要到特定目标的路径 │ ├─ 是 → 继续判断 │ └─ 否 → 使用 Dijkstra │ ├─ 有合适的启发式函数 │ ├─ 是 → 使用 A* │ └─ 否 → 使用 Dijkstra │ └─ 对性能要求高 ├─ 是 → 努力实现好的启发式使用 A* └─ 否 → 使用 Dijkstra更简单5. 本章总结核心要点Dijkstra 算法思想贪心策略每次选择最近的未访问节点数据结构优先队列最小堆、distance 数组、visited 集合时间复杂度O((VE)logV)应用OSPF 路由协议、网络延迟优化局限无方向性搜索扩展节点多A* 算法思想Dijkstra 启发式f(n) g(n) h(n)关键启发式函数的设计可采纳性、一致性时间复杂度O((VE)logV)实际更快应用游戏寻路、GPS 导航、机器人路径规划优势有方向搜索减少无效扩展算法选择到所有点的最短路径→ Dijkstra到特定目标的路径→ A*有好启发式无启发式信息→ Dijkstra存在负权边→ Bellman-Ford/SPFA见下篇
从 Dijkstra 到 A*：贪心策略与启发式搜索
《图算法与计算机网络》系列 · 第 2 篇本文将深入讲解两个基于贪心策略的最短路径算法Dijkstra 和 A*。从基础的路由协议到游戏寻路理解算法如何从盲目搜索进化到智能搜索。系列文章导航篇目标题第 1 篇计算机网络与图算法从理论到实践第 2 篇从 Dijkstra 到 A*贪心策略与启发式搜索第 3 篇Bellman-Ford、SPFA 与 Floyd-Warshall动态规划的力量第 4 篇构建最优网络Prim 与 Kruskal 算法第 5 篇探索网络结构BFS、DFS 与拓扑排序第 6 篇流量优化之道Ford-Fulkerson 最大流算法文章目录系列文章导航引言从盲目到智能的路径搜索1. 最短路径问题概述1.1 问题定义1.2 网络中的实际应用1.3 算法分类2. Dijkstra 算法详解2.1 核心思想贪心策略2.2 算法原理图解2.3 数据结构设计2.4 完整代码实现2.5 时间复杂度分析基础版本无堆优化堆优化版本基于 Python heapq 实现2.6 网络应用OSPF 协议OSPF 简介OSPF 工作原理OSPF 示例为什么 OSPF 选择 Dijkstra3. A\* 算法详解3.1 核心思想启发式搜索3.2 启发式函数设计常见启发式函数启发式函数的性质3.3 数据结构设计3.4 完整代码实现4. 算法对比与选择4.1 相同点4.2 不同点4.3 选择决策树5. 本章总结核心要点Dijkstra 算法A\* 算法算法选择引言从盲目到智能的路径搜索想象你在一个迷宫中寻找出口方法 1盲目搜索从起点开始向所有方向均匀探索每到一个新位置继续向四周扩散最终能找到出口但可能走了很多弯路方法 2智能搜索从起点开始优先朝出口方向探索利用对出口位置的直觉启发式信息更快找到出口少走很多弯路这就是Dijkstra和A*的区别1. 最短路径问题概述1.1 问题定义给定一个图 G (V, E) 和起点 s找到从 s 到其他所有节点的最短路径。起点 s / | \ / | \ ● ● ● 哪条路径最短 \ | / \| / 终点 t1.2 网络中的实际应用场景节点边权重目标路由选择路由器链路延迟/跳数最小延迟导航系统路口道路距离/时间最快到达游戏寻路位置可行路径移动成本最短路径网络优化服务器连接带宽成本最小成本1.3 算法分类根据算法思想最短路径算法可分为贪心策略Dijkstra、A*动态规划Bellman-Ford、Floyd-Warshall队列优化SPFA本篇聚焦贪心策略的两个代表算法2. Dijkstra 算法详解2.1 核心思想贪心策略贪心思想每一步都选择当前最优的解。初始状态 distance[s] 0 (起点到自身距离为 0) distance[其他] ∞ (未知距离设为无穷大) 重复以下步骤直到所有节点都被访问 1. 选择 distance 最小的未访问节点 u 2. 标记 u 为已访问 3. 更新 u 的所有邻居 v 的 distance 如果 distance[u] weight(u,v) distance[v] 则 distance[v] distance[u] weight(u,v)2.2 算法原理图解让我们通过一个实例来理解网络拓扑路由器延迟 0 / \ 4/ \1 / 2 \ 1 — — 2 \ / 1\ / 5 \ / 3执行过程初始 distance [0, ∞, ∞, ∞] visited {} 优先队列 [(0, 0)] # (距离节点) 第 1 轮 - 弹出节点 0 (距离最小) - 更新邻居 * 节点 1: distance[1] min(∞, 04) 4 * 节点 2: distance[2] min(∞, 01) 1 - visited {0} - distance [0, 4, 1, ∞] - 优先队列 [(1, 2), (4, 1)] 第 2 轮 - 弹出节点 2 (距离 1最小) - 更新邻居 * 节点 1: distance[1] min(4, 12) 3 ✓ 更新 * 节点 3: distance[3] min(∞, 15) 6 - visited {0, 2} - distance [0, 3, 1, 6] - 优先队列 [(3, 1), (4, 1), (6, 3)] 第 3 轮 - 弹出节点 1 (距离 3最小) - 更新邻居 * 节点 3: distance[3] min(6, 31) 4 ✓ 更新 - visited {0, 2, 1} - distance [0, 3, 1, 4] - 优先队列 [(4, 1), (4, 3), (6, 3)] 第 4 轮 - 弹出节点 3 (距离 4最小) - 无邻居需要更新 - visited {0, 2, 1, 3} - distance [0, 3, 1, 4] 完成最终结果 distance [0, 3, 1, 4] 路径 0→1: 0→2→1 (延迟 3ms) 0→2: 0→2 (延迟 1ms) 0→3: 0→2→1→3 (延迟 4ms)2.3 数据结构设计Dijkstra 算法需要以下数据结构# 1. 图的表示邻接表graph{0:[(1,4),(2,1)],# 节点 0 的邻居(邻居节点权重)1:[(3,1)],2:[(1,2),(3,5)],3:[]}# 2. distance 字典记录起点到各点的最短距离distance{0:0,1:4,2:1,3:6}# 3. visited 集合标记已访问的节点visited{0,2,1,3}# 4. priority_queue优先队列最小堆# 存储 (distance, node) 元组importheapq pq[(0,0),(1,2),(4,1),(6,3)]# 5. predecessor 字典记录路径前驱用于重构路径predecessor{0:None,1:2,2:0,3:1}# 路径重构3 ← 1 ← 2 ← 02.4 完整代码实现 Dijkstra 算法 时间复杂度O((V E) log V) - 使用最小堆优化 空间复杂度O(V) importheapqfromtypingimportDict,List,Tuple,Optionaldefdijkstra(graph:Dict[int,List[Tuple[int,float]]],start:int)-Tuple[Dict[int,float],Dict[int,Optional[int]]]: Dijkstra 最短路径算法 Args: graph: 邻接表 {node: [(neighbor, weight), ...]} start: 起点 Returns: (distance, predecessor) - distance: 起点到各点的最短距离 - predecessor: 各点的前驱节点用于重构路径 # 1. 初始化distance{node:float(inf)fornodeingraph}distance[start]0predecessor{node:Nonefornodeingraph}# 2. 优先队列最小堆# 存储 (distance, node) 元组pq[(0,start)]# 3. 已访问集合visitedset()# 4. 主循环whilepq:# 4.1 弹出距离最小的节点curr_dist,curr_nodeheapq.heappop(pq)# 4.2 如果已访问跳过避免重复处理ifcurr_nodeinvisited:continue# 4.3 标记为已访问visited.add(curr_node)# 4.4 更新邻居节点forneighbor,weightingraph.get(curr_node,[]):ifneighborinvisited:continue# 4.5 松弛操作new_distcurr_distweightifnew_distdistance[neighbor]:distance[neighbor]new_dist predecessor[neighbor]curr_node heapq.heappush(pq,(new_dist,neighbor))returndistance,predecessordefreconstruct_path(predecessor:Dict[int,Optional[int]],start:int,end:int)-List[int]: 重构从 start 到 end 的路径 Args: predecessor: 前驱节点字典 start: 起点 end: 终点 Returns: 路径节点列表 path[]currentendwhilecurrentisnotNone:path.append(current)currentpredecessor[current]path.reverse()# 反转路径# 检查路径是否有效ifpathandpath[0]start:returnpathelse:return[]# 无法到达# 使用示例if__name____main__:# 定义图网络拓扑graph{0:[(1,4),(2,1)],1:[(3,1)],2:[(1,2),(3,5)],3:[]}# 运行 Dijkstradistance,predecessordijkstra(graph,start0)# 输出结果print(从节点 0 出发的最短距离)fornodeinsorted(distance.keys()):print(f 到节点{node}:{distance[node]})# 重构路径print(\n路径重构)fortargetin[1,2,3]:pathreconstruct_path(predecessor,0,target)ifpath:path_str → .join(map(str,path))print(f 0→{target}:{path_str})else:print(f 0→{target}: 不可达)运行结果从节点 0 出发的最短距离 到节点 0: 0 到节点 1: 3 到节点 2: 1 到节点 3: 4 路径重构 0→1: 0 → 2 → 1 0→2: 0 → 2 0→3: 0 → 2 → 1 → 32.5 时间复杂度分析基础版本无堆优化# 每次选择最小 distance 需要 O(V)# 总共 V 轮# 时间复杂度O(V²)堆优化版本基于 Python heapq 实现重要说明本文代码使用 Python 标准库heapq它不支持高效的decrease_key操作。因此采用惰性删除Lazy Deletion策略# 代码实现ifnew_distdistance[neighbor]:distance[neighbor]new_dist heapq.heappush(pq,(new_dist,neighbor))# 直接 push 新元组旧元组留在堆中时间复杂度分析# 入队次数分析 # - 理论模型支持 decrease_key每个节点入队一次共 O(V) 次 # - 本文实现heapq惰性删除每个节点可能多次入队 # # 最坏情况下每条边都可能触发一次 heappush堆中元素可达 O(E) # 每次堆操作O(log E) # 总时间复杂度O(E log E) # 由于 log E ≤ 2 log V因为 E ≤ V² # 渐近意义上O(E log V) # 加上初始化O((V E) log V)空间复杂度分析# 理论最优O(V) - 如果支持 decrease_key # 本文实现O(V E) - 堆中可能残留旧的历史记录 # 具体分析 # - distance 字典O(V) # - predecessor 字典O(V) # - visited 集合O(V) # - 优先队列最坏情况O(E) ← 注意由于惰性删除堆中可能累积大量旧记录 # 总空间复杂度O(V E)对比不同实现实现方式时间复杂度空间复杂度入队次数本文实现heapq惰性删除O(E log V)O(V E)最多 E 次理论实现支持 decrease_keyO((VE) log V)O(V)最多 V 次斐波那契堆O(E V log V)O(V)V 次工程建议Python 标准库heapq虽然理论复杂度稍差但实际性能良好对于稀疏图E V²E ≈ V两者差异不大如需严格 O(V) 空间需自定义支持decrease_key的堆结构2.6 网络应用OSPF 协议OSPF 简介OSPFOpen Shortest Path First开放式最短路径优先协议类型链路状态路由协议算法Dijkstra 算法标准RFC 2328应用企业网、数据中心、ISPOSPF 工作原理1. 发现邻居 路由器发送 Hello 包发现直连的邻居路由器 2. 交换链路状态信息 路由器之间交换 LSA链路状态通告 3. 构建链路状态数据库LSDB 每个路由器都有完整的网络拓扑图 4. 运行 Dijkstra 算法 以自己为根计算到所有网络的最短路径 5. 生成路由表 根据计算结果填充路由表OSPF 示例网络拓扑 R0 (本路由器) / \ 2/ \5 / \ R1 R2 \ / \ 3\ /1 \4 \ / \ R3 R4 OSPF 计算过程 1. R0 收集所有 LSA构建完整拓扑 2. R0 运行 Dijkstra 算法 3. 计算结果 - R0→R1: 2 (直接) - R0→R2: 5 (直接) - R0→R3: 5 (R0→R1→R3) - R0→R4: 9 (R0→R2→R4) 4. 生成路由表 目标网络 下一跳 成本 R1 网络 R1 2 R2 网络 R2 5 R3 网络 R1 5 R4 网络 R2 9为什么 OSPF 选择 Dijkstra收敛快网络变化后快速重新计算无环路Dijkstra 保证无环路支持多路径可以计算等价多路径可扩展支持分层设计区域划分3. A* 算法详解3.1 核心思想启发式搜索评估函数f(n) g(n) h(n) 其中 - g(n)从起点到节点 n 的实际代价已知 - h(n)从节点 n 到目标的估计代价启发式 - f(n)经过节点 n 的总代价估计选择策略每次选择 f(n) 最小的节点扩展平衡已走路径和预估剩余路径3.2 启发式函数设计启发式函数 h(n) 是 A* 的灵魂常见启发式函数defeuclidean_distance(a,b): 欧几里得距离直线距离 适用可以自由移动的场景如无人机 return((a[0]-b[0])**2**(a[1]-b[1])2)**0.5defmanhattan_distance(a,b): 曼哈顿距离城市街区距离 适用只能上下左右移动如网格地图 returnabs(a[0]-b[0])abs(a[1]-b[1])defchebyshev_distance(a,b): 切比雪夫距离八方向移动 适用可以八个方向移动如国际象棋中的国王 returnmax(abs(a[0]-b[0]),abs(a[1]-b[1]))defdiagonal_distance(a,b): 对角线距离允许对角移动 适用网格地图允许对角移动 dxabs(a[0]-b[0])dyabs(a[1]-b[1])returnmax(dx,dy)(min(dx,dy)*(1.414-1))启发式函数的性质可采纳性Admissibilityh(n) ≤ 实际代价保证找到最优解例如欧几里得距离 ≤ 实际路径距离一致性Consistencyh(n) ≤ cost(n, neighbor) h(neighbor)保证 f(n) 单调不减更强的条件启发式函数对性能的影响h(n) 0 A* 退化为 Dijkstra 保证最优但慢 h(n) 很小但0 接近 Dijkstra 保证最优较慢 h(n) 接近实际值 理想情况 保证最优快 h(n) 很大超过实际值 接近贪心最佳优先搜索 快但不保证最优3.3 数据结构设计# 1. 图的表示邻接表graph{(0,0):[((0,1),1),((1,0),1)],# 网格坐标}# 2. g_score 字典起点到各点的实际代价g_score{node:float(inf)fornodeingraph}g_score[start]0# 3. f_score 字典估计总代价f_score{node:float(inf)fornodeingraph}f_score[start]heuristic(start,goal)# 4. open_set待扩展节点集合优先队列open_set[(f_score[start],start)]# 5. closed_set已处理节点集合closed_setset()# 6. came_from 字典路径重构came_from{start:None}3.4 完整代码实现 A* 寻路算法 时间复杂度分析 - 最坏情况h(n)0退化为 DijkstraO(E log V) - 平均情况有限图 一致性启发式O(E log V) - 注意 * 以上分析基于显式图如路由拓扑、固定网格的最坏情况 * 在状态空间无限或路径长度无界的情况下时间复杂度可能是指数级的 O(b^d) b 为分支因子d 为解的深度 * 本文讨论的计算机网络和网格寻路属于有限图场景因此 O(E log V) 成立 空间复杂度分析 - 本文实现heapq惰性删除O(V E) - 理论最优支持 decrease_keyO(V) - 实际工程中A* 的内存压力通常高于 Dijkstra 原因 * 需要同时存储 open_set 和 closed_set * 在大规模地图中O(V) 的空间占用可能导致内存溢出 * Dijkstra 在某些优化下可以更早释放节点而 A* 需要保留更多节点信息 importheapqfromtypingimportDict,List,Tuple,Optional,Callabledefastar(graph:Dict[int,List[Tuple[int,float]]],start:int,goal:int,heuristic:Callable[[int,int],float])-Tuple[float,List[int]]: A* 最短路径算法 Args: graph: 邻接表 {node: [(neighbor, weight), ...]} start: 起点 goal: 目标 heuristic: 启发式函数 h(n) Returns: (cost, path) - cost: 最短路径的总代价 - path: 路径节点列表 # 1. 初始化g_score{node:float(inf)fornodeingraph}g_score[start]0f_score{node:float(inf)fornodeingraph}f_score[start]heuristic(start,goal)# 2. open_set优先队列open_set[(f_score[start],start)]# 3. closed_setclosed_setset()# 4. came_from 字典came_from{start:None}# 5. 主循环whileopen_set:# 5.1 弹出 f_score 最小的节点_,currentheapq.heappop(open_set)# 5.2 到达目标ifcurrentgoal:# 重构路径path[]nodegoalwhilenodeisnotNone:path.append(node)nodecame_from[node]path.reverse()returng_score[goal],path# 5.3 已处理过跳过ifcurrentinclosed_set:continue# 5.4 标记为已处理closed_set.add(current)# 5.5 扩展邻居forneighbor,weightingraph.get(current,[]):ifneighborinclosed_set:continue# 5.6 计算新的 g_scoretentative_gg_score[current]weightiftentative_gg_score[neighbor]:# 找到更好的路径came_from[neighbor]current g_score[neighbor]tentative_g f_score[neighbor]tentative_gheuristic(neighbor,goal)heapq.heappush(open_set,(f_score[neighbor],neighbor))# 无法到达目标returnfloat(inf),[]# 使用示例if__name____main__:# 定义图graph{0:[(1,4),(2,1)],1:[(3,1)],2:[(1,2),(3,5)],3:[]}# 定义启发式函数这里用简单的估计defheuristic(a,b):# 实际应用中应该用更精确的启发式returnabs(a-b)*2# 简单估计# 运行 A*cost,pathastar(graph,start0,goal3,heuristicheuristic)# 输出结果print(f最短路径代价{cost})print(f路径{ → .join(map(str,path))})4. 算法对比与选择4.1 相同点特性DijkstraA*算法思想贪心策略贪心策略 启发式数据结构优先队列优先队列最优性保证最优保证最优可采纳启发式时间复杂度O((VE)logV)O((VE)logV)有限图 一致性启发式空间复杂度O(V E)本文 heapq 实现O(V E)本文 heapq 实现内存压力更高负权边不支持不支持4.2 不同点特性DijkstraA*搜索方向无向扩散有向搜索扩展节点数多少好启发式搜索范围全向定向实际运行时间较慢较快需要启发式❌✅适用场景单源到所有点单源到单目标4.3 选择决策树需要计算最短路径 │ ├─ 存在负权边 │ ├─ 是 → 使用 Bellman-Ford/SPFA见第 3 篇 │ └─ 否 → 继续判断 │ ├─ 需要到所有点的最短路径 │ ├─ 是 → 使用 Dijkstra │ └─ 否 → 继续判断 │ ├─ 只需要到特定目标的路径 │ ├─ 是 → 继续判断 │ └─ 否 → 使用 Dijkstra │ ├─ 有合适的启发式函数 │ ├─ 是 → 使用 A* │ └─ 否 → 使用 Dijkstra │ └─ 对性能要求高 ├─ 是 → 努力实现好的启发式使用 A* └─ 否 → 使用 Dijkstra更简单5. 本章总结核心要点Dijkstra 算法思想贪心策略每次选择最近的未访问节点数据结构优先队列最小堆、distance 数组、visited 集合时间复杂度O((VE)logV)应用OSPF 路由协议、网络延迟优化局限无方向性搜索扩展节点多A* 算法思想Dijkstra 启发式f(n) g(n) h(n)关键启发式函数的设计可采纳性、一致性时间复杂度O((VE)logV)实际更快应用游戏寻路、GPS 导航、机器人路径规划优势有方向搜索减少无效扩展算法选择到所有点的最短路径→ Dijkstra到特定目标的路径→ A*有好启发式无启发式信息→ Dijkstra存在负权边→ Bellman-Ford/SPFA见下篇
