CODEWITHSUNDEEP
javaalgorithmsortingpriority-queuedijkstra
Sunny Xu
Sunny Xu

Reputation: 31

How do I implement PriorityQueue for Dijkstra's algorithm?

I have a question regarding implementing priority queue for Dijkstra's algorithm, because this is a hw so I couldn't create another class, so I'm trying to find a way to add nodes(integer)in priority queue but I want the queue to sort the weight inside the node, but not the node itself.

For example,I have 3 nodes(0,1,2) and node 0 has a weight of 10, node 1 has 15, and node 2 has 5.

Queue<Integer> queue = new PriorityQueue<Integer>();
queue.add(0);
queue.add(1);
queue.add(2);

while(!queue.isEmpty()){
    System.out.println(queue.poll());
}

This should give me a output of 2,0,1. Is this possible without creating another class? Or is there a different approach I could use besides priority queue?

Thanks in advance!!!!!! any help would be much appreciated!

One solution I could think of is sorting a normal queue every time I add a node into it, so if I have node 2,0,1 in the queue and I want to add node 3 which has a weight of 8, I would need to compare the weight with the top element of queue until it fits into the queue, so it would be 2,3,0,1 in queue, but this is kindda inefficient tho.

Upvotes: 1

Views: 637

Answers (1)

Malt
Malt

Reputation: 30295

You have two options:

  1. Create your own Node class, and make it implement the Comparable<Node> interface. The class will have a weight attribute, and it could compare Nodes based on their weight. This will create a natural ordering of Nodes that PriorityQueue will use.

  2. Create the priority queue with the PriorityQueue(Comparator<? super E> comparator) constructor. It takes a comparison function (Comparator) for comparing two items. You can therefore have that function compare using the node's weights (which don't have to be kept in the same queue - the might be calculated dynamically or be kept in some separate data structure).

Upvotes: 1

Related Questions