4. 经典算法：Dijkstra算法原理、与A*的对比分析
聊到路径规划，Dijkstra算法是个绕不开的起点。说实话，我入行那会儿，第一个认真啃下来的算法就是它。那时候做AGV调度，地图就几十个节点，用Dijkstra跑起来还挺顺畅。后来场景复杂了，才慢慢体会到它和A*之间的差距。
今天咱们就把Dijkstra掰开揉碎了讲清楚，再跟A*做个对比。嗯，这部分内容，我个人觉得是理解更高级规划算法的基石。
4.1 Dijkstra算法的核心思想
Dijkstra算法解决的是“单源最短路径”问题。说白了，就是从一个起点出发，找到去地图上所有其他点的最短路径。它是个贪心算法，每一步都选当前代价最小的节点去扩展。
它的核心逻辑，我总结为三步：
- 初始化：起点代价为0，其他所有点代价为无穷大。
- 选择：从未处理的节点中，挑出当前代价最小的那个。
- 松弛：检查这个节点的邻居，如果通过当前节点能获得更小的代价，就更新邻居的代价。
重复第2和第3步，直到所有节点都被处理过。
关键点：Dijkstra算法保证，当它第一次从优先队列中取出一个节点时，这个节点的代价就是全局最优的。这个性质，我当年面试时被问过好几次。
4.2 算法流程与代码实现
咱们直接看代码。这是我习惯用的一个实现，用Python写的，清晰易懂。
import heapq
def dijkstra(graph, start):
# graph: 邻接表，{node: [(neighbor, cost), ...]}
# 初始化
distances = {node: float('inf') for node in graph}
distances[start] = 0
pq = [(0, start)] # (代价, 节点)
visited = set()
while pq:
current_dist, current_node = heapq.heappop(pq)
if current_node in visited:
continue
visited.add(current_node)
# 松弛操作
for neighbor, weight in graph[current_node]:
distance = current_dist + weight
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(pq, (distance, neighbor))
return distances
这段代码里，我用了heapq来实现优先队列。为什么？因为每次取最小代价节点时，堆的复杂度是O(log N)，比线性扫描快得多。我在项目中遇到过有人用列表加min()函数，地图一大，直接卡死。
避坑指南：我曾经在实现时忘记用visited集合，结果同一个节点被反复处理，算法效率大打折扣。记住，节点一旦被弹出，它的最短路径就已经确定了，不需要再处理。
4.3 Dijkstra vs A*：核心差异
A*算法可以看作是Dijkstra的“升级版”。它引入了一个启发式函数h(n)，来引导搜索方向。咱们用一个表格来对比，这样更直观。
| 对比维度 | Dijkstra | A* |
|---|---|---|
| 代价函数 | f(n) = g(n) | f(n) = g(n) + h(n) |
| 搜索方向 | 均匀向外扩展 | 朝目标方向扩展 |
| 最优性 | 保证全局最优 | h(n)可采纳时保证最优 |
| 适用场景 | 无启发信息、需要全图路径 | 有明确目标、地图较大 |
| 时间复杂度 | O((V+E)logV) | 通常优于Dijkstra |
你想想看，Dijkstra像个“无头苍蝇”，从起点一圈一圈往外扩。而A*有了启发函数，就像有了指南针，知道目标在哪个方向，优先往那个方向探索。
为什么会这样？因为A*的代价函数里多了个h(n)。h(n)是当前节点到目标的估计代价。如果h(n)始终小于等于真实代价，A*就能保证找到最短路径，而且比Dijkstra快得多。
4.4 什么时候该用Dijkstra？
我个人觉得，Dijkstra并没有过时。在以下场景，它反而是更好的选择：
- 需要计算所有点到所有点的最短路径：比如做路网分析，Dijkstra跑一次就能得到起点到所有点的距离。
- 没有好的启发函数：有些场景下，你很难估计到目标的距离。比如在抽象状态空间里，h(n)不好定义。
- 地图规模小：节点数在几百以内，Dijkstra和A*的差距不大，用Dijkstra反而更简单可靠。
注意：Dijkstra不能处理负权边。如果图里有负权边，得用Bellman-Ford算法。我在做机器人路径规划时，很少遇到负权边，但做图论题时经常被坑。
4.5 知识体系流程图
下面这张图，是我梳理的Dijkstra与A*对比的知识结构。你可以把它当作一个快速索引。
4.6 我的个人经验
我记得有一次做仓储机器人项目，地图有上千个节点。一开始我用Dijkstra，每次规划路径要等好几秒。后来换成A*，用曼哈顿距离做启发函数，规划时间降到了几十毫秒。效果立竿见影。
但我也踩过坑。有一次启发函数设计得太“乐观”，导致A*扩展了太多节点，性能反而比Dijkstra还差。嗯，这里要注意：h(n)不能太大，否则会失去引导作用；也不能太小，否则退化成Dijkstra。
说白了，Dijkstra和A*没有绝对的优劣。它们就像工具箱里的两把扳手，用哪个取决于你要拧什么样的螺丝。理解它们的原理和差异，你才能在项目中做出正确的选择。
一句话总结：Dijkstra稳扎稳打，保证最优；A*有方向感，效率更高。选哪个，看你的场景有没有“指南针”。