Java Program to Implement Dijkstra's Shortest Path Algorithm

Simple Java Program code to find the shortest path from single source using Dijkstra's Single Source Shortest Path Algorithm .It is similar to Prim's algorithm but we are calculating the shortest path from just a single source to all other remaining vertices using Matrix.In this Java Program first we input the number of nodes and cost matrix weights for the graph ,then we input the source vertex . After that we get the distance matrix using Calc() method . Finally we print the distance matrix which has shortest distance from source vertex.

Also Read : How to Create Patch in Google Summer of Coding

Take an Example for the Image below , We have four vertices a , b , c , d with their Cost weights are given in their edges.Source vertex is : Vertex 'a' which is marked.

First we write the Cost matrix as :

1 2 3 4
1 i 3 i 7
2 3 i 4 2
3 i 4 i 5
4 7 2 5 i

Index position starts from 1 and ends at 4 . ( 1 to 4) and i stands for infinity or 999.We know that start or source vertex is 'a' or 1.So the distance array from 'a' to all other remaining vertices will be i , 3 , i , 7 .

First we find the smallest element and its position in the distance array i , 3 , i , 7 which will be 3 and using the position of smallest element 3 we find the other shortest possible available paths . So the distance matrix will updated to i , 3 , 7 , 7 . We repeat this same process to get remaining shortest paths available .

Java Program Code :


import java.util.*;
public class Dijkstra
{
 public  int distance[] = new int[10];
 public  int cost[][] = new int[10][10];
 
 public void calc(int n,int s)
 {
  int flag[] = new int[n+1];
  int i,minpos=1,k,c,minimum;
  
  for(i=1;i<=n;i++)
  {  
      flag[i]=0; 
      this.distance[i]=this.cost[s][i]; 
  }
  c=2;
  while(c<=n)
  {
   minimum=99;
   for(k=1;k<=n;k++)
   { 
          if(this.distance[k]<minimum && flag[k]!=1)
       {
        minimum=this.distance[i];
        minpos=k;
       }
      } 
            flag[minpos]=1;
      c++;
      for(k=1;k<=n;k++){
       if(this.distance[minpos]+this.cost[minpos][k] <  this.distance[k] && flag[k]!=1 )
       this.distance[k]=this.distance[minpos]+this.cost[minpos][k];
   }   
  } 
  
 }
 public static void main(String args[])
 {
  int nodes,source,i,j;
  Scanner in = new Scanner(System.in);
  System.out.println("Enter the Number of Nodes \n");
  nodes = in.nextInt();
  Dijkstra d = new Dijkstra();
  System.out.println("Enter the Cost Matrix Weights: \n");
        for(i=1;i<=nodes;i++)
          for(j=1;j<=nodes;j++)
          {
            d.cost[i][j]=in.nextInt();
            if(d.cost[i][j]==0)
              d.cost[i][j]=999;
          }
  System.out.println("Enter the Source Vertex :\n");
  source=in.nextInt();
  
  d.calc(nodes,source);
  System.out.println("The Shortest Path from Source \t"+source+"\t to all other vertices are : \n");
        for(i=1;i<=nodes;i++)
          if(i!=source)
  System.out.println("source :"+source+"\t destination :"+i+"\t MinCost is :"+d.distance[i]+"\t");
        
  
 } 
}

Please Click and Drag from the beginning to End of the above Source code for Selection and Copying.

To Compile and Run Java Program for the above Example :

javac Dijkstra.java
java Dijkstra

Enter the Number of Nodes :4
Enter the Cost Matrix Weights:
0 3 999 7
3 0 4 2
999 4 0 5
7 2 5 0
Enter the Source Vertex :
1
The Shortest Path from Source Vertex 1 to all other vertices are :

source :1 destination :2 MinCost is :3
source :1 destination :3 MinCost is :7
source :1 destination :4 MinCost is :5

Please Note that this.distance[] and this.cost[][] basically refers to current object d's distance and Cost matrix .Thanks and Enjoy Coding.

If you have any Comments please let me know .