5
\$\begingroup\$

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<Node> {

private final char label;
private int distanceFromSource;
private final Map<Node, Integer> 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<Node, Integer> 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<Node> 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<Node> nodePriority, int noOfVertices) {

    Set<Node> MST = new LinkedHashSet<>();
    while (MST.size() < noOfVertices) { // time complexity: O(n)  


        Node minNode = nodePriority.poll();
        MST.add(minNode);

        /* list of nodes to be updated in nodePriority after iteration finishes. */
        List<Node> nodesToAdd = new ArrayList<>();
        Iterator<Node> 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.getDistanceFromSource() + minNode.getNeighbourerList().get(node);
                if (node.getDistanceFromSource() > adjacentNodeDistanceFromSource) {

                    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))
                }
            }
        }
        nodePriority.addAll(nodesToAdd); // all updated nodes added to priority Queue.
    }
    /* display final shortest distances for all vertices from source */
    for (Node node : MST) {
        System.out.println(node.getLabel() + " : " + node.getDistanceFromSource());
    }
}

I think the time complexity is \$O(n^2)\$. How can we improve on it?

\$\endgroup\$
  • \$\begingroup\$ You have an outer loop labelled // time complexity: O(n), inside which is an inner loop also labelled // time complexity: O(n), inside which is an operation labelled time complexity: O(logn(n)). Are you sure that the complexity isn't O(n^2 log n)? \$\endgroup\$ – Peter Taylor Oct 23 '14 at 16:56
  • \$\begingroup\$ The code looks like and is commented as a O(n^2*log(n)) complexity. Why do you think it is O(n^2)? \$\endgroup\$ – Mephy Oct 23 '14 at 16:56
  • \$\begingroup\$ If I'm not mistaken, Java's PriorityQueue is a Min Heap implementation, and a Fibonacci Heap may have better results (some methods in PriorityQueue are O(log n) while a Fibonacci Heap would do the same in O(1), like Add/Insert). \$\endgroup\$ – Mephy Oct 23 '14 at 17:01
  • \$\begingroup\$ @PeterTaylor I know it is O(n^2*logn(n)), but log(n) is not as bad as O(n^2). So changing O(n^2) to O(n) complexity is what I would like to achieve first. \$\endgroup\$ – Meena Chaudhary Oct 23 '14 at 17:46
3
\$\begingroup\$

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<Node, Integer> 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<Node, Integer> 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<Node> 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<Node, Integer> findShortestDistances(Node start, Set<Node> destinations)

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

Set<Node> 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<Node> nodesToAdd = new ArrayList<>();
Iterator<Node> 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<Node> 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<Node, Integer> 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.

\$\endgroup\$
  • \$\begingroup\$ It appears to me this will throw the "'to' node unreachable" exception every time. The priority queue is never populated before the loop begins. \$\endgroup\$ – nclark Mar 9 '17 at 16:25
  • \$\begingroup\$ @nclark Yup, you're totally right. There should have been a toVisit.add(from); right after toVisit. \$\endgroup\$ – raptortech97 Mar 10 '17 at 16:17
  • \$\begingroup\$ @nclark Thanks for pointing that out, just edited my post to fix this. \$\endgroup\$ – raptortech97 Mar 10 '17 at 16:25
3
\$\begingroup\$

I would add a few notes to raptortech97:

The duplicated nodes on a priority queue would violate the invariant of priority queue. Java PriorityQueue is an implementation of min-heap, and the invariant on a min-heap node is "parent is smaller than its children."

Consider the following test:

Proof of duplicate node problem:

class Node {
    int value;

    public Node(int value) {
        this.value = value;
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[6];
    PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(o -> o.value));
    for (int i=0; i<6; i++){
        nodes[i] = new Node(i+10);
        pq.add(nodes[i]);
    }
    // pq contains 10, 11, 12, 13, 14, 15
    nodes[3].value -= 10;
    // value 13 decreased to 3
    pq.add(nodes[3]); // and re-added to the priority queue.
    // pq contains two 3 instances, and 10, 11, 12, 14, 15.
    // The second 3 is not that important
    // we will ignore when we poll the second 3. 

    // add other values, larger than 3 and smaller than others.
    pq.add(new Node(7));
    pq.add(new Node(8));
    pq.add(new Node(16));
    // now we have two 3 instances, 10, 11, 12, 14, 15, 7, 8, and 16. 

    // We poll 3 times. We expect to pick 3, 7 and 8. 
    // The second 3 may appear or not, we do not care. 
    System.out.println(pq.poll().value);
    System.out.println(pq.poll().value);
    System.out.println(pq.poll().value);
}

We expect an output of 3, 7 and 8. However, the result is 3, 10, 8!!! That violates the Dijkstra algorithm. We expect that 7 appears before 10 and 8. What is the problem? The problem is re-used nodes of a priority queue.

To remedy the problem, we can recreate the Node during updates. However, we cannot just recreate Node instances because Node instances are referenced from other Node instances to describe edges. As pointed by @raptortech97, Node itself holds the data for graph, edges, along with the Dijkstra algorithm related data. If we separate graph related data and algorithm related data, we have a better design, and also resolve the "recreate problem".

Result:

public static int shortestPathDijkstra(Node source, Node target) {
    Map<Node, MyDijkstraNode> result = new HashMap<>(); // can be an array if vertices are integer-indexed. 
    PriorityQueue<MyDijkstraNode> pq = new PriorityQueue<>(Comparator.comparingInt(MyDijkstraNode::getMinCost));

    MyDijkstraNode resultSource = new MyDijkstraNode(source);
    resultSource.setPre(null);
    resultSource.setMinCost(0);
    pq.add(resultSource);
    result.put(source, resultSource);

    Set<Node> btdt = new HashSet<>(); // can be a boolean array if vertices are integer-indexed.
    while (!pq.isEmpty()) {
        MyDijkstraNode uNode = pq.poll();
        Node u = uNode.getU();
        if (btdt.contains(u)) {
            continue;
        }
        btdt.add(u);
        Map<Node, Integer> edges = u.getNeighbours();
        for (Map.Entry<Node, Integer> e : edges.entrySet()) {
            Node v = e.getKey();
            int w = e.getValue();
            if (btdt.contains(v)) {
                continue;
            }
            MyDijkstraNode existingNode = result.get(v);
            if (existingNode == null || existingNode.getMinCost() > uNode.getMinCost() + w) {
                MyDijkstraNode newNode = new MyDijkstraNode(v);
                newNode.setMinCost(uNode.getMinCost() + w);
                newNode.setPre(uNode);
                pq.add(newNode);
                result.put(v, existingNode);
            }
        }
    }
    MyDijkstraNode targetDijkstraNode = result.get(target);
    if (targetDijkstraNode==null){
        throw new RuntimeException("no path found");
    }
    return targetDijkstraNode.getMinCost(); 
    // or return targetDijkstraNode to get full path. 
    // or return result to get all shortest paths to all other vertices from single source.  
}

class Node {
    private final char label;
    private final Map<Node, Integer> neighbours;

    public Node(char label) {
        this.label = label;
        neighbours = new HashMap<>();
    }

    public void addNeighbour(Node node, int distance) {
        neighbours.put(node, distance);
    }

    public char getLabel() {
        return label;
    }

    public Map<Node, Integer> getNeighbours() {
        return neighbours;
    }
}

class MyDijkstraNode {
    private Node u;
    private int minCost;
    private MyDijkstraNode pre;

    public MyDijkstraNode(Node u) {
        this.u = u;
    }

    public Node getU() {
        return u;
    }

    public int getMinCost() {
        return minCost;
    }

    public MyDijkstraNode getPre() {
        return pre;
    }

    public void setPre(MyDijkstraNode pre) {
        this.pre = pre;
    }

    public void setMinCost(int minCost) {
        this.minCost = minCost;
    }
}
\$\endgroup\$
1
\$\begingroup\$
        Node node = nodePriorityIterator.next();
        if (minNode.getNeighbourerList().containsKey(node)) { // time complexity: O(log(n))

            int adjacentNodeDistanceFromSource = minNode.getDistanceFromSource() + minNode.getNeighbourerList().get(node);

"Please go to the warehouse and check if we have X, thanks!"
(some time passes)
"Yes, we have X."
"Okay, please go fetch it for me."
(some more time passes)
"Here it is."

You're wasting time by waiting for it.

Integer neighborDistance = minNode.getNeighbourerList().get(node);
if(neighborDistance != null){
    int adjacentNodeDistanceFromSource = minNode.getDistanceFromSource() + neighborDistance;

That saves you this double check.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.