最短路径 - Dijkstra（堆优化）中优先队列的懒删除如何理解？

什么是懒删除？

在Dijkstra算法中，同一个节点可能被多次加入优先队列，但只有最短的那次才是有效的。懒删除就是"推迟删除"，直到真正从队列中取出时再判断是否有效。

举个例子理解

假设有这样一个图：

A --2--> B
A --5--> C
B --1--> C

执行过程：

1. 初始：

   • dist[A] = 0, dist[B] = ∞, dist[C] = ∞
   • 队列：[A(0)]

2. 处理A：

   • 更新B：dist[B] = 0+2=2，B(2)入队
   • 更新C：dist[C] = 0+5=5，C(5)入队
   • 队列：[B(2), C(5)]

3. 处理B：

   • 更新C：通过B到C：2+1=3 < 5
   • dist[C] = 3，C(3)入队
   • 队列：[C(5), C(3)] ← 同一个节点C在队列中出现两次

4. 现在队列中有两个C：

   • C(5) - 旧的，过时的
   • C(3) - 新的，更短的

懒删除的工作原理

while (!pq.isEmpty()) {int[] cur = pq.poll();  // 1. 从队列取出int u = cur[0], d = cur[1];// 2. 关键检查：如果取出的距离 > 当前记录的最短距离if (d > dist[u]) {continue;  // 跳过这个过时的记录}// 3. 只有这个距离 <= 记录的最短距离，才处理for (Edge e : graph[u]) {// ... 更新邻居}
}