Dijkstra’s Algorithm:
In the priority queue implemented (PriorityQueue queue = new PriorityQueue<>(
Comparator.comparingInt(ne -> ne.priority))
, how does the comparingInt function place a node with minimum weight. Does it sort the entire array?
When I tested with the graph similar to the one used in the Dijkstra’s video, it just swapped the front of the queue element with the minimum weight element. (e.g. if the queue has [B, C] and then D is visited and the minimum distance is updated in distances hash table for D then when adding to queue, the queue becomes [D, C, B]). Please explain this and inner working of a priority queue in depth. Thanks!
@Mosh @SAM
Are you asking about how PriorityQueue is implemented? Most likely using a heap. The comparingInt method tells the heap how to decide which item is at the top of the heap.