Answering your question - yes, this is a correct solution (the algorithm is pretty simple), and yes, it is not the most efficient one.
The efficiency depends on the implementation of the priority queue. In your case, I assume this is PriorityQueue
provided in java.util
. The more efficient way uses what is called a Fibonacci Heap. Unfortunately, there is no implementation available in java.util
, but there are plenty of implementations online (like this one). You can test your solution using one of them.
I will also suggest a couple of things you could implement to improve readability of your code.
Naming
In Java, methods should start with a lowercase character, unlike classes. So it is best practice to name your method findShortestPath
.
Also, while frequent in mathematical notation, variable names like u
and v
can be confusing. These are Node
s in your case, so you can name them accordingly: currentNode
, neighbourNode
, or at least just current
and neighbour
.
Formatting
One of your loops contains only one statement, but I would strongly suggest adding brackets anyway or extracting the whole thing to a separate method (see below).
Additionally, consider:
for(Node v:neighbours)
for(Node v : neighbours)
It's a small thing, but most code formatters will do it this way, and it is easier to read.
The same goes for:
Node u=pq.poll();
Node u = pq.poll();
The same applies to mathematical operations, like:
v.getCost() > (u.getCost() + (graph.getCost(u, v))
If you are using an IDE like Eclipse or IntelliJ IDEA, there are features that format your code automatically.
Comments and methods
Comments are good if you are writing complex code that could be hard to understand without them. That's not the case here. Compare:
if(v.getCost()>(u.getCost()+(graph.getCost(u, v)))){ // if there is a cheaper one
// do stuff
}
with
if(thereIsACheaperOne(u,v)){
// do stuff
}
private boolean thereIsACheaperOne(Node u, Node v){
return v.getCost()>(u.getCost()+(graph.getCost(u, v)))
}
When the method names you are using are meaningful, there is no need to comment code - it comments itself. If you extract a lot of statements like this, reading the algorithm becomes really easy. It becomes a short list of easy to understand calls, instead of lots of mathematical operations here and there.
And if you are unsure about what a certain step does, you can just read one specific method body.
A good rule for naming the method could be what I just done - just name the method just like you would phrase the comment.
In general, one method should be doing one thing and one thing only.
pq.remove(v); //remove it
pq.add(v); // add it again
Comments like these are pretty much useless. Anyone with a minimum knowledge about programming will know what this code does. These comments make the code messy.
And more...
In your code, you use graph.getAdj()
twice. Now, what will happen, if something (e.g. another thread) changes the graph
after you added all your nodes, but before you started calculating distances? I suggest that you create a local final variable in your method:
final <WhateverTypeItIs> adjacencyStructure = graph.getAdj()
This way, you are sure that you are working on the same copy of the adjacency structure (be it a list, or matrix) everywhere in your method.
You could also consider adding exception handling to your method instead of checking for source == null
. And why are you only checking source? What happens if graph
is null?
I would separate this into two parts: first, try to get all the variables needed and then call a separate method that is the algorithm itself. All this in a try-catch
block. You could easily catch the NullPointerException
and inform the user that either source
or graph
is not set up properly. Or, better, add a bit more logic to that to ensure which of these is not set up properly.