Dijkstra's algorithm

Question

Assuming everything else works as expected, is the following a correct - but not the most efficient way - of implementing Dijkstra algorithm? Because I have tested it on several examples and it gives correct result. But I can't imagine Dijkstra is that simple.

  public static void FindShortestPath(Node source, Directed graph)
    {
        if(source==null)
        {
            System.err.println("Source doesn't exist.");
            System.exit(0);
        }
       source.setCost(0); // all nodes are initialized with cost=Double.Max_VALUE when first created.
       PriorityQueue<Node> pq=new PriorityQueue<>(); // Node implements comparable according to cost
       for(Node node:graph.getAdj().keySet()) // get all nodes 
          pq.add(node); 
        while(!pq.isEmpty()) 
        {
            Node u=pq.poll(); // the minimum
            List<Node> neighbours=graph.getAdj().get(u); // get the minimum direct successors
            for(Node v:neighbours) 
            { 
                if(v.getCost()>(u.getCost()+(graph.getCost(u, v)))) // if there is a cheaper one
                {
                    v.setCost(u.getCost()+graph.getCost(u, v)); // change its cost
                    pq.remove(v);  //remove it
                    pq.add(v);  // add it again
                } 
            }
        }    
    }

Answer 1

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 Nodes 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.