Node comparison using priority queue for Dijkstra's Shortest Path Algorithm

Question

Instead of using a MinHeap that will allow me to change the vertex priorities I am using the Java library PriorityQueue.

Here is how I have implemented the vertices which will generate the vertex array. Also, I have not maintained any separate array for storing the shortest distance to a vertex from source. Instead, I have a class variable will handle that and more importantly allow the priority queue to sort the elements by implementing a different version of compareTo method.

class indivisualvertex implements Comparable<indivisualvertex> {

int data;                                  //data associated with the vertex
double distanceFromSource;                 //will store the distances from the source vertex
int previousVertexOnShortestPathFromSource;//will store the previous vertex on the path
neighbours adjacentPointsList;             // neighbouring vertices stored in a linked list



//for sorting the vertices in the priority queue according to their distances from the source
public int compareTo(indivisualvertex other) {
    if (this.equals(other)) {
        return 0;
    } else if (this.distanceFromSource > other.distanceFromSource) {
        return 1;
    } else {
        return -1;
    }

}
}

Here's also my implementation for the edge relaxation method used after a vertex is chosen from the priority queue. Since there isn't any method to modify the elements inside of a priority queue, the code picks out the desired vertex, changes its distanceFromSource and previousVertexOnShortestPathFromSource variables and then puts it back, sorting the queue in the process.

 private void relax(indivisualvertex indx) {

 //traverse the neighbouring edges 
 for (neighbours nbr = indx.adjacentPointsList; nbr != null; nbr = nbr.next){

        //condition where a vertex is unvisited and also provides a shorter path
        if (visited[nbr.pointer_of_vertex] == false && vertices[nbr.pointer_of_vertex].distanceFromSource > vertices[nbr.from].distanceFromSource + nbr.weight) {
            pq.remove(vertices[nbr.pointer_of_vertex]);
            vertices[nbr.pointer_of_vertex].distanceFromSource = vertices[nbr.from].distanceFromSource + nbr.weight;
            vertices[nbr.pointer_of_vertex].previousVertexOnShortestPathFromSource = nbr.from;
            pq.add(vertices[nbr.pointer_of_vertex]);
        }
    }
}

The implementation works fine. I need to know if there can be any disadvantages to to not building our own minimum heap for this purpose. Also, while relaxing the edges the method extracts the vertex and then puts it back. Is this an expensive operation? How much does it affects the performance of the algorithm?

Answer 1

Stylistic issues

"Indivisual" is not an English word. It seems likely that you mean "individual".

Please use CamelCase with an initial capital letter for class and interface names. It makes your code much easier for others to read. Specifically, indivisualvertex --> IndividualVertex, and neighbours --> Neighbours.

Please use camelCase with an initial lowercase letter for method, field, and parameter names. In particular, pointer_of_vertex --> pointerOfVertex, or, more precisely, vertexIndex.

Class names generally should be singular nouns, for a class always describes one thing, even if that thing is an aggregate.

Descriptive class and variable names are generally good form, but it is possible to go overboard. The name previousVertexOnShortestPathFromSource is considerably too long for my taste, and at the same time a bit inaccurate. I tend to read it as "absurdly long name", which defeats the purpose of descriptive naming. It would be even worse if there were other names of such length to distinguish among. For this particular case, I would certainly choose something more pithy, such as previousVertexIndex.

Where descriptive comments for variables are needed, I generally prefer to see them on the preceding line, not as trailing in-line comments. The latter work for me only if they are quite short. However, do resist adding such comments at all when they add nothing to what your nice, descriptive variable names already say.

It's at minimum unnecessarily verbose to compare boolean variables with boolean literals, such as in the expression visited[nbr.pointer_of_vertex] == false. It is usually better form to just use the boolean variable either directly or subject to boolean negation: !visited[nbr.pointer_of_vertex].

Correctness issues

indivisualvertex.compareTo() is flawed. Given distinct indivisualvertex instaces v1 and v2 with the same values of distanceFromSource, v1.compareTo(v2) and v2.compareTo(v1) will both return -1.

Just because you're comparing floating-point values does not mean that you can ignore the equality case.

Performance considerations

You wrap up your question by raising a series of performance considerations:

can there be any disadvantages to to not building our own minimum heap for this purpose?

Of course there can. You already said yourself that the standard library's PriorityQueue does not offer some of the operations you really would like to have, and therefore that you have to use a workaround. On the other hand, the standard library's PQ has to be very general; all the operations it does implement, it must implement in a generic way. Although I have every reason to expect the result is robust and efficient -- and obviously, it's already there -- it is likely that additional efficiency would be possible from an implementation tuned to your need.

Also, while relaxing the edges the method extracts the vertex and then puts it back. Is this an expensive operation?

It's at least twice as costly as rearranging a min heap appropriately without removing the modified element could be made to be. You've given no basis or context for putting that on absolute grounds.

How much does it affects the performance of the algorithm?

For the overall algorithm, that depends on the data. For a single relaxation, see above.