Dijkstra's Algorithm Java

Shortest Path Problem with Dijkstra's Algorithm Java

Before diving into what Dijkstra's algorithm is, we'll understand the meaning of the shortest path.

Shortest path

Consider you want to travel from city A to city B. There are various routes that you can take to reach your destination. Each road connecting two cities has a weight equal to the distance between the two cities. To cover the distance from city A to city B in the shortest time possible, obviously you will choose the shortest route. The same principle is used in Dijkstra's algorithm.

Shortest Path Problem

While dealing with graph theory, you will come across problems where the keywords like 'shortest path', 'shortest distance', and 'shortest route'. If you encounter any of these keywords and the given graph has non-negative edge weights, directed and weighted edges, here Dijkstra's algorithm can be applied.

How Dijkstra's Algorithm Works?

Dijkstra's algorithm is used to find the shortest route between the source and the destination. It uses the greedy approach where the shortest path is chosen. The algorithm keeps track of the currently known shortest distance from each node to the source node and it updates these values if it finds a shorter path.

Also, it works on the principle of relaxation. Here, more accurate values gradually replace an approximation to the correct distance until the shortest distance is reached. It uses a priority queue to store the closest vertex that has not been processed yet and performs relaxation on its outgoing edges.

Dijkstra Algorithm Steps

Let us comprehend the steps involved in Dijkstra Algorithm Java.

1. First we create an array to mark the visited and the unvisited nodes.
2. All the nodes should be marked as unvisited at the start.
3. We create another array to store the distance between the source to the vertices. All the nodes except the starting node should be initialized with infinity and the starting node should be initialized with 0.
4. Then we start from the source vertex. Let the current vertex be u and the adjacent vertex be v.
5. For the current vertex u, traverse all adjacent vertices v. If v has not been visited, update its distance if it is smaller than the current distance of v.
6. Then we select the next vertex with the least distance that has not been visited.
7. Repeat steps 5-6 until all nodes have been visited or the destination has been reached.

Dijkstra Algorithm Pseudocode

We have implemented the same steps in the form of pseudocode.

Implementation of Dijkstra’s Algorithm in Java

There are various ways in which we can implement Dijkstra’s Algorithm in Java.

a) Using a Priority Queue

We will write a code using a priority queue where we will display the shortest path along with the edges that were visited.

We first create a Pair class which has the source node, the neighbor node, and the weight. We have initialized its constructor. We have then implemented the Comparable interface and the weight will be compared.

Output:

Explanation:

• We first create a Pair class which has the source node, the neighbor node, and the weight. We have initialized its constructor.
• We have then implemented the Comparable interface and the weight will be compared.
• In the main function, we create a graph and then add the edges accordingly.
• We create a boolean array visited which tracks whether the vertex has been visited or not. We create a priority queue of the
• Add the source node in the priority queue. Then while the queue is not empty, now we keep removing one edge and add the adjacent edges if they have not been visited and mark them as visited.
• As we are using a priority queue, the edge with a lesser value will be popped. The adjacent edges are added and the steps are repeated till all nodes are covered.

b) Using Adjacency Matrix

In this method, an adjacency matrix is created, and the getVertex() function is used to get the closest unvisited node. The dijkstra() function is used to return the shortest distance array.

Output:

Explanation:

• This implementation assumes that the input graph is represented as an adjacency matrix, where graph[i][j] stores the weight of the edge from vertex i to vertex j. A weight of 0 represents no edge between the two vertices.
• The Main class is defined with a private static final variable INF initialized to Integer.MAX_VALUE, which is used to represent infinite distance.
• The dijkstra() method is defined, which takes two arguments - a 2D array graph representing the adjacency matrix of the graph, and an integer source representing the source vertex.
• The size of the graph is obtained by getting the length of the first dimension of the adjacency matrix using the length method.
• Two arrays are created to keep track of the shortest distances and visited nodes. The dist array stores the shortest distance from the source to each vertex, and the visited array keeps track of whether a vertex has been visited or not.
• The dist array is initialized with infinity using the Arrays.fill method, and the distance of the source vertex is set to 0.
• The algorithm runs for n-1 iterations, where n is the number of vertices in the graph. In each iteration, the vertex with the minimum distance that has not been visited is selected.
• The minDistance() method is called to find the vertex with the minimum distance. This method loops through all the vertices and returns the index of the vertex with the minimum distance that has not been visited yet.
• The selected vertex is marked as visited by setting the corresponding element of the visited array to true.
• For each adjacent vertex v of the selected vertex u, the algorithm checks if it has not been visited, if there is an edge between u and v, and if the distance from the source to u plus the weight of the edge from u to v is less than the current distance from the source to v. If all of these conditions are satisfied, the distance from the source to v is updated to the new, shorter distance.
• After all the adjacent vertices have been processed, the algorithm selects the next vertex with the minimum distance that has not been visited.
• Finally, the printDistances() method is called to print the shortest distances from the source to all the vertices.
• The main() method creates an example graph represented as an adjacency matrix, and calls the dijkstra method to find the shortest distances from the source vertex 0 to all the other vertices.

c) Backtrace - Find the Complete Path

In order to find the complete path, we follow the predecessors step by step. Consider the following graph

To find the route from A to D, first, we have to perform the method called backtrace using predecessors. In the above example, the predecessor of D is C, the predecessor of C is B and the predecessor of B is A. So the shortest path is A-->B->C->D.

d) Shortest Path to All Nodes

If we continue until the table contains only a single entry, we have found the shortest paths to all nodes. When our table of the nodes contains only one node after removing all of them, the shortest path of all the neighbors has already been found. Hence we have found the shortest path to all the nodes.

Dijkstra's Algorithm Complexity

The Dijkstra algorithm has a time complexity of $O(V^2)$ using the adjacency matrix representation of the graph. The time complexity can be reduced to O((V+E)logV) using the adjacency list representation of the graph or priority queue, where E is the number of edges in the graph and V is the number of vertices in the graph.

Limitations of the Dijkstra Algorithm

• We have already discussed that Dijkstra's algorithm works for non-negative, directed and weighted graphs. If the edge weight is negative, the algorithm won’t work.
• Since Dijkstra follows a Greedy Approach, once a node is marked as visited it cannot be reconsidered even if there is another path with less cost or distance. This issue persists only if there exists a negative edge weight in the graph.
• To find the shortest path in a graph having negative edge weight, an alternative Bellman-Ford algorithm is used to find the shortest distance as it stops the loop when it encounters a negative cycle.

Dijkstra's Algorithm Applications

• Used in applications where the shortest route has to be found.
• It is used in IP protocol routing. The open shortest path first is a link-state routing protocol. It is used to find the shortest path between the start and end router.
• To designate a file server in RAM. To minimize the number of hops from one server to another computer, the Dijkstra algorithm is used.
• Used in telephone networks.