# Implement Dijkstra's Algorithm in Java

Sheeraz Gul Jan 30, 2023 Apr 01, 2022

When finding the shortest path between two graph nodes, we can implement Dijkstra’s Algorithm, a widely used algorithm. This tutorial describes the procedure of Dijkstra’s Algorithm and demonstrates how to implement it in Java.

## Dijkstra’s Algorithm

Dijkstra’s algorithm can find the shortest path from a source node to all the nodes in a weighted graph. The shortest path can also be found in a source vertex in the graph.

Finding the shortest path through Dijkstra’s algorithm will generate a Shortest Path Tree (SPT) with the root source vertex.

While implementing Dijkstra’s algorithm in Java, we maintain two lists or sets. The first contains all vertices in the Shortest Path tree, and the second has the vertices in the evaluation phase for including in SPT.

We find a vertex from the second list in every iteration, which will have the shortest path. Here is the step-by-step process of Dijkstra’s algorithm:

### Psuedo Code for Dijkstra’s Algorithm

``````Method DIJKSTRA(G, SV)
G-> graph;
SV->starting vertex;
begin
for every vertex VX in G    //initialization; set the initial path to infinite and current node to 0 or null;
Distance[VX] <- infinite
Current[VX] <- NULL
If V != SV, add VX to Priority Queue    // During the first run, this vertex is the source or starting node
Distance[SV] <- 0

while Priority Queue IS NOT EMPTY    // where the neighbor ux has not been extracted  yet from the priority queue
UX <- Extract MIN Neighbor from Priority Queue
for each unvisited adjacent_node  VX of UX
Temporary_Distance <- Distance[UX] + Edge_Weight(UX, VX)
if Temporary_Distance < Distance[VX]    // A distance with lesser weight (shorter path) from ux is found
Distance[VX] <- Temporary_Distance
Current[VX] <- UX    // update the distance of UX
return Distance[], Current[]
end
``````

## Implement Dijkstra’s Algorithm Using Priority Queue in Java

Below is the Java implementation of Dijkstra’s Algorithm using a priority queue:

``````package delftstack;

import java.util.*;

public class Dijkstra_Algorithm {
public static void main(String arg[]) {
int Vertex = 6;
int source_vertex = 0;
//representation of graph will be the adjacency list
List<List<Node> > Node_list = new ArrayList<List<Node> >();
// For every node in the graph Initialize adjacency list
for (int i = 0; i < Vertex; i++) {
List<Node> item = new ArrayList<Node>();
}

//The edges of the graph

// Run the Dijkstra_Algorithm on the graph
Graph_priority_queue gpq = new Graph_priority_queue(Vertex);
gpq.Dijkstra_Algo(Node_list, source_vertex);

// Printing the shortest path from source node to all other the nodes
System.out.println("The shortest paths from source nodes to all other nodes:");
System.out.println("Source_Node\t\t" + "Other_Node#\t\t" + "Path_Distance");
for (int x = 0; x < gpq.distance.length; x++)
System.out.println(source_vertex + " \t\t\t " + x + " \t\t\t "  + gpq.distance[x]);
}
}

class Graph_priority_queue {
int distance[];
Set<Integer> visited_Node;
PriorityQueue<Node> Priority_Queue;
int Vertex; // vertices
List<List<Node> > node_list;
//constructor
public Graph_priority_queue(int Vertex) {
this.Vertex = Vertex;
distance = new int[Vertex];
visited_Node = new HashSet<Integer>();
Priority_Queue = new PriorityQueue<Node>(Vertex, new Node());
}

// Dijkstra's Algorithm implementation
public void Dijkstra_Algo(List<List<Node> > node_list, int source_vertex) {
this.node_list = node_list;

for (int x = 0; x < Vertex; x++) {
distance[x] = Integer.MAX_VALUE;
}
// add the source vertex to the Priority Queue

// Distance of the source from source itself is 0
distance[source_vertex] = 0;
while (visited_Node.size() != Vertex) {

//ux is deleted from the Priority Queue which has minimum distance
int ux = Priority_Queue.remove().dj_node;

// add the ux node to finalized list which is visited
}
}
// process all the neighbors of the just visited node
int Edge_Distance = -1;
int New_Distance = -1;

// process all neighboring nodes of ux
for (int x = 0; x < node_list.get(ux).size(); x++) {
Node vx = node_list.get(ux).get(x);

//  if current node is not in 'visited'
if (!visited_Node.contains(vx.dj_node)) {
Edge_Distance = vx.dj_cost;
New_Distance = distance[ux] + Edge_Distance;

// compare the distances
if (New_Distance < distance[vx.dj_node])
distance[vx.dj_node] = New_Distance;

// Add the current vertex to the PriorityQueue
}
}
}
}

// The Class to handle nodes
class Node implements Comparator<Node> {
public int dj_node;
public int dj_cost;
public Node() { }

public Node(int dj_node, int dj_cost) {
this.dj_node = dj_node;
this.dj_cost = dj_cost;
}
@Override
public int compare(Node dj_node1, Node dj_node2) {
if (dj_node1.dj_cost < dj_node2.dj_cost)
return -1;
if (dj_node1.dj_cost > dj_node2.dj_cost)
return 1;
return 0;
}
}
``````

The code above will give the shortest paths for the given graph using Dijkstra’s algorithm in Java.

Output:

``````The shortest paths from source nodes to all other nodes:
Source_Node    Other_Node#    Path_Distance
0              0              0
0              1              5
0              2              3
0              3              6
0              4              2
0              5              7
``````

## Implement Dijkstra’s Algorithm Using Adjacency Matrix in Java

Here is the Java implementation of Dijkstra’s Algorithm using the Adjacency Matrix:

``````package delftstack;

//Dijkstra's Algorithm using Adjacency matrix  in Java

public class Dijkstra_Algorithm {

public static void dijkstra_algo(int[][] Input_Graph, int source_node) {
int Node_Count = Input_Graph.length;
boolean[] Vertex_Visited = new boolean[Node_Count];
int[] Node_Distance = new int[Node_Count];
for (int x = 0; x < Node_Count; x++) {
Vertex_Visited[x] = false;
Node_Distance[x] = Integer.MAX_VALUE;
}

// Distance of the source node to itself is zero
Node_Distance[source_node] = 0;
for (int x = 0; x < Node_Count; x++) {

// Updating the distance between the source vertex and neighboring vertex
int ux = findMinDistance(Node_Distance, Vertex_Visited);
Vertex_Visited[ux] = true;

// Updating all the neighboring vertices distances
for (int vx = 0; vx < Node_Count; vx++) {
if (!Vertex_Visited[vx] && Input_Graph[ux][vx] != 0 && (Node_Distance[ux] + Input_Graph[ux][vx] < Node_Distance[vx])) {
Node_Distance[vx] = Node_Distance[ux] + Input_Graph[ux][vx];
}
}
}
for (int x = 0; x < Node_Distance.length; x++) {
System.out.println(String.format("Distance from the source node %s to the node %s is %s", source_node, x, Node_Distance[x]));
}
}

// Finding the shortest distance
private static int findMinDistance(int[] Node_Distance, boolean[] Vertex_Visited) {
int Minimum_Distance = Integer.MAX_VALUE;
int Minimum_Distance_Vertex = -1;
for (int x = 0; x < Node_Distance.length; x++) {
if (!Vertex_Visited[x] && Node_Distance[x] < Minimum_Distance) {
Minimum_Distance = Node_Distance[x];
Minimum_Distance_Vertex = x;
}
}
return Minimum_Distance_Vertex;
}

public static void main(String[] args) {
int source_node = 0;
int Input_Graph[][] = new int[][] { { 0, 0, 3, 2, 0, 0, 1 },
{ 0, 0, 2, 0, 4, 1, 0 },
{ 1, 0, 0, 3, 3, 0, 0 },
{ 2, 0, 1, 0, 5, 0, 1 },
{ 0, 0, 0, 4, 0, 2, 3 },
{ 0, 3, 0, 1, 2, 0, 1 },
{ 0, 0, 0, 3, 0, 0, 4 } };
Dijkstra_Algorithm Demo = new Dijkstra_Algorithm();
Demo.dijkstra_algo(Input_Graph, source_node);
}
}
``````

The code above will output the shortest paths for the given graph in the adjacency matrix using Dijkstra’s algorithm in Java.

Output:

``````Distance from the source node 0 to the node 0 is 0
Distance from the source node 0 to the node 1 is 11
Distance from the source node 0 to the node 2 is 3
Distance from the source node 0 to the node 3 is 2
Distance from the source node 0 to the node 4 is 6
Distance from the source node 0 to the node 5 is 8
Distance from the source node 0 to the node 6 is 1
``````

We can use both methods of Dijkstra’s algorithm to calculate the shortest paths for a graph using Java.

Author: Sheeraz Gul

Sheeraz is a Doctorate fellow in Computer Science at Northwestern Polytechnical University, Xian, China. He has 7 years of Software Development experience in AI, Web, Database, and Desktop technologies. He writes tutorials in Java, PHP, Python, GoLang, R, etc., to help beginners learn the field of Computer Science.