Implementation of Dijkstra algorithm using Java

By Abhishek Birendra Verma

In this tutorial, we will learn about the Dijkstra algorithm and we will also see the program to implement the Dijkstra algorithm using Java.

So before proceeding towards the code, Let us first understand the Dijkstra algorithm. Dijkstra algorithm solves the single-source shortest path problem. However, the algorithm works only on a directed and positively weighted graph. Positively weighted graph means where weights of all edges are non-negative i.e G=(V, E) is a positively weighted graph then w( u, v) ≥ 0. Dijkstra's algorithm is a greedy algorithm.

For a given graph G=(V, E) and a source vertex s, it maintains a set S of vertices. Initially, no vertex is in S. For a vertex u ϵ V - S, (i.e for a vertex which is in V but is not in S) if it has the minimum shortest distance from source s to u then u is added to S. This process is continued till V - S is not equal to null.

Please note that here in the code visited[] array does the work of set S i.e it keeps track of the vertices that have been visited and we also ask for the destination to print the shortest path between source and destination.

This is  the graph that we have taken as an example for the code given below

import java.util.Scanner;

public class Dijkstra { 
  
  public static int V ; 
  //this function is used to find the minimum distance of a node from the source which is not visited yet
  public int Find_min_dist(int distance[], boolean[] visited) 
  { 
    
    int min = 9999, index = -1; 

    for (int v = 0; v < V; v++) 
      if (visited[v] == false && distance[v] <= min) { 
        min = distance[v]; 
        index = v; 
      } 

    return index; 
  } 
  //Here the distance is printed from the source vertex  to each vertex in the graph
  public void printSolution(int distance[]) 
  { 
    System.out.println("Vertex \t\t Distance from Source"); 
    for (int i = 0; i < V; i++) 
      System.out.println(+(i+1) + " \t\t " + distance[i]); 
  } 
  
  Dijkstra(int adj[][], int src,int end) 
  { 
    int distance[] = new int[V]; 
    boolean visited[] = new boolean[V]; 
    

    
    for (int i = 0; i < V; i++) { 
      distance[i] = 9999; 
      visited[i] = false; 
    } 

     
    distance[src] = 0; 
    for (int i = 0; i < V - 1; i++) { 
      
      int u = Find_min_dist(distance, visited); 
      visited[u] = true;
      //if previous minimum distance from src to v is greater than distance[u] + adj[u][v] then distance[v] is updated
      for (int v = 0; v < V; v++) 
        if (visited[v]==false && adj[u][v] != 0 && distance[u] != 9999 && distance[u] + adj[u][v] < distance[v]) 
          distance[v] = distance[u] + adj[u][v]; 
    } 

    printSolution(distance);
    findpath(distance,adj,end,src);
  } 
  // findpath() is used to print the shortest path from source to the destination
  public void findpath(int distance[], int adj[][],int destination,int src)
  {
    int path[]=new int[V];
    //path[] is used as a queue in which all the nodes which are a part of the shortest path are inserted
    boolean visited[] = new boolean[V]; 
    int index=-1,i=0,min=9999,j,count=0;
    path[0]=destination;
    //here declaring visited[i] for all vertices as false to backtrack from destination to src to get the shortest path
    for(i=0;i<V;i++)
      visited[i]=false;
    
    for(i=0;i<V;i++)
    {
      min=9999;
      for( j=0;j<V;j++)
      {// Here backtrack from destination to src and adding all the nodes to path[] which are a part of the shortest path 
        if(adj[destination][j]!=0&&visited[j]==false&&adj[destination][j]+distance[j]<min)
        {
          index=j;
          min=adj[destination][j]+distance[j];
          visited[j]=true;
        }
        
      }
      path[i+1]=index;
      destination=index;
      count++;
      if(destination==src)
        break;
    }
    System.out.println("The path from Source to Destination is:");
    for(i=count;i>0;i--)
    {
        System.out.print(path[i]+1);
        System.out.print("-->");	
      
    }
    System.out.print(path[i]+1);
    
  }
  
  public static void main(String[] args) 
  { 
    Scanner sc=new Scanner(System.in);
    
    
    System.out.print("Enter the total no. of vertices:");
    V=sc.nextInt();
    int adj[][] = new int[V][V];
    //Asking the user for the adjacency matrix
    System.out.println("Enter the adjacency matrix for "+V+" vertices");
    for(int i=0;i<V;i++)
    
    {
      for(int j=0;j<V;j++)
      {
        System.out.print("Enter Adj["+(i+1)+"]["+(j+1)+"]:");
        adj[i][j]=sc.nextInt();
      }
    }
     System.out.println("Enter the Source node:");
     int src=sc.nextInt()-1;
     System.out.println("Enter the Destination node:");
     int end=sc.nextInt()-1;
    Dijkstra obj = new Dijkstra(adj, src,end); 
    sc.close();
    
  } 
} 

 

 

Output:

1)                                                                                               2)