# Graphs - Implementing Dijkstras Algorithm (Shortest Path) in Java

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:

1. Remove the node/distance pair from the head of the priority queue
2. Update the distance in our distances if the distance for that particular node is less then the one in our distances list
3. If the node has not been visited add it to our visited set and then add all of it’s edges (& their distances which is the distance of the node + the edge) to our priority queue (so that they will be visited later on).
4. When the priority queue is empty the distances between the starting node and every other node is contained within the distances list. Unreachable nodes will have a distance of infinity.

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:

``````public class DijkstrasAlgoExample {

}``````

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).

``private static int nodeIndex = 0;``

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:

``````private class Node<U> {

}``````

The node class needs class level variables containing the data, edges, and index.

``````private U data;
private Map<Node<U>, Integer> edges;
private int index = -1;``````

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:

``````public void addEdge(Node<U> node, int weight) {
}``````

Put the node and the weight into our hash map. This will either add a new entry or overwrite a previous entry.

``edges.put(node, weight);``

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.

``````if(!node.getEdges().containsKey(this)) {
}``````

Else if the edge does contain this node then overwrite it if the weight is different.

``````} else {
if(node.getEdges().get(this) != weight) {
}
}``````

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)) {
} else {
if(node.getEdges().get(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)) {