Dijkstras algorithm is an algorithm used to find the shortest path between two nodes in a weighted graph. It works by first initializing a list of distances between each node and the initial node. Each distance is initially set to infinity. We also need a set of nodes to keep track of which nodes have been visited. It is initially empty, but later filled in as each node is visited. A priority queue (AKA min heap) is also needed for the implementation. After running the algorithm the shortest distance to each node in the graph will be contained in the distances list.
The priority queue will contain pairs of Nodes and Integers. This pair represents a Node and it’s distance from the start node. To begin with the starting node and it’s distance from the start node (0) is added to the priority queue. While the priority queue is not empty we will do the following:
The use of the priority queue is vital to Dijkstra’s algorithm. It ensures that the node being visited is the closest unvisited node to the start node.
Let’s start implementing Dijkstra’s Algorithm with a class definition:
We need a class level variable (an integer to be precise) to keep track of the current nodeIndex in our graph to allow us to assign each Node it’s own unique ID. This integer needs to be declared private and static to prevent tampering with. This unique ID setup will work for our purposes, but has limitations (ie can only be as big as what can be held in a 32-bit integer).
Now that we’ve declared our nodeIndex variable let’s go ahead and declare a class to represent a node in our graph. This class needs to contain the data associated with each node, the index of the node, and a map containing the nodes linked to the current node as well as their distance (ie the edges). The class declaration looks as follows:
The node class needs class level variables containing the data, edges, and index.
By declaring the edges as a map of nodes to integers it allows us to store the weight for each edge with the node. Add getters and setters for the data, index, and edges.
public U getData() {
return data;
}
public void setData(U data) {
this.data = data;
}
public Map<Node<U>, Integer> getEdges() {
return edges;
}
public void setEdges(Map<Node<U>, Integer> edges) {
this.edges = edges;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}Ok so the next thing to do is to write a constructor for our Node class. This constructor needs will take in the data as an input. It needs to set the data, initialize the edges map, set the index to the nodeIndex, and increment the nodeIndex (so that each index for each node is unique).
The constructor is as follows:
public Node(U data) {
this.data = data;
edges = new HashMap<Node<U>, Integer>();
this.index = nodeIndex;
nodeIndex += 1;
}Note that this will result in a unique index each time (as long as the number of nodes remains less then capacity of an integer) as the nodeIndex variable is declared static. It’s time now to add a function that adds an edge to our node. This will input a node as well as an integer weight. Since we are making an undirected graph it will add the edge to our current node as well as the node contained in the edge.
The function definition looks as follows:
Put the node and the weight into our hash map. This will either add a new entry or overwrite a previous entry.
Next add code to ensure that the edge node contains an edge to this node with the same weight as our graph is bidirectional. If the edges node doesn’t contain this node then simply add it.
Else if the edge does contain this node then overwrite it if the weight is different.
The finished function is as follows:
/**
* Add an undirected edge, will replace an already existing edge between the two nodes
*/
public void addEdge(Node<U> node, int weight) {
edges.put(node, weight);
if(!node.getEdges().containsKey(this)) {
node.addEdge(this, weight);
} else {
if(node.getEdges().get(this) != weight) {
node.addEdge(this, weight);
}
}
}The finished node class is as follows:
private class Node<U> {
private U data;
private Map<Node<U>, Integer> edges;
private int index = -1;
public Node(U data) {
this.data = data;
edges = new HashMap<Node<U>, Integer>();
this.index = nodeIndex;
nodeIndex += 1;
}
public U getData() {
return data;
}
public void setData(U data) {
this.data = data;
}
public Map<Node<U>, Integer> getEdges() {
return edges;
}
public void setEdges(Map<Node<U>, Integer> edges) {
this.edges = edges;
}
public int getIndex() {
return index;
}
public void setIndex(int index) {
this.index = index;
}
/**
* Add an undirected edge, will replace an already existing edge between the two nodes
*/
public void addEdge(Node<U> node, int weight) {
edges.put(node, weight);
if(!node.getEdges().containsKey(this)) {
node.addEdge(this, weight);
} else {
if(node.getEdges().get(this) != weight) {
node.addEdge(this, weight);
}
}
}
}With the node class completed that makes a great spot to wrap this post up. The implementation of Dijkstra’s algorithm will be continued in the following post: Implementing Dijkstras Algorithm (Shortest Path) in Java - Part Two.