How to Implement Dijkstra's Algorithm in Java

Sheeraz Gul Feb 02, 2024

Java Java Algorithm

Dijkstra’s Algorithm
Implement Dijkstra’s Algorithm Using Priority Queue in Java
Implement Dijkstra’s Algorithm Using Adjacency Matrix in Java

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:

First of all, mark all the nodes in the graph as unvisited.
Now, initialize the starting node with zero; all the other nodes with infinity mean the biggest number.
Make starting node the current node.
This current node will now be used to analyze all its unvisited neighbor nodes then calculate the distance by adding the weight of the edge, which will develop the connection between the current and neighbor nodes.
Compare the distance which is recently calculated and the distance allotted to the neighbor node; this will be treated as the current distance of the neighboring node.
Now, consider the surrounding nodes of the current node which have not been visited yet and mark the current node as visited.
This process is repeated till the end node is marked as visited, which means Dijkstra’s algorithm has finished its task. And if the end node is not marked as visited yet, then:
Select the unvisited node with the shortest path, and it will be the new current node. Then repeat the process from step 4.

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>();
      Node_list.add(item);
    }

    // The edges of the graph
    Node_list.get(0).add(new Node(1, 5));
    Node_list.get(0).add(new Node(4, 2));
    Node_list.get(0).add(new Node(2, 3));
    Node_list.get(1).add(new Node(5, 2));
    Node_list.get(1).add(new Node(4, 3));
    Node_list.get(2).add(new Node(3, 3));
    Node_list.get(2).add(new Node(4, 2));

    // 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
    Priority_Queue.add(new Node(source_vertex, 0));

    // 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
      visited_Node.add(ux);
      Adjacent_Nodes_Graph(ux);
    }
  }
  // process all the neighbors of the just visited node
  private void Adjacent_Nodes_Graph(int ux) {
    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
        Priority_Queue.add(new Node(vx.dj_node, distance[vx.dj_node]));
      }
    }
  }
}

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

LinkedIn Facebook

Dijkstra’s Algorithm

First of all, mark all the nodes in the graph as unvisited.

Now, initialize the starting node with zero; all the other nodes with infinity mean the biggest number.

Make starting node the current node.

This current node will now be used to analyze all its unvisited neighbor nodes then calculate the distance by adding the weight of the edge, which will develop the connection between the current and neighbor nodes.

Compare the distance which is recently calculated and the distance allotted to the neighbor node; this will be treated as the current distance of the neighboring node.

Now, consider the surrounding nodes of the current node which have not been visited yet and mark the current node as visited.

This process is repeated till the end node is marked as visited, which means Dijkstra’s algorithm has finished its task. And if the end node is not marked as visited yet, then:

Select the unvisited node with the shortest path, and it will be the new current node. Then repeat the process from step 4.

Psuedo Code for Dijkstra’s Algorithm

Implement Dijkstra’s Algorithm Using Priority Queue in Java

Implement Dijkstra’s Algorithm Using Adjacency Matrix in Java

Related Article - Java Algorithm