Problems with Dijkstra's algorithm using PriorityQueue and adjacency list (java)

Competitive programming, which I started thinking of practicing programming, becomes a regular practice.

What i learned

--How to use Priority Queue --How to use the Comparator interface --How to use the Cloneable interface

Problems with the above and their solutions.

What I wanted to do

I tried to solve ALDS shortest path tree problem C. Dijkstra's algorithm using an adjacency list.

For example, given a test case like the one in the image below, each node outputs the shortest distance to reach from node 0. 0 is the distance 0, 1 is the distance 1, 3 is the distance 5, and so on.

procedure

Initialize 0 as a searched node at a distance of 0. A loop that searches for the nearest unsearched node from the searched node group. If one unsearched node is already searched, the shortest distance of the node adjacent to it can change. Therefore, the search is performed while updating the distance of each node. In the case of an image, the search has been completed in the order of 0 → 1 → 2 → 5 → 4 → 3 → 6 → 7 → 8, for example, 3 is updated as distance 13 (after 0 search) → 5 (after 4 search). ..

Define the Node class with the following properties

class Node{ int id; //Node number int d=INFTY; //Shortest distance from node 0 ← Find while updating this int color=0; //Initial value 0,If searched 1 TreeMap<Integer,Integer> child =new TreeMap<>(); //{id:Side weight}List of adjacent nodes in format }

 1. Define the following variables in the main () method
 --`queue`: Priority queue that stores Node objects in d order ** (Trouble 1) **
 --`nodes []`: Array to store each node in the latest state
 1. Set the distance of 0 to 0 (`nodes [0] .d = 0;`) and put it in the priority queue. Currently `queue` contains only 0 nodes.



 1. Select by ʻu = queue.poll () `. Make u searched and update if the `d` of the adjacent node can be updated. ** (Trouble 2) **
 In the case of the image, the first time is updated as follows.

    ```
nodes[1].d=1;
nodes[3].d=13;

Put an adjacent node (unsearched) in the priority queue. At this point, the first time, the references to nodes [i](i = 1,3) are arranged in the queue in ascending order of d.
Extract the node with the smaller d from the queue and select it. After that, repeat steps 4 to 6. ** (Trouble 3) **

Why did you get in trouble?

-(Trouble 1) I wasn't good at putting objects in the Priority Queue and got a warning (it worked locally but I got a compile error in an online judge) -(Trouble 2) Priority Queue can contain multiple data that refer to the same object -** (Trouble 3) Priority Queue does not reconstruct the order even if the reference destination is updated (= the order is out of order) **

↓ Details

I wasn't good at putting objects in the Priority Queue and got a warning (it worked locally but I got a compile error in an online judge)

The following is correct. This will put Node at the beginning of the queue in ascending order of d.

class MyComparator implements Comparator<Node>{
    @Override
    public int compare (Node n1, Node n2) {
        int d1 = n1.d;
        int d2 = n2.d;

        if (d1 > d2) {
            return 1;
        } else if (d1 < d2) {
            return -1;
        } else{
            return 0;
        }
    }
}
//Below main()In the method
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

I didn't know the lambda expression until a while ago, so when I searched for a traditional interface implementation, I failed because there were many sites that did not use generics as shown below.

class MyComparator implements Comparator {
    public int compare (Object o1, Object o2){//processing}
}//Below main()In the method
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

/*Local warning that Object → Node type conversion is not safe
    Type safety: The expression of type PriorityQueue needs unchecked conversion to conform to Queue<Node>
Firm compilation error in AOJ
    rep/Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
*/

openjdk version "11.0.3" 2019-04-16

Priority Queue can contain multiple data that refer to the same object

Not surprisingly, this caused a large number of the same objects to be queued. In the middle

nodes[1].d=1
nodes[3].d=13;
queue.add(nodes[1]);
queue.add(nodes[3]);

However, it is updated as nodes [3] .d = 5; after that. I also queued this and tried to queue two types of data: {id = 3, d = 5}, {id = 3, d = 13}. However, since the two data in the queue refer to the same object nodes [3], only two data with a distance of 5 with id3 can be entered. The solution itself is easy, and if a node with the same id exists in the queue, it should not be newly added. But it's dirty (I looked up the queue id in the for statement). However, there was the following problem and this was no good after all. What should I do if a property that is not used for sort is queued?

Priority Queue does not reconstruct the order even if the reference destination is updated (= the order is out of order)

Even if (Trouble 2) is solved, it will be a wrong answer because of this.

nodes[2].d=2;
nodes[3].d=3;
queue.add(nodes[2]);
queue.add(nodes[3]);
queue.peek();       //If you look at the top without taking it out, nodes[2]
nodes[3].d=1;
queue.peek();       //This is also nodes[2]

(Since the position of node 3 (currently d = 5) in the queue is the position sorted by d = 13, the node selection after selecting node 4 is 2 of 3 and 7 (position of d = 8). 7 is taken out of the queue by selection) ** In other words, the standard Priority Queue cannot be handled while updating the properties inside. ** **

Solved as follows.

nodes [] only manages the latest version (latest distance), and stores in the queue as the object itself, not as a reference.
Since multiple versions of node management (queue both {id = 3, d = 5} and {id = 3, d = 13}) that could not be realized in (Trouble 2) are realized. , If ʻud> nodes [id] `is selected as u from the queue, it will be ignored.

At that time, I tried using ʻObject.clone (), so make a note about it. Objects can be replicated in classes that implement the Cloneable interface and override the clone () method. clone ()has a deep copy (the object members in the object to be copied are also copied) and a shallow copy (the object members in the object to be copied are the same as the original), and the following is a shallow copy (this time deep is required) Since there is no). TheTreeMap` object refers to the same object for all objects, but this time it is not updated, so there is no problem.

class Node implements Cloneable{
    int id;
    int d;
    int color=0;
    TreeMap<Integer,Integer> child = new TreeMap<>();  //{id:weight}Adjacency list

    @Override
    protected Node clone() throws CloneNotSupportedException {
    Node  node = (Node)super.clone();
    return node;
}//Below main()In the method
try{
    queue.add(nodes[0].clone());
} catch (CloneNotSupportedException e){//Error handling}

For deep copy, add node.child = this.child.clone (); when overriding clone ().

Summary

The java standard Priority Queue is generally out of order when updating the objects inside. If you want to Dijkstra, duplicate the object with clone () and put all the objects before update in the priority queue, and skip the process when you take out the object other than the latest state.