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?
// time complexity: O(n), inside which is an inner loop also labelled// time complexity: O(n), inside which is an operation labelledtime complexity: O(logn(n)). Are you sure that the complexity isn'tO(n^2 log n)? – Peter Taylor Oct 23 '14 at 16:56O(n^2*log(n))complexity. Why do you think it isO(n^2)? – Mephy Oct 23 '14 at 16:56PriorityQueueis a Min Heap implementation, and a Fibonacci Heap may have better results (some methods inPriorityQueueareO(log n)while a Fibonacci Heap would do the same inO(1), likeAdd/Insert). – Mephy Oct 23 '14 at 17:01