Optimizing Dijkstra implementation using PriorityQueue in Java

I am trying to make Dijkstra implementation more efficient. Below is the code for class Node which implements Comparable so it can be used in PriorityQueue.

public class Node implements Comparable {

private final char label;
private int distanceFromSource;
private final Map neighbourList;

public Node(char label, int distanceFromSource) {
    this.label = label;
    this.distanceFromSource = distanceFromSource;
    this.neighbourList = new LinkedHashMap<>();
}

public void addNeighbourer(Node node, int distance) {
    neighbourList.put(node, distance);
}

public char getLabel() {
    return label;
}

public Map getNeighbourerList() {
    return neighbourList;
}

public int getDistanceFromSource() {
    return distanceFromSource;
}

public void setDistanceFromSource(int distanceFromSource) {
    this.distanceFromSource = distanceFromSource;
}

@Override
public int compareTo(Node o) {
    return Integer.compare(this.getDistanceFromSource(), o.getDistanceFromSource());
}

}

Adding Node to PriorityQueue and calling the Dijkstra method to find shortest distances:

PriorityQueue nodePriority = new PriorityQueue<>();
    nodePriority.add(nodeA);
    nodePriority.add(nodeB);
    nodePriority.add(nodeC);
    nodePriority.add(nodeD);
    nodePriority.add(nodeE);
    nodePriority.add(nodeF);
    Dijkistra dijkistra = new Dijkistra();
    dijkistra.findShortestDistances(nodePriority, 6);

Below is the algorithm for Dijkstra:

```
public void findShortestDistances(PriorityQueue nodePriority, int noOfVertices) {

Set MST = new LinkedHashSet<>();
while (MST.size() nodesToAdd = new ArrayList<>();
Iterator nodePriorityIterator = nodePriority.iterator();
while (nodePriorityIterator.hasNext()) { // time complexity: O(n)

Node node = nodePriorityIterator.next();
if (minNode.getNeighbourerList().containsKey(node)) { // time complexity: O(log(n))

int adjacentNodeDistanceFromSource = minNode.ge

This works, but there's definitely room for improvement.

Node class

A Node has a distanceFromSource, which means it's tied to the dijkstra algorithm, and the nodes can't be reused in other runs of the algorithm. This is not great and results in a relatively awkward interface, but we'll leave it for now.

private final char label;
private int distanceFromSource;
private final Map neighbourList;

You made label and neighbourList final, and I always love to see that! label should probably be a String, though, to make it a little more usable. (If you want to go the extra mile, you could use generics, which will make it a lot easier for any library that wants to use it.) Also, I don't see why the distances need to be integer; Dijkstra's algorithm doesn't require it, and it might be a pretty limiting factor in some applications. Also, distanceFromSource should probably be tentativeDistanceFromSource. The Node should also have a boolean visited set initially to false.

this.neighbourList = new LinkedHashMap<>();

Nice use of the diamond, but why does neighborList need to be a LinkedHashMap? We really don't care about the order of neighborList at all, so it could just be a HashMap.

public void addNeighbourer(Node node, int distance)
public Map getNeighbourerList()

It might just be me, but misspellings bug the hell out of me. The word you're looking for is neighbour (neighbor in the US).

Algorithm

public void findShortestDistances(PriorityQueue nodePriority, int noOfVertices) {

This raises a lot of questions. Why isn't this static? The Dijkstra class seems to be empty except for this, so it should be fine being static. Why don't I get the shortest distances back? If I'm using this program, I probably want the result to be returned. If I want to print it to the console, I can do that myself. Why should I have to give you a PriorityQueue to start with, instead of just a starting node? What is noOfVertices, and why do I have to supply it? As a consumer of this program, I probably want a function signature that looks more like

public static int findShortestDistance(Node start, Node final)

or, if I want to find the distances to multiple nodes at the same time, it might look like

public static Map findShortestDistances(Node start, Set destinations)

where the returned map will have all the elements of destinations as its keys.

Set MST = new LinkedHashSet<>();

What's MST? Why does it need to be a LinkedHashSet instead of just a HashSet? Luckily we can actually get rid of MST by changing the signature.

// list of nodes to be updated in nodePriority after iteration finishes.
List nodesToAdd = new ArrayList<>();
Iterator nodePriorityIterator = nodePriority.iterator();
while (nodePriorityIterator.hasNext()) {  // time complexity: O(n)
    Node node = nodePriorityIterator.next();
    if (minNode.getNeighbourerList().containsKey(node)) { // time complexity: O(log(n))
        //...
    }
}
nodePriority.addAll(nodesToAdd); // all updated nodes added to priority Queue.

This is a major issue. You should not be iterating through all the other nodes in the list and testing if the other node is in this node's neighbor list. (Also, that's O(1), not O(n), to check if a key exists in a hashmap.) Instead, iterate through the neighborList, possibly testing to see if the node is visited yet.

Node updatedCopy = node; // original node copied.
    updatedCopy.setDistanceFromSource(adjacentNodeDistanceFromSource); // node copy updated with new value.
    nodesToAdd.add(updatedCopy); // updated node added to list.
    nodePriorityIterator.remove();  // time complexity: O(logn(n))

Whoa! Node updatedCopy = node; does not copy the node! Java passes objects by pointer! Luckily, this still works. Also, removing the node isn't quite necessary.

Result

public static int findShortestDistance(Node from, Node to) {
    Queue toVisit = new PriorityQueue<>();
    toVisit.add(from); // We have to populate the queue at the start. Thanks to nclark for pointing this out to me.

    while (!toVisit.isEmpty()) {
        Node min = toVisit.remove();
        if (min == to) {
            return min.getDistanceFromSource();
        }
        if (min.isVisited()) {
            continue;
        }
        min.setVisited(true);
        for (Map.Entry neighborEntry : min.getNeighborList().entrySet()) {
            int adjacentDistance = min.getDistanceFromSource() + neighborEntry.getValue();
            Node neighbor = neighborEntry.getKey();
            if (neighbor.getDistanceFromSource > adjacentDistance && !neighbor.isVisited()) {
                neighbor.setDistanceFromSource(adjacentDistance);
                toVisit.add(neighbor);
            }
        }
    }

    throw new RuntimeException("'to' node unreachable");
}

Nodes will be duplicated in the queue, but that's not that bad.

StackExchange Code Review Q#67704, answer score: 4