Dijkstra的算法-优先级队列问题 [英] Dijkstra's algorithm - priority queue issue

问题描述

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

I have a Graph class with a bunch of nodes, edges, etc. and I'm trying to perform Dijkstra's algorithm. I start off adding all the nodes to a priority queue. Each node has a boolean flag for whether it is already 'known' or not, a reference to the node that comes before it, and an int dist field that stores its length from the source node. After adding all the nodes to the PQ and then flagging the source node appropriately, I've noticed that the wrong node is pulled off the PQ first. It should be that the node with the smallest dist field comes off first (since they are all initialized to a a very high number except for the source, the first node off the PQ should be the source... except it isn't for some reason). Below is my code for the algorithm followed by my compare method within my Node class.

    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问题吗？

Can anyone help me find the issue with my PQ?

推荐答案

优先级队列假设插入元素后顺序不变。

The priority queue uses assumption that order doesn't change after you will insert the element.

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

So instead of inserting all of the elements to priority queue you can:

1. 仅从一个节点开始。

1. Start with just one node.

优先级队列不为空时的循环。

Loop while priority queue is not empty.

如果元素已知，则不执行任何操作。

Do nothing, if element is "known".

每当发现较小的距离时，将其添加到权重为正确的优先级队列。

Whenever you find smaller distance add it to priority queue with "right" weight.

因此，您需要将其他东西存储在优先级队列中，一对：插入时的距离，节点本身。

So you need to store a sth else in priority queue, a pair: distance at insertion time, node itself.

这篇关于Dijkstra的算法-优先级队列问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！