实现Dijkstra算法时PriorityQueue的poll()返回错误对象如何修复

问题根因 #

Java 标准库的PriorityQueue基于二叉小顶堆实现，仅在元素执行入队offer()、出队poll()操作时才会进行堆调整。元素入队后你修改了它参与排序的weight属性，队列内部无法感知到这个变化，也不会自动重新排序堆结构，因此堆顶始终是旧逻辑下的最小元素，自然拿不到更新后的最小权重节点。

推荐修复方案：懒删除（性能最优、实现简单） #

这是实现Dijkstra算法最常用的适配方案，不用修改队列原有元素，仅靠额外标记过滤无效元素即可：

1. 给Node类新增boolean visited属性，默认值为false，用于标记节点是否已经被取出处理过
2. 松弛操作更新节点权重后，直接把更新后的节点重新插入优先队列，不用处理队列中已存在的旧版本同节点
3. 每次从队列取出节点后，先判断是否已经处理过，已处理则直接跳过当前循环，未处理则先标记为已处理，再执行后续松弛逻辑

另外注意你当前的代码没有给源点设置初始权重为0，所有节点默认都是Integer.MAX_VALUE，也会导致逻辑错误，需要补充初始化逻辑。

修复后的代码示例

修改后的Node类：

private static class Node implements Comparable<Node>{
    String name;
    ArrayList<Edge> connections;
    int weight;
    Node parent;
    boolean visited; // 新增标记

    public Node(String name) {
        this.name = name;
        this.weight = Integer.MAX_VALUE;
        parent = null;
        connections = new ArrayList<>();
        this.visited = false;
    }

    // 其余方法保持不变
    public void addConnection(Node node, int weight){
        if(node == null)
            return;
        Edge edge = new Edge(this, node, weight);
        connections.add(edge);
    }

    @Override
    public int compareTo(Node o) {
        if(this.weight - o.weight == 0)
            return this.name.compareTo(o.name);
        return this.weight - o.weight;
    }

    @Override
    public String toString() {
        return "" + name + ": " + weight;
    }
}

// Edge类无需修改
private static class Edge {
    Node origin;
    Node destiny;
    int weight;

    public Edge(Node origin, Node destiny, int weight) {
        this.origin = origin;
        this.destiny = destiny;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "<" + origin.name + "," + destiny.name + ": " + weight + ">";
    }
}

修改后的算法逻辑：

// 假设你要以sourceNode为源点跑算法，先设置源点权重为0
sourceNode.weight = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(sourceNode); // 不需要一开始把所有节点都塞进去，全塞也不影响逻辑

while(!pq.isEmpty()){
    Node actualNode = pq.poll();
    // 已处理过的节点直接跳过
    if(actualNode.visited) continue;
    actualNode.visited = true;

    // 不可达节点处理
    if(actualNode.weight == Integer.MAX_VALUE) {
        actualNode.weight = -1;
        continue;
    }

    // 松弛逻辑
    for(Edge connection : actualNode.connections) {
        Node dest = connection.destiny;
        if(!dest.visited && dest.weight > actualNode.weight + connection.weight) {
            dest.weight = actualNode.weight + connection.weight;
            dest.parent = actualNode;
            // 更新后直接把节点重新入队
            pq.offer(dest);
        }
    }
}

不推荐的替代方案 #

你也可以在每次更新节点权重时，先调用pq.remove(node)把旧节点从队列删除，再把更新了权重的节点重新入队触发堆调整，但PriorityQueue的remove方法时间复杂度为O(n)，图规模较大时性能会比懒删除方案差很多，不建议使用。

内容的提问来源于stack exchange，提问作者Alejandro Villalobos