什么是懒删除？
在Dijkstra算法中，同一个节点可能被多次加入优先队列，但只有最短的那次才是有效的。懒删除就是"推迟删除"，直到真正从队列中取出时再判断是否有效。
举个例子理解
假设有这样一个图：
A --2--> B
A --5--> C
B --1--> C
执行过程：
-
初始：
- dist[A] = 0, dist[B] = ∞, dist[C] = ∞
- 队列：[A(0)]
-
处理A：
- 更新B：dist[B] = 0+2=2，B(2)入队
- 更新C：dist[C] = 0+5=5，C(5)入队
- 队列：[B(2), C(5)]
-
处理B：
- 更新C：通过B到C：2+1=3 < 5
- dist[C] = 3，C(3)入队
- 队列：[C(5), C(3)] ← 同一个节点C在队列中出现两次
-
现在队列中有两个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]) {// ... 更新邻居}
}