Dijkstra算法原理：算法思想、距离更新规则、优先队列的作用
好，咱们今天来聊聊Dijkstra算法。说实话，这个算法在我刚入行做路径规划时，是第一个让我觉得「哇，原来计算机可以这样思考」的算法。它不像A*那样带点「直觉」，Dijkstra更像一个老实人——一步一步来，绝不走捷径。
算法思想：从起点出发，像水波一样扩散
Dijkstra的核心思想，说白了就是一句话：从起点开始，逐步探索离起点最近的点，直到到达终点。
你想想看，它像什么？就像你在平静的水面扔下一颗石子。波纹从落点一圈一圈往外扩散。每一圈波纹上的点，都是当前离起点最近的那些点。Dijkstra就是这么干的——它维护一个「已确定最短路径」的集合，然后不断把「下一个最近的点」加进来。
我记得有一次在项目中，需要在一个有几十万个节点的地图上做路径规划。当时团队里有人想直接用A*，但我坚持先用Dijkstra做基准测试。为什么？因为Dijkstra保证能找到全局最优解，而A*在某些启发式函数设计不好的情况下会跑偏。嗯，这就是老实人的好处——靠谱。
核心思想总结：
- 从起点出发，逐步扩展
- 每次选择当前距离起点最近且未访问的节点
- 保证每个节点第一次被访问时，距离就是最短距离
- 直到所有节点都被访问，或者到达目标节点
距离更新规则：松弛操作
Dijkstra里最核心的操作，叫做「松弛」。这个词听起来挺玄乎，其实很简单。
假设我们当前在节点A，已知A到起点的最短距离是d[A]。现在A有一条边通向B，边的权重是w(A,B)。那么从起点经过A再到B的距离就是 d[A] + w(A,B)。
如果这个值比当前记录的d[B]还要小，我们就更新d[B] = d[A] + w(A,B)。这个过程就叫松弛。
用公式表达就是：
if d[A] + w(A,B) < d[B]:
d[B] = d[A] + w(A,B)
parent[B] = A # 记录路径我曾经在调试一个无人车路径规划模块时，发现车辆总是绕远路。查了半天，原来是松弛操作里忘记更新父节点了。结果路径虽然距离对了，但回溯出来的路径是错的。这个坑我踩过，你千万别踩。
注意：松弛操作的前提是，当前节点A已经被确定为最短路径节点。也就是说，只有从「已确定」的节点出发去更新邻居，才是有效的。否则可能会出现「用未确定的距离去更新别人」的情况，导致结果错误。
优先队列的作用：高效选点
好，现在问题来了。Dijkstra每轮都要从所有未访问的节点中，选出距离起点最近的那个。如果每次都用遍历的方式去找，那复杂度就是O(n²)。对于大规模地图来说，这太慢了。
这时候就需要优先队列登场了。优先队列（通常用最小堆实现）可以让我们在O(log n)的时间内取出最小值，在O(log n)的时间内插入新值。
具体怎么用？
- 把起点放入优先队列，距离为0
- 每次从队列中取出距离最小的节点
- 如果该节点已经访问过，跳过
- 否则标记为已访问，然后对该节点的所有邻居执行松弛操作
- 如果某个邻居的距离被更新了，就把新的距离和该邻居一起放入优先队列
- 重复直到队列为空或到达目标
这里有个细节我想强调一下：优先队列里可能会存在同一个节点的多个不同距离的副本。比如节点B先被以距离10放入队列，后来又被以距离8更新了，那么队列里就有两个B。我们取出来的时候，先取到的是距离8的那个，然后标记B已访问。后面再取到距离10的那个B时，发现已经访问过了，直接跳过就行。
我个人习惯用Python的heapq来实现，代码非常简洁：
import heapq
def dijkstra(graph, start, end):
# graph: 邻接表，graph[u] = [(v, w), ...]
INF = float('inf')
dist = {node: INF for node in graph}
dist[start] = 0
pq = [(0, start)] # (距离, 节点)
visited = set()
while pq:
d, u = heapq.heappop(pq)
if u in visited:
continue
visited.add(u)
if u == end:
return d
for v, w in graph[u]:
if v not in visited:
new_dist = d + w
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (new_dist, v))
return INF # 不可达小技巧：在实际项目中，我通常不会用visited集合，而是用dist字典来判断。如果从队列中取出的距离大于dist中记录的距离，说明这个节点已经被更新过了，直接跳过。这样可以省掉一个集合的内存开销。
算法流程总结
把上面说的串起来，Dijkstra的完整流程就是：
| 步骤 | 操作 | 说明 |
|---|---|---|
| 1 | 初始化 | 起点距离设为0，其他节点距离设为无穷大 |
| 2 | 入队 | 将起点放入优先队列 |
| 3 | 取点 | 从队列中取出距离最小的节点 |
| 4 | 检查 | 如果已访问则跳过，否则标记为已访问 |
| 5 | 松弛 | 更新所有邻居的距离 |
| 6 | 入队 | 被更新的邻居放入优先队列 |
| 7 | 循环 | 重复3-6直到队列为空或到达目标 |
你可能会问：为什么Dijkstra不能处理负权边？嗯，这个问题问得好。因为Dijkstra假设「已经确定最短路径的节点，不会再被更短的路径更新」。但如果有负权边，后面可能会出现一条更短的路径，打乱这个假设。所以Dijkstra只适用于非负权图。如果你遇到负权边，那就得用Bellman-Ford了——不过那是另一节课的内容。
最后说一句，Dijkstra虽然看起来简单，但它在自动驾驶路径规划中的地位不可替代。很多全局规划器底层用的就是Dijkstra或者它的变种。理解透了这个算法，后面学A*、Hybrid A*都会轻松很多。