// The algorithm itself is quite clear.
public void calculate(final Node source, final Node drain) {
init(source);
Node node;
while (! prioQueue.isEmpty()) { // will hold all nodes in order of shortest distance
node = prioQueue.remove(); // next "nearest" node is to be checked
if(node == drain) {
extractPath(node, source); // build shortest path
break;
}
visitedNodes.add(u); // another node is seen
handleNode(u); // check the edges that leave that node
}
}
// All edges of a node are checked to produce a shorter path from source.
private void handleNode(Node u) {
for (final Node node : getNeighbourNodes(u)) {
if (! visitedNodes.contains(node)) {
if (minDistances.get(node) > minDistances.get(u) + edgeOfNodes(u, node).getWeight()) {
minDistances.put(node, minDistances.get(u) + edgeOfNodes(u, node).getWeight());
predecessors.put(node, u);
prioQueue.offer(node);
}
}
}
}
// The path is found and now its components are added to the list of nodes.
// Note that the list is in reversed order.
private void extractPath(final Node drain, final Node source) {
Node node1 = drain;
Node node2 = source;
while (predecessors.get(node1) != null) {
nodesList.add(node1);
node2 = predecessors.get(node1);
edgeList.add(graphModel.getEdgeOfNodes(node1, node2));
node1 = node2;
}
nodesList.add(source);
Collections.reverse(nodesList); // reverse the "wrong" order
}
// All distances except for first node to itself are set to infinity.
private void init(final Node start) {
for (final Node node : getAllNodesOfGraph()) {
minDistances.put(node, Double.POSITIVE_INFINITY);
}
minDistances.put(start, 0.0);
prioQueue.add(start);
}
|