看这两个算法的人多半是遇到了路径规划或者图搜索的问题。无论你是刚接触游戏开发里的自动寻路还是在搞机器人导航、地图路径计算Dijkstra 和 A* 几乎是绕不开的两个名字。网上讲原理的文章很多但大多是教科书式的堆公式看完还是一头雾水不知道实际写代码时怎么选、怎么调。这篇小结我就用实际项目里跑过的经验把这两个算法的核心思路、差异、代码实现和调优技巧一次说清楚。先说个结论Dijkstra 是 A的特例A是 Dijkstra 的“开挂版”**。两者本质都是遍历图节点找最短路径区别在于 A* 多了个“方向感”知道往终点方向优先探索所以大多数场景下更快。但“快”不等于“永远更好”——有些场景下 Dijkstra 反而更稳。具体怎么选咱们往下看。1. 核心思路拆解它们到底在算什么1.1 图搜索的基本框架在聊具体算法前先建立一个共识这两个算法解决的都是“在带权重的图中从起点到终点找一条总代价最小的路径”这个问题。这里的“图”可以是一张地图、一个迷宫、一组城市道路网络甚至抽象的依赖关系。图由节点Node和边Edge组成边上有权重Weight权重可以表示距离、时间、消耗等。两个算法的核心都在做一件事维护一个“已确认最短路径的节点集合”和“待探索节点的边界”不断从边界中选一个节点向外扩展直到覆盖终点。区别就在“怎么选”这个动作上。我见过很多初学者把 Dijkstra 当成“BFS 权重”这个理解方向是对的但不够精确。BFS 用队列先进先出Dijkstra 用优先队列最小堆按当前累计代价排序。这个数据结构上的差异直接决定了算法能否处理任意非负权重图。1.2 Dijkstra老老实实撒网Dijkstra 的思路非常朴素从起点出发先把起点到所有邻居的距离算出来挑最近的邻居过去再从那里继续往外扩每次都是“当前已知代价最小的节点优先扩展”。这个过程可以理解为你在一大片迷雾里找宝藏Dijkstra 的做法是从起点开始一圈一圈均匀地往外探索。每一圈都保证当前边界上的节点是“到起点代价最小”的。这样当你第一次到达终点时这条路径一定是全局最短的。关键点在于每次从优先队列里弹出的节点它的“最短路径”就已经确定了不需要再更新。这是 Dijkstra 正确性的核心保证。import heapq def dijkstra(graph, start, goal): # 优先队列元组为(当前累计代价, 节点) pq [(0, start)] # 记录起点到每个节点的最小代价 dist {start: 0} # 记录路径 prev {start: None} visited set() while pq: cost, node heapq.heappop(pq) if node in visited: continue visited.add(node) if node goal: # 回溯路径 path [] while node is not None: path.append(node) node prev[node] return path[::-1], cost for neighbor, weight in graph[node].items(): new_cost cost weight if neighbor not in dist or new_cost dist[neighbor]: dist[neighbor] new_cost prev[neighbor] node heapq.heappush(pq, (new_cost, neighbor)) return None, float(inf)这个实现做过两处优化一是用visited集合避免同一个节点被重复处理——因为从优先队列弹出的节点已经是最优的再弹出相同的节点可以直接跳过二是判断终点是否找到时放在弹出处而不是在压入队列时判断这样能保证找到的是真正的最短路径。1.3 A*带指南针的 DijkstraA* 和 Dijkstra 的代码结构几乎一模一样唯一区别是优先队列的排序依据从“起点到当前节点的累计代价 g(n)”改成了“ g(n) 启发式估计值 h(n)”也就是 f(n) g(n) h(n)。这里的 h(n) 是从当前节点到终点的估计代价它是 A* 的“指南针”。Dijkstra 是“从起点均匀撒网”A* 则是“优先朝终点方向探索”。import heapq import math def a_star(graph, start, goal, heuristic): # 优先队列元组为(f值, 累计代价g, 节点) pq [(0 heuristic(start, goal), 0, start)] dist {start: 0} prev {start: None} visited set() while pq: f, cost, node heapq.heappop(pq) if node in visited: continue visited.add(node) if node goal: path [] while node is not None: path.append(node) node prev[node] return path[::-1], cost for neighbor, weight in graph[node].items(): new_cost cost weight if neighbor not in dist or new_cost dist[neighbor]: dist[neighbor] new_cost # 注意这里压入的是 f 值 新累计代价 启发值 heapq.heappush(pq, (new_cost heuristic(neighbor, goal), new_cost, neighbor)) return None, float(inf)核心差异就这么简单Dijkstra 弹出的是 g(n) 最小的节点A* 弹出的是 g(n) h(n) 最小的节点。但就是这一行代码的区别让两者在搜索效率上天差地别。1.4 启发式函数的选择是灵魂A* 的效率完全取决于 h(n) 的设计。h(n) 不同算法表现完全不同甚至正确性都可能受影响。h(n) 0A* 退化成 Dijkstra失去方向感老老实实一圈圈撒网。h(n) 始终小于等于真实代价这种启发函数被称作“可采纳的Admissible”能保证 A* 找到最短路径。比如网格地图中用曼哈顿距离只能上下左右走或用欧几里得距离可以斜着走都满足这个条件。h(n) 真实代价这是最理想的情况A* 会直奔终点完全不走弯路但拿到这个函数本身就等于已经知道最短路径了。h(n) 大于真实代价A* 不再保证找到最短路径但搜索速度更快这种启发式叫做“不可采纳的”。实际项目中常有人为了提高速度使用“高估”的启发式比如把曼哈顿距离乘以一个大于 1 的系数。这样做确实会大幅减少搜索节点数但代价是结果可能不是最优路径。在游戏寻路中玩家往往感知不到“不是全局最短”这点小差异所以很多商业引擎就是这么做的。2. 深度对比两个算法到底差在哪2.1 搜索行为与效率对比Dijkstra 的搜索是“以起点为中心各向均匀扩展”。想象在二维网格地图上跑 Dijkstra你看到的搜索区域是一个以起点为中心的圆一圈一圈向外扩散直到扩展到终点为止。A* 的搜索区域则是一个以起点和终点连线为主轴的椭圆形甚至接近直线朝着终点方向明显更“用力”。这个差异在最坏情况下会非常大。在一个 1000x1000 的网格地图上如果起点在左上角终点在右下角Dijkstra 差不多要把整个地图都遍历一遍才能找到路径——因为它没有任何方向引导。A* 则只需要搜索主对角线附近的一小片区域搜索量能少一两个数量级。但 Dijkstra 也有 A* 比不了的场景。当图上没有明确的目标点时——比如你要算“从某个点到所有其他点的最短距离”Dijkstra 一次跑完就能得到所有答案A* 只能针对单个目标反复跑多次。另外如果启发式函数设计得不好A* 的“方向感”反而会把它带进坑里绕远路。2.2 适用场景对照我根据自己的项目经验总结了一张场景对照表你完全可以照着这个选场景推荐算法原因单起点到单终点的静态图A*启发式引导搜索范围小速度快单起点到多终点的查询Dijkstra一次遍历得到所有节点的最短路径多起点到多终点的路由表Dijkstra每个起点各跑一次结果全量复用网络拓扑动态变化、权重频繁修改两者都需重跑但 Dijkstra 实现更简单A* 的启发式在动态环境下容易失效地图规模大、寻路频繁游戏A*速度快配合抽稀、跳点优化效果显著迷宫地图、障碍复杂各有优劣取决于启发式质量启发式设计得好A* 优势极大2.3 一个容易忽略的隐性差异可扩展性我在实际项目里发现一个比较隐蔽的问题Dijkstra 的结果是可复用的A的结果不可复用*。什么意思如果一张地图上有大量“从任意起点到某个固定终点”的查询Dijkstra 从终点反向往外跑一遍把所有节点的最短路径都存下来后续任意起点直接查表返回结果时间复杂度 O(1)。A* 每个查询都要重新跑一遍虽然单次快但总次数上去了反而可能不如 Dijkstra 跑一次划算。这个场景在地图导航中很常见——一个物流中心的配送范围查询配送中心是固定终点几百个起始点需要计算最短配送路径。这时候用 Dijkstra 从配送中心反向跑一次用空间换时间效果奇佳。3. 实操踩坑从理论到能用的代码3.1 图怎么表示字典还是二维数组实现时第一个选择是图的表示方式。我一直用“字典套字典”的方式也就是键为节点值为一个字典里面存邻居节点和边权重graph { A: {B: 5, C: 1}, B: {A: 5, D: 2, E: 4}, C: {A: 1, D: 3, F: 6}, # ... }这种表示方式的好处是通用不管什么类型的图都能用。如果地图是规则的二维网格用二维数组更高效——每个格子的坐标本身就是节点上下左右就是邻居省去了节点编码和解码的麻烦。3.2 网格地图里启发式的选择网格地图是最常见的 A* 应用场景也是新手最容易踩坑的地方。网格地图分几种四方向移动上下左右和八方向移动加上斜对角。四方向移动用曼哈顿距离abs(dx) abs(dy)。因为移动一格代价为 1所以这个值恰好等于真实最短步数下界。八方向移动用切比雪夫距离max(abs(dx), abs(dy))或对角距离dx dy (sqrt(2) - 2) * min(dx, dy)。后者更精确因为对角线移动一次相当于水平加垂直但距离是 sqrt(2) 而不是 2。如果搞错了比如四方向移动用欧几里得距离搜索时会倾向于走对角线但实际不能斜着走表现就是路径拐来拐去搜索效率反而下降。这里的启发式函数不匹配是新手最容易犯的错误。3.3 实际代码里优先级队列的坑Python 里用heapq时有个非常隐蔽的坑堆里元素是元组比较时从第一个元素开始如果第一个元素相同就比较第二个元素。当节点用字符串表示时字符串可以比较没问题但如果节点是自定义对象没有定义比较函数就会报错。解决方式很粗暴在元组里塞一个不会重复的序号counter 0 heapq.heappush(pq, (f_value, counter, node)) counter 1这个序号只是用来打破平局防止 Python 去比较自定义节点对象。这种细节点跑到一半报TypeError: not supported between instances of Node and Node时才反应过来一次排查就是小半天。3.4 大数据量下的优化技巧当我处理过百万级节点的地图后发现几个优化的关键点按收益排序不要用visited集合改为给每个节点打“标记”字段。因为集合的哈希查询虽然快但百万级节点的重复查询开销也不小。用数组直接下标访问O(1) 且没有哈希冲突。优先队列用二叉堆就够不要用斐波那契堆。虽然理论复杂度更好但实际常数太大还不如二叉堆快。dist字典可以提前初始化成全无穷大数组省去字典查找的哈希开销。网格地图场景下节点可以用(row, col)转成单一整数索引数组访问远比字典快。限制搜索范围。如果地图非常大可以先用粗略的路径规划圈定一个“走廊区域”再在走廊内跑 A*。这是工程上常用的分层寻路思路。一个我踩过的坑用 Python 写 A*在 500x500 的网格上跑还可以到 2000x2000 就明显卡顿。后来发现是visited集合和dist字典的哈希开销太大。改成二维数组后速度直接提升了 40% 左右。4. 常见问题与调优经验4.1 为什么 A* 找出来的路径不是最短的太常见了几乎每周都有同事来问一次。多半是这几个原因启发式函数使用了高估比如用欧几里得距离除以一个小于 1 的数导致 h(n) 偏大。网格地图八方向移动但启发式用了曼哈顿距离低估了真实代价。低估一般不会破坏最优性但会降低效率。终点判定时机写错了。在压入队列的时候判断“这个节点是终点”而不是在弹出时判断。前者在某些情况下确实能加快速度少一次扩展但可能拿到非最优解——因为压入时只是“找到了终点”并不代表这是全局最优的到达方式。4.2 权重为负的时候会发生什么Dijkstra 和 A* 都要求边权重非负。如果图里有负权边贪心的“每次选最小”策略会失效——因为当前看起来代价更小的路径绕一圈走负权边后总代价反而更低而它可能已经被标记为“确认”了。处理负权图要换算法比如 Bellman-Ford。路径规划相关的实际场景里很少出现负权但如果你在做资源调度、成本优化这类问题得留个心眼。4.3 网格太大跑不动除了 A* 还能做什么A* 不是银弹地图大到一定程度光靠启发式优化是不够的。分享几个我实际用过的方案跳点搜索在网格地图上预处理跳点A* 只在跳点之间搜索中间节点直接跳过。实现复杂度中等提速效果通常有 10 倍以上。层次寻路把地图抽象成多个层次高层跑粗粒度、低层跑细粒度。经典方案是 HPA*Hierarchical Path-Finding A*。路点图不用网格手工放置路点waypoint在这些点上跑 A*。缺点是需要额外工作放置路点且路径不够精细但搜索速度极快。4.4 动态障碍物的处理思路游戏里经常有动态障碍物NPC 行走时路被突然挡住。最简单粗暴的方案是“撞到了就原地重新寻路”但这样会显得很傻。更好一点的做法是检测到原路径被阻塞时先将阻塞点标记为不可通行然后以当前位置为起点重跑 A*。如果阻塞点离终点很近可以只做局部重规划减少计算量。我自己比较喜欢的一种做法是“路径平滑 局部重规划”A* 跑出来的路径往往有锯齿状折线先用拉直算法如 Douglas-Peucker 或简单的视线检查平滑路径遇到动态障碍只对受影响的一段做局部重规划。这样既保留了全局最优性大部分时候又避免频繁全图重跑性能和效果都能兼顾。5. 我的实际使用感受跑了这么多项目后我对这两个算法的态度是先想清楚目标和场景再选算法。不要一听到 A* 就兴奋觉得 Dijkstra 是“老古董”。做多目标查询和全量路径计算时Dijkstra 稳如老狗做单目标实时寻路时A* 快如闪电。还有一个小技巧先用 Dijkstra 验证逻辑正确性再换 A优化性能*。Dijkstra 的实现简单不容易出错用它做基准测试确定最优路径确认逻辑没问题后再改成 A* 加启发式函数对比两者输出的路径是否一致在可采纳启发式下应该是一致的。这个工作流帮我排查过不少启发式函数设计错误。最后再分享一个判断搜索质量的指标A的扩展节点数*。如果启发式函数设计得好扩展节点数应该远小于总节点数。如果发现 A* 快把整个图都搜完了才找到终点那大概率是启发式函数写错了赶紧回头检查 h(n) 的实现。