**This Tutorial Explains how to Implement the Dijkstra’s algorithm in Java to find the Shortest Routes in a Graph or a Tree with the help of Examples:**

In our earlier tutorial on Graphs in Java, we saw that graphs are used to find the shortest path between the nodes apart from other applications.

To find the shortest path between two nodes of a graph, we mostly employ an algorithm known as “**Dijkstra’s Algorithm**”. This algorithm remains the widely used algorithm to find the shortest routes in a graph or a tree.

**=> Check ALL Java Tutorials Here**

What You Will Learn:

## Dijkstra’s Algorithm In Java

Given a weighted graph and a starting (source) vertex in the graph, Dijkstra’s algorithm is used to find the shortest distance from the source node to all the other nodes in the graph.

As a result of the running Dijkstra’s algorithm on a graph, we obtain the shortest path tree (SPT) with the source vertex as root.

In Dijkstra’s algorithm, we maintain two sets or lists. One contains the vertices that are a part of the shortest-path tree (SPT) and the other contains vertices that are being evaluated to be included in SPT. Hence for every iteration, we find a vertex from the second list that has the shortest path.

The pseudocode for the Dijkstra’s shortest path algorithm is given below.

### Pseudocode

**Given below is the pseudocode for this algorithm.**

procedure dijkstra(G, S) G-> graph; S->starting vertex begin for each vertex V in G //initialization; initial path set to infinite path[V] <- infinite previous[V] <- NULL If V != S, add V to Priority Queue PQueue path [S] <- 0 while PQueue IS NOT EMPTY U <- Extract MIN from PQueue for each unvisited adjacent_node V of U tempDistance <- path [U] + edge_weight(U, V) if tempDistance < path [V] path [V] <- tempDistance previous[V] <- U return path[], previous[] end

**Let’s now take a sample graph and illustrate the Dijkstra’s shortest path algorithm**.

Initially, the SPT (Shortest Path Tree) set is set to infinity.

Let’s start with vertex 0. So to begin with we put the vertex 0 in sptSet.

**sptSet = {0, INF, INF, INF, INF, INF}.**

Next with vertex 0 in sptSet, we will explore its neighbors. Vertices 1 and 2 are two adjacent nodes of 0 with distance 2 and 1 respectively.

In the above figure, we have also updated each adjacent vertex (1 and 2) with their respective distance from source vertex 0. Now we see that vertex 2 has a minimum distance. So next we add vertex 2 to the sptSet. Also, we explore the neighbors of vertex 2.

Now we look for the vertex with minimum distance and those that are not there in spt. We pick vertex 1 with distance 2.

As we see in the above figure, out of all the adjacent nodes of 2, 0, and 1 are already in sptSet so we ignore them. Out of the adjacent nodes 5 and 3, 5 have the least cost. So we add it to the sptSet and explore its adjacent nodes.

In the above figure, we see that except for nodes 3 and 4, all the other nodes are in sptSet. Out of 3 and 4, node 3 has the least cost. So we put it in sptSet.

As shown above, now we have only one vertex left i.e. 4 and its distance from the root node is 16. Finally, we put it in sptSet to get the final sptSet = {0, 2, 1, 5, 3, 4} that gives us the distance of each vertex from the source node 0.

### Implementation Of Dijkstra’s Algorithm In Java

Implementation of Dijkstra’s shortest path algorithm in Java can be achieved using two ways. We can either use priority queues and adjacency list or we can use adjacency matrix and arrays.

**In this section, we will see both the implementations.**

#### Using A Priority Queue

In this implementation, we use the priority queue to store the vertices with the shortest distance. The graph is defined using the adjacency list. A sample program is shown below.

import java.util.*; class Graph_pq { int dist[]; Set<Integer> visited; PriorityQueue<Node> pqueue; int V; // Number of vertices List<List<Node> > adj_list; //class constructor public Graph_pq(int V) { this.V = V; dist = new int[V]; visited = new HashSet<Integer>(); pqueue = new PriorityQueue<Node>(V, new Node()); } // Dijkstra's Algorithm implementation public void algo_dijkstra(List<List<Node> > adj_list, int src_vertex) { this.adj_list = adj_list; for (int i = 0; i < V; i++) dist[i] = Integer.MAX_VALUE; // first add source vertex to PriorityQueue pqueue.add(new Node(src_vertex, 0)); // Distance to the source from itself is 0 dist[src_vertex] = 0; while (visited.size() != V) { // u is removed from PriorityQueue and has min distance int u = pqueue.remove().node; // add node to finalized list (visited) visited.add(u); graph_adjacentNodes(u); } } // this methods processes all neighbours of the just visited node private void graph_adjacentNodes(int u) { int edgeDistance = -1; int newDistance = -1; // process all neighbouring nodes of u for (int i = 0; i < adj_list.get(u).size(); i++) { Node v = adj_list.get(u).get(i); // proceed only if current node is not in 'visited' if (!visited.contains(v.node)) { edgeDistance = v.cost; newDistance = dist[u] + edgeDistance; // compare distances if (newDistance < dist[v.node]) dist[v.node] = newDistance; // Add the current vertex to the PriorityQueue pqueue.add(new Node(v.node, dist[v.node])); } } } } class Main{ public static void main(String arg[]) { int V = 6; int source = 0; // adjacency list representation of graph List<List<Node> > adj_list = new ArrayList<List<Node> >(); // Initialize adjacency list for every node in the graph for (int i = 0; i < V; i++) { List<Node> item = new ArrayList<Node>(); adj_list.add(item); } // Input graph edges adj_list.get(0).add(new Node(1, 5)); adj_list.get(0).add(new Node(2, 3)); adj_list.get(0).add(new Node(3, 2)); adj_list.get(0).add(new Node(4, 3)); adj_list.get(0).add(new Node(5, 3)); adj_list.get(2).add(new Node(1, 2)); adj_list.get(2).add(new Node(3, 3)); // call Dijkstra's algo method Graph_pq dpq = new Graph_pq(V); dpq.algo_dijkstra(adj_list, source); // Print the shortest path from source node to all the nodes System.out.println("The shorted path from source node to other nodes:"); System.out.println("Source\t\t" + "Node#\t\t" + "Distance"); for (int i = 0; i < dpq.dist.length; i++) System.out.println(source + " \t\t " + i + " \t\t " + dpq.dist[i]); } } // Node class class Node implements Comparator<Node> { public int node; public int cost; public Node() { } //empty constructor public Node(int node, int cost) { this.node = node; this.cost = cost; } @Override public int compare(Node node1, Node node2) { if (node1.cost < node2.cost) return -1; if (node1.cost > node2.cost) return 1; return 0; } }

**Output:**

#### Using Adjacency Matrix

In this approach, we use the adjacency matrix to represent the graph. For spt set we use arrays.

**The following program shows this implementation.**

import java.util.*; import java.lang.*; import java.io.*; class Graph_Shortest_Path { static final int num_Vertices = 6; //max number of vertices in graph // find a vertex with minimum distance int minDistance(int path_array[], Boolean sptSet[]) { // Initialize min value int min = Integer.MAX_VALUE, min_index = -1; for (int v = 0; v < num_Vertices; v++) if (sptSet[v] == false && path_array[v] <= min) { min = path_array[v]; min_index = v; } return min_index; } // print the array of distances (path_array) void printMinpath(int path_array[]) { System.out.println("Vertex# \t Minimum Distance from Source"); for (int i = 0; i < num_Vertices; i++) System.out.println(i + " \t\t\t " + path_array[i]); } // Implementation of Dijkstra's algorithm for graph (adjacency matrix) void algo_dijkstra(int graph[][], int src_node) { int path_array[] = new int[num_Vertices]; // The output array. dist[i] will hold // the shortest distance from src to i // spt (shortest path set) contains vertices that have shortest path Boolean sptSet[] = new Boolean[num_Vertices]; // Initially all the distances are INFINITE and stpSet[] is set to false for (int i = 0; i < num_Vertices; i++) { path_array[i] = Integer.MAX_VALUE; sptSet[i] = false; } // Path between vertex and itself is always 0 path_array[src_node] = 0; // now find shortest path for all vertices for (int count = 0; count < num_Vertices - 1; count++) { // call minDistance method to find the vertex with min distance int u = minDistance(path_array, sptSet); // the current vertex u is processed sptSet[u] = true; // process adjacent nodes of the current vertex for (int v = 0; v < num_Vertices; v++) // if vertex v not in sptset then update it if (!sptSet[v] && graph[u][v] != 0 && path_array[u] != Integer.MAX_VALUE && path_array[u] + graph[u][v] < path_array[v]) path_array[v] = path_array[u] + graph[u][v]; } // print the path array printMinpath(path_array); } } class Main{ public static void main(String[] args) { //example graph is given below int graph[][] = new int[][] { { 0, 2, 1, 0, 0, 0}, { 2, 0, 7, 0, 8, 4}, { 1, 7, 0, 7, 0, 3}, { 0, 0, 7, 0, 8, 4}, { 0, 8, 0, 8, 0, 5}, { 0, 4, 3, 4, 5, 0} }; Graph_Shortest_Path g = new Graph_Shortest_Path(); g.algo_dijkstra(graph, 0); } }

**Output:**

### Frequently Asked Questions

**Q #1) Does Dijkstra work for undirected graphs?**

**Answer:** If the graph is directed or undirected does not matter in the case of Dijkstra’s algorithm. This algorithm is concerned only about the vertices in the graph and the weights.

**Q #2) What is the time complexity of Dijkstra’s algorithm?**

**Answer: **Time Complexity of Dijkstra’s Algorithm is O (V 2). When implemented with the min-priority queue, the time complexity of this algorithm comes down to O (V + E l o g V).

**Q #3) Is Dijkstra a greedy algorithm?**

**Answer: **Yes, Dijkstra is a greedy algorithm. Similar to Prim’s algorithm of finding the minimum spanning tree (MST) these algorithms also start from a root vertex and always chooses the most optimal vertex with the minimum path.

**Q #4) Is Dijkstra DFS or BFS?**

**Answer: **It is neither. But as Dijkstra’s algorithm uses a priority queue for its implementation, it can be viewed as close to BFS.

**Q #5) Where is the Dijkstra algorithm used?**

**Answer: **It is used mostly in routing protocols as it helps to find the shortest path from one node to another node.

## Conclusion

In this tutorial, we have discussed the Dijkstra’s algorithm. We use this algorithm to find the shortest path from the root node to the other nodes in the graph or a tree.

We usually implement Dijkstra’s algorithm using a Priority queue as we have to find the minimum path. We can also implement this algorithm using the adjacency matrix. We have discussed both these approaches in this tutorial.

We hope you will find this tutorial helpful.