java - Dijkstra的算法-优先级队列问题

我有一个带有一堆节点，边等的Graph类，并且我正在尝试执行Dijkstra的算法。我开始将所有节点添加到优先级队列。每个节点都有一个布尔标志，用于指示它是否已经“已知”，对之前节点的引用以及一个int dist字段，该字段存储其距源节点的长度。在将所有节点添加到PQ，然后适当地标记源节点之后，我注意到错误的节点首先从PQ中拉出。应该是具有最小dist字段的节点首先脱落（因为除了源以外，它们都被初始化为一个非常高的数字，所以PQ之外的第一个节点应该是来源...除了不是某些节点）原因）。
以下是我的算法代码，其后是Node类中的compare方法。

    public void dijkstra() throws IOException {
    buildGraph_u();
    PriorityQueue<Node> pq = new PriorityQueue<>(200, new Node());

    for (int y = 0; y < input.size(); y++) {
        Node v = input.get(array.get(y));
        v.dist = 99999;
        v.known = false;
        v.prnode = null;
        pq.add(v);
    }

    source.dist = 0;
    source.known = true;
    source.prnode = null;
    int c=1;
    while(c != input.size()) {
        Node v = pq.remove();
        //System.out.println(v.name);
                    //^ Prints a node that isn't the source
        v.known = true;
        c++;
        List<Edge> listOfEdges = getAdjacent(v);
        for (int x = 0; x < listOfEdges.size(); x++) {
            Edge edge = listOfEdges.get(x);
            Node w = edge.to;
            if (!w.known) {
                int cvw = edge.weight;
                if (v.dist + cvw < w.dist) {
                    w.dist = v.dist + cvw;
                    w.prnode = v;
                }
            }
        }
    }
}

public int compare (Node d1, Node d2) {
       int dist1 = d1.dist;
       int dist2 = d2.dist;
       if (dist1 > dist2)
         return 1;
       else if (dist1 < dist2)
         return -1;
       else
         return 0;
     }

谁能帮助我找到我的PQ问题？

最佳答案

优先级队列使用以下假设：插入元素后顺序不会改变。

因此，除了将所有元素插入优先级队列之外，您还可以：


从一个节点开始。
优先级队列不为空时循环。
如果element为“已知”，则不执行任何操作。
每当发现较小的距离时，将其添加到权重为“正确”的优先级队列中。
因此，您需要将其他东西存储在优先级队列中，一对：插入时的距离，节点本身。

关于java - Dijkstra的算法-优先级队列问题，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/13594699/