I use the code below in a simulation. Because I am calling the dijkstra method over and over, performance is very crucial for me. , I use PriorityQueue to keep the nodes of the graph in an ascending order relative to their distance to the source. PriorityQueue provides me to access the node with smallest distance with O(log n) complexity. However, to keep the nodes in order after recalculating a nodes distance, I need to first remove the node, than add it again. I suppose there may be a better way. I appreciate for ANY feedback. Thanks in advance for all community.
public HashMap<INode, Double> getSingleSourceShortestDistance(INode sourceNode) {
HashMap<INode, Double> distance = new HashMap<>();
PriorityQueue<INode> pq;
// The nodes are stored in a priority queue in which all nodes are sorted
according to their estimated distances.
INode u = null;
INode v = null;
double alt;
Set<INode> nodeset = nodes.keySet();
Iterator<INode> iter = nodeset.iterator();
//Mark all nodes with infinity
while (iter.hasNext()) {
INode node = iter.next();
distance.put(node, Double.POSITIVE_INFINITY);
previous.put(node, null);
}
iter = null;
// Mark the distance[source] as 0
distance.put(sourceNode, 0d);
pq = new PriorityQueue<>(this.network.getNodeCount(), new NodeComparator(distance));
pq.addAll(nodeset);
// Loop while q is empty
while (!pq.isEmpty()) {
// Fetch the node with the smallest estimated distance.
u = pq.peek();
/**
* break the loop if the distance is greater than the max net size.
* That shows that the nodes in the queue can not be reached from
* the source node.
*/
if ((Double.isInfinite(distance.get(u).doubleValue()))) {
break;
}
// Remove the node with the smallest estimated distance.
pq.remove(u);
// Iterate over all nodes (v) which are neighbors of node u
iter = nodes.get(u).keySet().iterator();
while (iter.hasNext()) {
v = (INode) iter.next();
alt = distance.get(u) + nodes.get(u).get(v).getDistance();
if (alt < distance.get(v)) {
distance.put(v, alt);
//To reorder the queue node v is first removed and then inserted.
pq.remove(v);
pq.add(v);
}
}
}
return distance;
}
protected static class NodeComparator<INode> implements Comparator<INode> {
private Map<INode, Number> distances;
protected NodeComparator(Map<INode, Number> distances) {
this.distances = distances;
}
@Override
public int compare(INode node1, INode node2) {
return ((Double) distances.get(node1)).compareTo((Double) distances.get(node2));
}
}