Dijkstra's Algorithm in Java

Dijkstra's Algorithm is a popular algorithm used when working with graphs. This algorithm finds the shortest distance from a source vertex to all other vertices of a weighted graph.

In this tutorial, we will learn the working of this algorithm and implement it in Java.

Dijkstra's Algorithm

As discussed above, Dijkstra's algorithm is used to solve the shortest-path problem for a weighted graph. At each iteration, the algorithm finds the node that is closest to the current node. It then explores this closest node and repeats the above step. We need to maintain a list of distances to each node. This will help us in determining the next node to explore.

The algorithm chooses the most optimal path at each iteration without worrying about what lies further, so it is classified as a Greedy Algorithm. The following steps explain the working of the algorithm.

• We first create a distance array to store the distances from the source to the vertices. We also create a visited array to indicate whether we have finalized the shortest distance for a node or not.
• Next, we will create a loop that will run as long as we have not found the shortest distance for each node.
• Inside the loop, we will find the closest node whose shortest distance has not been computed yet. The node should not be present in the visited array.
• Next, we will explore all the adjacent neighbors of this node. If we can reach a node via this closest node and travel less amount of distance, then we will update the shortest distance for that node. Basically, we will update the shortest distance of a node X if:

(current shortest distance from source to the current closest node) + (distance from the current closest node to node X) < (current shortest distance from source to node X)

Let's try to understand the algorithm with the help of an example. We will work on the graph shown below. We will create a distance array and initialize each element(except the source) to infinity. Vertices are named from 0 to 5. It will make it easier to update the distance array using indices.

We will add the distance to each neighbor of the current node(0 in this step) to the array. Now we choose the closest unvisited node from the distance array. So node 3 is chosen. The shortest distance for node 3 has been finalized.

Next, we will update the distance array for all the neighbors of node 3. We will only update the distance if we can reach a node by traveling less distance. Now the closest node for which distance has been finalized is node 4. The shortest distance for node 4 has been finalized.

Now, from node 4, we can reach node 1 by traveling less distance. So we will update the distance array value for node 1. The next closest unsettled node is node 5.

From node 5, we cannot reach any node by traveling a lesser distance. So no distance value will be updated in this step. Node 1 is chosen as the next closest node.

From node 1, the only node whose distance can be updated is node 2. The next closest node will also be node 2. Now, all the nodes have been visited and the shortest distance has been settled for all of them. The loop will terminate.

The final shortest-distance array is [0, 27, 34, 18, 21, 25].

The drawback of Dijkstra's Algorithm

A major drawback of Dijkstra's algorithm is that it cannot handle negative edge weights. This happens because Dijkstra's algorithm uses a greedy approach. Whenever the closest node is chosen from the distance array, we mark that node's distance as finalized. We won't ever update that node's distance. This works perfectly fine for positive weights but may give inconsistent solutions for negative edge weights.

For example, consider the following directed and weighted graph with a negative edge weight.

Let's consider vertex A as the source. In the first iteration, the distance for B and C is updated. Since C is the closest node, we will mark that node's shortest finalized distance as 5. From C, we cannot reach any other node. Next node B will be chosen as the closest, and the distance for this node is also marked as final. All nodes have been visited and the shortest distance has been finalized, so the algorithm ends. But we can reach node C via node B by traveling a shorter distance(-6). But Dijkstra's algorithm says that the shortest distance from A to C is 5.

Dijkstra's Algorithm Implementation

Let's first take a look at our Graph class. It has a 2-D adjacency matrix, and an integer variable used to store the number of vertices. It also has an addEdge() method. We are using a directed graph for our implementation, and so two cells of the adjacency matrix will be updated when adding an edge.

class Graph
{
	int[][] adjMatrix;
	int numOfvertices;
	
	Graph(int[][] mat, int v)
	{
		this.adjMatrix = mat;
		this.numOfvertices = v;
	}
	
	void addEdge(int src, int dest, int edgeWeight)
	{
		adjMatrix[src][dest] = edgeWeight;
		adjMatrix[dest][src] = edgeWeight;
	}
}

Let's implement Dijkstra's algorithm in Java. We will use a helper method called getClosestVertex() to find the closest unvisited node. The code for this method is shown below.

public static int getClosestVertex(int[] distance, boolean[] visited)
{
	int min = Integer.MAX_VALUE;
	int minIdx = -1;
	for(int i=0; i<distance.length; i++)
	{
		if(distance[i] < min)
			if(visited[i] == false)
			{
				min = distance[i];
				minIdx = i;
			}
	}
	return minIdx;
}

Next, we will implement the main algorithm in a dijkstrasShortestPath() method. This method will take a Graph and a source vertex as parameters. It will return a shortest-distance array.

public static int[] dijkstrasShortestPath(Graph g, int src)
{
	//final shortest distance array
	int[] distance = new int[g.numOfvertices];
	//array to tell whether shortest distance of vertex has been found
	boolean[] visited = new boolean[g.numOfvertices];
		
	//initializing the arrays
	for(int i=0; i<g.numOfvertices; i++)
	{
		distance[i] = Integer.MAX_VALUE;//initial distance is infinite
		visited[i] = false;//shortest distance for any node has not been found yet
	}
	distance[src] = 0;
		
	for(int i=0; i<g.numOfvertices; i++)
	{
		int closestVertex = getClosestVertex(distance, visited);//get the closest node
		//if closest node is infinite distance away, it means that no other node can be reached. So 
        return
		if(closestVertex == Integer.MAX_VALUE)
			return distance;
			
		visited[closestVertex] = true;
		for(int j=0; j<g.numOfvertices; j++)
		{
			if(visited[j] == false)//shortest distance of the node j should not have been finalized
			{
				if(g.adjMatrix[closestVertex][j] != 0)
				{
					int d = distance[closestVertex] + g.adjMatrix[closestVertex][j];
					if(d < distance[j])//distance via closestVertex is less than the initial distance
						distance[j] = d;
				}
			}		
		}
	}
	return distance;
}

Let's check whether our code gives the expected results.

import java.util.Arrays;

public static void main(String[] args)
{
	int numOfVertices = 6;
	int[][] adjMat = new int[6][6];
	Graph graph = new Graph(adjMat, numOfVertices);
	graph.addEdge(0, 4, 21);
    graph.addEdge(0, 3, 18);
    graph.addEdge(2, 1, 7);
    graph.addEdge(1, 4, 6);
    graph.addEdge(4, 5, 10);
    graph.addEdge(4, 3, 11);
    graph.addEdge(5, 3, 7);
    int[] dist = dijkstrasShortestPath(graph, 0);
	System.out.print(Arrays.toString(dist));
}

[0, 27, 34, 18, 21, 25]

Space and Time Complexity

For each iteration, we are calculating the distance from the closest node to all the remaining nodes. This leads to the time complexity of O(V^2), where V is the number of vertices.

We are also maintaining two arrays(distance and visited) so an additional space equal to the number of vertices is required. The space complexity for the above implementation is O(V).

Summary

Dijkstra's algorithm is used to find the shortest distance between the nodes of a graph. We can use this algorithm for both directed and undirected graphs, but it won't work with negative edge weights. We can further optimize our implementation by using a min-heap or a priority queue to find the closest node.