PriorityQueue not working

Question

I'm trying to implement Dijkstra algorithm on my own in java. I have a min-priority queue that stores nodes ordered by their current shortest path.

The first step goes smoothly, I set starting node with distance 0 and others with Integer.MAX_VALUE. The starting node was polled out correctly. However, after i removed the first node, the second node that been removed is not the node with smallest distance. I cant figure out why. Any opinions?

Here is my code

public void Dijkstra(Node s){
    initialize(s);
    List<Node> set = new ArrayList<Node>();
    Comparator<Node> c = new CompareNode();
    PriorityQueue<Node> Q = new PriorityQueue<Node>(V,c);
    for (Node q: Nodes){
        Q.add(q);
    }
    while (Q.size()!=0){
        Node u = Q.remove();
        System.out.println();
        System.out.println(u + " is removed with dis " + u.getD());
        set.add(u);
        for (Node w: u.getWeightedAdj().keySet()){
            relax(u,w);
        }
    }
}

public void initialize(Node s){
    for (Node v: Nodes){
        v.setD(Integer.MAX_VALUE);
        v.setPredecessor(null);
    }
    s.setD(0);
}

public void relax(Node u, Node w){
    if (w.getD()>u.getD()+u.getWeightedAdj().get(w)){
        w.setD(u.getD()+u.getWeightedAdj().get(w));
        w.setPredecessor(u);
    }
}

And comparator class

import java.util.Comparator;

public class CompareNode implements Comparator<Node> {

@Override
public int compare(Node o1, Node o2) {
    if (o1.getD()>o2.getD())
        return 1;
    if (o1.getD()<o2.getD())
        return -1;
    return 0;
    }
}

when I ran it, the outcome looks like this

A is removed with dis 0

E is removed with dis 2147483647

C is removed with dis 2

D is removed with dis -2147483648

B is removed with dis 3

Note that your code is missing the change priority step. Change priority isn't automatic in java priority queues. And it doesn't provide a change priority method. Please see linked question for more — e4c5, May 04 '17 at 12:44

score 0 · Accepted Answer · answered May 04 '17 at 12:41

The problem is that the PriorityQueue orders the elements when they are added with the assumption that the order cannot change.

In your example all your distances are MaxInt when the nodes are added to the queue (except for the start node), and so they are placed into the queue in effectively a random order.

You then adjust the distances, but the PriorityQueue does not know about these adjustments so continues to return the elements in the original order.

The standard approach to this is to insert elements in the priority queue when the distance changes. (When an element is removed from the queue, you need to test whether you have already visited this element because the same element can appear multiple times in the queue.)

Thanks! I've been working on this for hours before I figure out the priority does't change.. — Linrong, May 04 '17 at 14:22

score 0 · Answer 2 · answered May 04 '17 at 12:49

It would be easier to add the nodes to the queue as they get discovered. I.e. in the beginning only add the root node, and then in each iteration add the newly discovered nodes that haven't been processed. In the iteration step you need to check if new nodes are in the queue or not and possibly update them if the new distance is shorter.

PriorityQueue not working

2 Answers2