Now that the node class is finished we can get back to implementing Dijkstras Algorithm. First off we will need a class level variable to hold the nodes in the graph. We will declare this as a map between integers to nodes. The key of the map (integer) refers to the index of the node.
Next we need to define a class that implements a comparator for pairs of nodes and integers. We need to do this so that we can use a priority queue of pairs of nodes and integers in our shortest path implementation. We need to have them order from smallest integer to largest integer. The integer in this pairing refers to the distance from the start node. The implementation of this is as follows:
private class EdgePairComparator implements Comparator<Pair<Node<Integer>, Integer>> {
@Override
public int compare(Pair<Node<Integer>, Integer> o1, Pair<Node<Integer>, Integer> o2) {
return o1.getValue().compareTo(o2.getValue());
}
}Now we can begin to write our shortest path function. It will input the starting node and ending node and return an integer containing the length of the shortest path between the two nodes. The function definition is as follows:
First we’ll declare a map of integer to integer called distances which will contain the distance to each node. The key of this map will be the index of the node and the value will be the distance to that node from the start node. We’ll initialize the distance of each node to be equal to Integer.MAX_VALUE as infinity isn’t an option for each node in our graph.
Map<Integer, Integer> distances = new HashMap<>();
for(Node<Integer> n : graph.values())
distances.put(n.getIndex(), Integer.MAX_VALUE);Declare a set of integer’s called visited. This set will keep track of which nodes have been visited. It is initially empty. As a node is visited it will be added to the set.
Declare a priority queue containing pairs of nodes and integers. It needs to be declared with the EdgePairComparator we defined earlier. This priority queue will contain the nodes and the distance of that node from the start node. The item at the front of the queue will by definition be the node with the shortest distance. This property is vital to Dijkstra’s algorithm.
Initially load the queue with the start node by declaring a new Pair containing the start node as well as the distance from the start node (0 as it is the start node). Add this startPair to the queue that was just declared.
Next we’ll iterate through the queue removing nodes off of it one at a time and visiting them (updating our distances map in the process). As each node is visited make sure to add it to the queue so that it also can be visited (if it has not already been visited). When the queue is finally empty the algorithm has finished processing. Start off by declaring a while loop that runs as long as the queue is not empty:
Remove the first pair from the queue. Get the weight, node, and nodeIndex from the pair. The weight represents the distance that node is from the start node.
Pair<Node<Integer>, Integer> pair = queue.remove();
Node<Integer> node = pair.getKey();
Integer weight = pair.getValue();
int nodeIndex = node.getIndex();If the weight is less then the distance in our distances map then update the distance to the correct value.
Next we need to add all of the edges in the currently visited node (if the currently visited node has not been visited) to the priority queue with a distance of the current weight + the weight of the edge. First make sure the node has not already been visited:
Add the node index to the visited set to mark of the node so that it isn’t visited again.
Get the edges for the currently visited node:
Loop through the all of the nodes in the edges:
Finally get the weight of the edge, create a new edgePair containing the edgeNode and the current distance for the pair (ie the weight + the edgeWeight), and add the pair to the queue so that we can visit it.
int edgeWeight = edges.get(edgeNode);
Pair<Node<Integer>, Integer> edgePair = new Pair<>(edgeNode, weight+edgeWeight);
queue.add(edgePair);Finally after the while loop has been processed, we need to return the distance between the start node and the end node at the end of the function. This distance will be contained in the distances map filled in in the while loop. If the node is unreachable then the distance will be equal to Integer.MAX_VALUE.
The finished getShortestPath() function is as follows:
public int getShortestPath(Node<Integer> start, Node<Integer> end) {
//keeps track of the distance between this node and every other node
Map<Integer, Integer> distances = new HashMap<>();
for(Node<Integer> n : graph.values())
distances.put(n.getIndex(), Integer.MAX_VALUE);
//keeps track of which nodes we have visited
Set<Integer> visited = new HashSet<Integer>();
//declare a priority queue which will be used to help find the shortest path to each node
PriorityQueue<Pair<Node<Integer>, Integer>> queue = new PriorityQueue<>(new EdgePairComparator());
//initially load the priority queue with the start node (as that is where we start!!!)
Pair<Node<Integer>, Integer> startPair = new Pair<>(start, 0);
queue.add(startPair);
//when the queue is empty we will have found the shortest distance from the start node to all other nodes
while(!queue.isEmpty()) {
//the pair at the front of the queue will be the current node to visit
Pair<Node<Integer>, Integer> pair = queue.remove();
Node<Integer> node = pair.getKey();
Integer weight = pair.getValue();
int nodeIndex = node.getIndex();
if(weight < distances.get(nodeIndex)) {
//if a shorter path has been found then update the distance
distances.put(nodeIndex, weight);
}
//visit all the adjacent nodes to the node currently being visited
if(!visited.contains(nodeIndex)) {
visited.add(nodeIndex); //mark off this node so that we don't have to visit it again
Map<Node<Integer>, Integer> edges = node.getEdges();
for(Node<Integer> edgeNode : edges.keySet()) {
int edgeWeight = edges.get(edgeNode);
Pair<Node<Integer>, Integer> edgePair = new Pair<>(edgeNode, weight+edgeWeight);
queue.add(edgePair);
}
}
}
return distances.get(end.getIndex());
}That concludes the writing of the getShortestPath() function. In the following post we will wrap up the implementation of Dijkstras Algorithm: Implementing Dijkstras Algorithm (Shortest Path) in Java - Part Three.