图搜索算法（上）：Dijkstra算法原理、实现与优缺点
说到路径规划，Dijkstra算法是绕不开的基石。我个人觉得，搞懂它，后面学A*、D*这些高级算法会轻松很多。说白了，Dijkstra就是解决“从A点到B点，哪条路最短”这个问题的最经典方法。
算法核心思想：贪心 + 动态规划
Dijkstra算法的本质，其实就两句话：每次找离起点最近的那个未处理节点，然后用它去更新邻居的距离。嗯，听起来很简单对吧？
我刚开始学的时候，总觉得这玩意儿跟“广度优先搜索”有点像。区别在哪呢？BFS用队列，一层层往外扩；Dijkstra用优先队列，谁距离小谁先出。你想想看，如果每条边的权重都是1，那Dijkstra就退化成BFS了。
核心前提：Dijkstra要求图中不能有负权边。为什么？因为一旦有负权边，已经确定的最短距离可能被后续的负权边“反超”，算法就失效了。
算法步骤详解
咱们一步步来拆解。假设有一个图，起点是S，终点是T。
- 初始化：所有节点的距离设为无穷大，起点S的距离设为0。创建一个优先队列，把S放进去。
- 循环处理：从优先队列里取出距离最小的节点u。
- 松弛操作：遍历u的所有邻居v。如果
dist[u] + weight(u,v) < dist[v]，就更新dist[v]，并把v加入优先队列。 - 重复：直到优先队列为空，或者取出了目标节点T。
这里有个细节：每个节点可能被多次加入优先队列，但只有第一次取出时，它的距离才是最终确定的。我在项目中遇到过有人没注意这点，导致算法死循环——嗯，调试了一下午才发现。
代码实现：Python版
我个人习惯用Python写原型，清晰又好改。下面是一个标准实现：
import heapq
def dijkstra(graph, start, end):
# graph: 邻接表，{node: [(neighbor, weight), ...]}
INF = float('inf')
dist = {node: INF for node in graph}
dist[start] = 0
pq = [(0, start)] # (距离, 节点)
visited = set()
while pq:
current_dist, u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
if u == end:
return current_dist
for v, w in graph[u]:
if v in visited:
continue
new_dist = current_dist + w
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return INF # 不可达避坑指南：我曾经在实现时忘了加visited集合，结果同一个节点被反复处理，性能直接崩了。记住：优先队列里取出的节点，如果已经访问过，直接跳过。
时间复杂度分析
这个得说清楚。用二叉堆实现的话：
| 操作 | 复杂度 | 说明 |
|---|---|---|
| 插入/更新 | O(log V) | 每个节点最多入堆一次 |
| 取出最小 | O(log V) | 每次取一个 |
| 总复杂度 | O((V+E) log V) | V是节点数，E是边数 |
如果图比较稠密（E接近V²），用斐波那契堆可以降到O(V log V + E)。但说实话，工程上很少用斐波那契堆——常数太大，实现也复杂。二叉堆够用了。
优缺点分析
优点：
- 保证找到最短路径（前提是无负权边）
- 实现简单，代码量少
- 适用于静态图（拓扑不变的情况）
缺点：
- 没有方向性，会探索很多无关区域。你想想看，如果目标在起点东边，它还是会往西边搜
- 在大规模图上，内存消耗大（需要存所有节点的距离）
- 无法处理动态变化的环境（比如突然出现的障碍物）
注意：在自动驾驶的全局路径规划中，Dijkstra很少直接使用。因为道路网络动辄几万个节点，跑一次要几百毫秒，太慢了。但它是理解A*算法的基础——A*就是在Dijkstra基础上加了启发式函数。
核心逻辑流程图
下面这张图展示了Dijkstra算法的核心流程，我特意画得简洁一些：
这张图把核心循环画清楚了。你注意看那个“已访问”的判断——这是很多人容易漏掉的。我刚开始写的时候，没加这个判断，结果在环形图上跑出了死循环。
实际应用中的坑
最后分享几个实战经验：
- 地图太大怎么办？ 可以用分层Dijkstra。先把地图分成区块，在区块级别做规划，再在区块内部细化。我在做园区物流机器人时用过这招，效果不错。
- 实时性要求高？ 可以设置一个最大搜索半径。比如只搜500米内的节点，超出就放弃。虽然可能找不到最优解，但至少能快速给出一个可行解。
- 路径平滑问题：Dijkstra找出来的路径可能有很多折角。我建议后面加一个平滑处理，比如用B样条曲线拟合一下。
一句话总结：Dijkstra是图搜索的“Hello World”，简单、可靠、但不够聪明。理解它，你就能理解更高级的启发式搜索算法。
可可精品资料库