4. Dijkstra算法原理：算法思想、伪代码、时间复杂度分析、优缺点
各位同学好，今天我们来聊聊路径规划里最经典的一个算法——Dijkstra。说实话，我入行那会儿，第一个认真啃下来的算法就是它。那时候还在做AGV调度，车间里几十台小车跑来跑去，路径规划全靠它撑着。嗯，咱们今天就把它彻底讲透。
4.1 算法思想：说白了就是“贪心+松弛”
Dijkstra算法的核心思想，我总结成一句话：从起点出发，每次选一个离起点最近且没处理过的节点，然后看看能不能通过它让别的节点更近一些。这个过程，专业术语叫“松弛”。
你想想看，这像不像我们平时找路？比如你要去一个陌生商场找某个店铺，你会先看看离你最近的几个路口，然后一步步往外扩。Dijkstra就是这么干的，只不过它用数学保证了每一步都是最优的。
我个人习惯把Dijkstra理解成“水波扩散”。从起点扔一颗石子，水波一圈圈往外推，最先碰到目标的那一圈，就是最短路径。这个比喻在我带新人时屡试不爽。
关键前提：图中所有边的权重必须是非负的。如果有负权边，Dijkstra会翻车——这个我后面会讲。
4.2 伪代码：咱们手写一遍
光说理论不够，咱们直接上伪代码。这是我当年在项目里实际用过的版本，稍微整理了一下：
function Dijkstra(Graph, source):
// 初始化
dist[source] = 0 // 起点到自己的距离为0
for each vertex v in Graph:
if v != source:
dist[v] = INFINITY // 其他节点距离设为无穷大
prev[v] = NULL // 前驱节点，用于回溯路径
add v to Q // 所有节点加入未处理集合
// 主循环
while Q is not empty:
u = vertex in Q with min dist[u] // 贪心：选距离最小的节点
remove u from Q
for each neighbor v of u: // 遍历u的所有邻居
alt = dist[u] + weight(u, v) // 计算新距离
if alt < dist[v]: // 如果新距离更短
dist[v] = alt // 更新距离
prev[v] = u // 记录前驱
return dist[], prev[]这段代码我当年背得滚瓜烂熟。你看，逻辑其实很清晰：初始化 → 循环选最小 → 松弛邻居。就这么三步。
避坑指南：我曾经在实现时犯过一个低级错误——忘记把起点从Q里移除。结果起点被反复选中，陷入死循环。嗯，这种细节往往最要命。
4.3 时间复杂度分析
时间复杂度取决于你用啥数据结构来维护那个“未处理节点集合Q”。咱们分几种情况聊聊：
| 实现方式 | 时间复杂度 | 适用场景 |
|---|---|---|
| 普通数组/列表 | O(V²) | 节点少（V < 1000） |
| 二叉堆（优先队列） | O((V+E) log V) | 稀疏图，最常用 |
| 斐波那契堆 | O(E + V log V) | 边特别多的大图 |
我项目中90%的情况都用二叉堆实现。为啥？因为V和E通常都在几千到几万这个量级，二叉堆已经足够快，而且实现简单。斐波那契堆虽然理论更快，但常数大、实现复杂，性价比不高。
这里有个小经验：如果图是网格地图（比如机器人栅格地图），V可能上百万，这时候O(V²)就扛不住了。我当年第一次做仓储机器人调度，地图1000×1000，用数组实现直接卡死。后来换成堆，秒出结果。
4.4 优缺点分析
做了这么多年算法，我越来越觉得：没有银弹，只有合适的工具。Dijkstra也一样，有它的长处和短板。
优点
- 保证最优解：只要边权非负，Dijkstra一定能找到最短路径。这个性质在工程中非常宝贵。
- 实现简单：伪代码就那么几行，调试起来也方便。我经常用它作为基准，验证其他算法的正确性。
- 稳定可靠：不像某些启发式算法（比如A*）可能因为启发函数设计不当而跑偏，Dijkstra老老实实，从不耍花招。
缺点
- 慢：说白了，它要探索很多无关节点。比如起点在深圳，目标在北京，它会把广州、长沙、武汉全算一遍才到北京。这在大型地图上很要命。
- 不能处理负权边：这是硬伤。如果有负权边，Dijkstra会过早地把某个节点标记为“已处理”，后面发现更短路径时已经来不及了。我踩过这个坑——有一次做路径规划，地图里有个“下坡路”被我设成了负权，结果算法给出的路径完全不对。
- 无方向性：它不知道目标在哪，只能盲目地往各个方向扩散。相比之下，A*算法用启发函数引导搜索方向，效率高得多。
注意：如果你遇到负权边，别硬用Dijkstra。改用Bellman-Ford算法，虽然慢点，但至少结果是对的。我曾经在一个项目里为了省事强行用Dijkstra处理负权图，结果被测试同学追着改bug改了一周。
4.5 知识体系总览
下面这张图是我自己画的，把Dijkstra的核心知识点串在了一起。你看一遍，应该就能建立起整体认知：
这张图把Dijkstra的四个核心维度串起来了。你看，算法思想决定了伪代码怎么写，伪代码又直接影响时间复杂度，而时间复杂度最终决定了它的优缺点和适用场景。一环扣一环。
4.6 我的实战建议
最后，结合我这些年的经验，给你几条实在的建议：
- 小图用Dijkstra，大图用A*：如果节点数少于1000，Dijkstra完全够用。超过这个量级，建议上A*或者JPS（跳点搜索）。
- 优先队列用对了，事半功倍：C++用priority_queue，Python用heapq，Java用PriorityQueue。别自己手写堆，容易出bug。
- 别忘了回溯路径：很多人只关注dist数组，忘了记录prev。没有prev，你只知道最短距离，却不知道具体怎么走。我见过不止一个新手犯这个错。
- 测试时用网格地图：我习惯先用一个10×10的网格图测试，肉眼就能验证结果对不对。没问题了再上真实地图。
好了，Dijkstra就讲到这里。这个算法虽然简单，但它是很多高级路径规划算法的基础。把它的原理吃透了，后面学A*、D*、RRT*都会轻松很多。
可可精品资料库