4、静态路径规划算法（Dijkstra）：原理、对比与场景分析
好，咱们今天聊聊 Dijkstra 算法。说实话，这玩意儿是路径规划领域的“老大哥”。我当年刚入行时，第一个认真啃下来的算法就是它。别看现在 A* 满天飞，但 Dijkstra 的底子打不牢，后面很多优化思路你根本接不住。
4.1 Dijkstra 算法原理：说白了就是“贪心 + 松弛”
Dijkstra 的核心思想，我总结成一句话：从起点出发，每次选一个当前距离最近且没处理过的节点，然后尝试用它去更新邻居的距离。这个过程叫“松弛”，你想想看，就像一根橡皮筋，你不断往外拉，直到绷紧到最短路径。
具体步骤其实不复杂：
- 初始化：起点距离设为 0，其他所有节点距离设为无穷大。
- 维护一个优先队列（或者简单点，每次遍历找最小）。
- 每次从队列里弹出距离最小的节点 u。
- 遍历 u 的所有邻居 v，如果
dist[u] + weight(u,v) < dist[v]，就更新 dist[v]。 - 重复直到队列为空。
嗯，这里要注意：Dijkstra 不能处理负权边。为什么？因为一旦有负权边，你之前认为“已经确定”的最短路径可能被后面更小的值推翻。我在项目中遇到过这种坑，后面会细说。
核心要点：Dijkstra 是一种贪心算法，它假设“当前距离最小的节点，它的最短路径已经确定”。这个假设只在非负权图中成立。
来个简单的代码示例，我用 Python 写了个最朴素的版本：
import heapq
def dijkstra(graph, start):
# graph: 邻接表，{node: [(neighbor, weight), ...]}
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)] # (距离, 节点)
while pq:
current_dist, u = heapq.heappop(pq)
if current_dist > dist[u]:
continue # 过时的条目，跳过
for v, w in graph[u]:
new_dist = dist[u] + w
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return dist
这段代码我用了很多年，基本没变过。你注意看第 8 行的 if current_dist > dist[u]，这个判断很多人会漏掉。我曾经因为这个 bug 在仿真里跑了一整夜，结果发现路径全是错的……从那以后，我写 Dijkstra 第一件事就是加这个跳过逻辑。
4.2 Dijkstra 与 A* 的对比：一个“盲目”，一个“有方向”
很多人问我：“既然有 A*，为什么还要学 Dijkstra？”我的回答是：Dijkstra 是 A* 的“无启发式版本”。你想想看，A* 就是在 Dijkstra 的基础上加了一个启发函数 h(n)，用来引导搜索方向。
我整理了一个对比表，这样更直观：
| 对比维度 | Dijkstra | A* |
|---|---|---|
| 搜索策略 | 广度优先 + 贪心 | 启发式搜索 |
| 启发函数 | 无（h(n)=0） | 有（如欧几里得距离） |
| 最优性 | 保证全局最优 | 保证最优（当 h(n) 可采纳时） |
| 搜索范围 | 全图扩散，像个圆 | 朝目标方向，像个锥形 |
| 时间复杂度 | O((V+E)logV) | 通常更快，但最坏情况相同 |
| 适用场景 | 无启发信息、负权边（需改算法） | 有明确目标、地图较大 |
我个人习惯这样选：如果地图小，或者你需要保证绝对最优，用 Dijkstra 准没错。如果地图大、目标明确，比如从北京到上海，那 A* 的启发式能帮你省掉大量计算。
我的经验：在机器人路径规划中，如果环境是静态的且节点数少于 1000，我通常直接用 Dijkstra。代码简单，不容易出 bug，而且调试起来特别方便。A* 虽然快，但启发函数设计不好反而会引入误差。
4.3 适用场景分析：什么时候该用它？
Dijkstra 不是万能的，但它在某些场景下确实无可替代。我总结了三个典型场景：
- 场景一：静态地图上的全局路径规划
比如仓库里的 AGV 小车，地图是固定的，障碍物位置已知。这时候 Dijkstra 能给出从充电桩到货架的最短路径。我做过一个项目，20 台 AGV 同时跑，每台都用 Dijkstra 算路径，配合交通管制，效果很稳。 - 场景二：网络路由协议
OSPF（开放最短路径优先）协议用的就是 Dijkstra。每个路由器维护一张链路状态数据库，然后跑 Dijkstra 算出到所有其他路由器的最短路径。这个场景下，节点数通常几百到几千，Dijkstra 完全够用。 - 场景三：作为其他算法的基准
我在做算法对比时，经常用 Dijkstra 的结果作为“黄金标准”。比如测试 A* 的优化效果，我就看它比 Dijkstra 快了多少，同时路径长度有没有变差。
避坑指南：我曾经在一个项目中，地图里有负权边（比如下坡路有“奖励”），直接用 Dijkstra 算出来的路径居然是错的。后来我才意识到，Dijkstra 不能处理负权边。如果你遇到这种情况，请改用 Bellman-Ford 算法。记住：Dijkstra 的“贪心”假设在负权图里不成立。
另外，Dijkstra 不适合动态环境。因为一旦地图变了，它需要从头重新计算。我见过有人试图用“增量式 Dijkstra”来应对动态变化，但说实话，效果不如 D* Lite 或 RRT* 这类专门为动态环境设计的算法。
最后总结一下我的看法：Dijkstra 是路径规划的“基本功”。它简单、可靠、容易理解。虽然现在有很多更花哨的算法，但 Dijkstra 的思想——贪心选择 + 松弛更新——是所有高级算法的基础。你把它吃透了，后面学 A*、D*、RRT 都会轻松很多。
嗯，这一节就到这里。下一节我们聊聊 A* 的启发函数怎么设计，那才是真正体现功力的地方。