4、单目标路径规划基础：Dijkstra算法原理、实现与局限性
各位同学，今天我们来聊聊路径规划里最经典的一个算法——Dijkstra。说实话，我入行那会儿，第一个认真啃下来的算法就是它。那时候还在做地面机器人巡检的项目，地图不大，但要求绝对最优解。Dijkstra虽然慢，但胜在稳，结果可解释性强。直到现在，我在做多目标航迹规划时，底层依然会用它做基准校验。
4.1 算法核心思想：贪心 + 松弛
Dijkstra算法的本质，说白了就是一句话：从起点出发，每次选一个当前距离最短的未处理节点，然后尝试用它去更新邻居的距离。这个过程叫“松弛”（Relaxation）。
你想想看，这像不像我们平时做决策？手里有一堆待办事项，先挑最紧急的那个处理掉，处理完再看看有没有因为这件事而变得更容易解决的其他事。嗯，就是这个道理。
核心前提：Dijkstra要求图中所有边的权重必须为非负数。为什么？因为一旦有负权边，当前选出的“最短距离”节点可能并不是真正的全局最短，后面再松弛时可能会发现更短的路径。这个坑，我踩过。
4.2 算法步骤详解
我个人习惯把Dijkstra拆成三个关键步骤来记：
- 初始化：起点距离设为0，其他节点距离设为无穷大。所有节点标记为“未访问”。
- 选择：从未访问节点中，选出距离最小的那个节点u。
- 松弛：遍历u的所有邻居v，如果
dist[u] + w(u,v) < dist[v]，就更新dist[v]，并记录前驱节点。
重复步骤2和3，直到所有节点都被访问过，或者目标节点被访问到（可以提前终止）。
我的小技巧：在实际工程中，我通常用优先队列（最小堆）来维护“未访问节点集合”，这样每次选最小距离节点的时间复杂度能从O(n)降到O(log n)。
4.3 代码实现：C++ 版本
下面是我在项目中常用的一个实现模板。注意，这里我用的是邻接表 + 优先队列，适合稀疏图。
#include <vector>
#include <queue>
#include <limits>
using namespace std;
const int INF = numeric_limits<int>::max();
// 图结构：邻接表，每个元素为 (邻居节点, 边权)
typedef pair<int, int> Edge;
vector<vector<Edge>> graph;
vector<int> dijkstra(int start, int n) {
vector<int> dist(n, INF);
dist[start] = 0;
// 优先队列：存储 (距离, 节点编号)，按距离升序
priority_queue<Edge, vector<Edge>, greater<Edge>> pq;
pq.push({0, start});
while (!pq.empty()) {
int d = pq.top().first;
int u = pq.top().second;
pq.pop();
// 如果当前取出的距离比记录的大，说明是旧数据，跳过
if (d > dist[u]) continue;
for (auto &edge : graph[u]) {
int v = edge.first;
int w = edge.second;
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.push({dist[v], v});
}
}
}
return dist;
}
注意：代码中 if (d > dist[u]) continue; 这一行非常关键。我曾经在早期版本中漏掉它，结果优先队列里堆积了大量过期数据，导致内存暴涨。这是Dijkstra实现中最常见的bug之一。
4.4 算法复杂度分析
| 实现方式 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 朴素数组实现 | O(V²) | O(V) | 稠密图（边数接近V²） |
| 二叉堆 + 邻接表 | O((V+E)logV) | O(V+E) | 稀疏图（大多数实际场景） |
| 斐波那契堆 + 邻接表 | O(VlogV + E) | O(V+E) | 理论最优，工程实现复杂 |
在实际的无人机航迹规划中，我们的图通常是稀疏的——每个节点只连接附近几个邻居。所以二叉堆实现是首选。我记得有一次做城市低空航路规划，节点数上万，用二叉堆Dijkstra跑一次也就几十毫秒，完全够用。
4.5 局限性：为什么不能直接用于多目标规划？
Dijkstra虽然经典，但用在多目标航迹规划上，有几个硬伤：
- 单源单目标效率低：如果只求一个目标点，Dijkstra仍然会探索大量无关区域。A*算法通过启发式函数解决了这个问题。
- 无法处理负权边：这在无人机场景中不常见，但如果你用“时间窗”或“惩罚项”建模，可能会出现负权。
- 多目标时重复计算：如果有N个目标点，你需要跑N次Dijkstra。这在实时规划中是不可接受的。
- 不直接支持约束：比如无人机最大转弯角、禁飞区等，Dijkstra本身不处理这些，需要额外改造。
我的经验：在《多目标航迹规划与冲突解决方案》课程中，Dijkstra更多是作为“基准算法”存在。我们用它来验证更高级算法的结果是否正确。比如，我会先跑一次Dijkstra得到理论最优解，然后对比启发式算法（如A*、RRT*）的误差。
4.6 知识体系流程图
下面我用一张SVG图来总结本章的核心逻辑，方便你建立整体认知：
4.7 避坑指南与工程建议
最后，分享几个我在实际项目中积累的经验：
- 关于无穷大的选择：不要用
INT_MAX，因为做加法时会溢出。我习惯用1e9或0x3f3f3f3f，后者在C++里加两倍也不会溢出。 - 关于提前终止：如果只求到某个目标点的最短路径，当目标节点被弹出优先队列时就可以停了。这能省下不少时间。
- 关于路径重建：别忘了维护前驱数组。我见过有人只算距离不存路径，结果跑完发现不知道路怎么走——这在实际中毫无意义。
- 关于动态变化：如果地图是动态的（比如临时禁飞区），Dijkstra需要重新跑。这时候可以考虑LPA*或D* Lite等增量算法。
一句话总结：Dijkstra是路径规划的“Hello World”。它简单、正确、可解释，但效率有限。掌握它是理解更高级算法（A*、D*、RRT等）的基石。下一章我们会看到，如何通过加入启发式信息，把Dijkstra升级成A*算法。
公众号:蓝海资料掘金营，微信deep3321