using java priorityQueue remove method

Question

I was looking for dijkstra algorithm with java.

Below code works normally.

public static void computePaths(Vertex source, Subway p, int broken)
    {
        //set the source vertex distance to 0 (as distance source->source=0)
        source.minDistance=0;
        //init queue , add source to keep track of nodes visited (cloud)
        PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>();
        vertexQueue.add(source);

        //keep track of total vertices tracked so as not to go in circles
        List<Integer> l=new LinkedList<Integer>();

    // while the cloud is not empty
    while (!vertexQueue.isEmpty()) {
        // take the head as u and...
        Vertex u = vertexQueue.poll();
        //(add position of u to the tracking list)
        l.add(new Integer(u.pos));


            // ...Visit each edge exiting u
            Iterator<Edge> it=(p.subwayNetwork.getEdges(u.pos)).iterator();
            while (it.hasNext())
            {

                Edge e= it.next();
                Vertex v = e.dest;
                Double weight = e.weight;
                // calculate the distance from u to the node v
                Double distanceThroughU = u.minDistance + weight;

                // if the distance is less then the min. distance, and not already visited, and  neither
                // the vertice and edge are broken
                if (distanceThroughU < v.minDistance && !l.contains(v.pos) && v.pos!=broken && !e.broken) {
                    //remove the node form the queue and update the distance and prev. value
                    vertexQueue.remove(v);
                    //update the distance
                    v.minDistance=distanceThroughU;
                    //update the path visited till now 
                    v.previous = u;
                    //reenter the node with the new distance
                    vertexQueue.add(v);

                }
            }

        }
    }

why that vertexQueue.remove(v); occurs no error?

since we init the queue, we add something then poll.

so queue might be empty.

I thought remove operation occurs NoSuchElementException error.

but it operates normally.

and advice would be appreciated

ptrckdev · Accepted Answer · 2018-06-12 09:17:26Z

1

The remove()-method has bool as its return value. It returns "true" if the queue changed as a result of the call, otherwise, it returns "false", but no exception!

Source: https://docs.oracle.com/javase/7/docs/api/java/util/PriorityQueue.html#remove(java.lang.Object)

answered Jun 12, 2018 at 9:17

ptrckdev

4134 silver badges9 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

jwkoo Over a year ago

you answered almost correct but it produces exception. when the queue is empty and call remove, than NoSuchElementException occurs. but if I remove something with params. it return false when the queue has no such thing. thanks anyway.

ptrckdev Over a year ago

just tested it and a remove()-call on an empty queue returns false since the element does not exist. That's expected behavior IMO. Edit: oh I see what you mean yes, when the queue is empty calling vertexQueue.remove() will return the exception, if you give the method an object it will return false. those two remove methods are completely different and I didn't think about the later one because in your code you used the remove(Object) method

jwkoo Over a year ago

maybe my question confused you. appreciate for helping me!

Collectives™ on Stack Overflow

using java priorityQueue remove method

1 Answer 1

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related