If you studied high school or college in Computer Science major you will definitely come across this algorithm. So what is Dijkstra’s algorithm and why we need this algorithm, let us look deep about this in this article

Dijkstra’s Algorithm is an algorithm which is used to find the shortest distance between two nodes in a graph. This algorithm was developed by Dijkstra in 1959 to minimize the amount of wire needed to connect the pins in the back every machine in his institution. Dijkstra’s ultimate aim is to create the shortest path tree. Before looking into the actual algorithm let us see some of the practical usages of this algorithm:

1. You all guys are using Google maps, Right? Have you ever think why Google is recommending this route to reach your destination? Google maps use purely this Dijkstra’s algorithm to decide a route for your travel. Google Maps marks your location as node A and your destination as node b. After, with this algorithm, it goes through all the shortest nodes (Paths) from the previous node to reach the destination.
2. Dijkstra’s algorithm is majorly used in routing protocols which is essential for any router to generate their forwarding table. By using this algorithm the router can update the shortest path from one router to another in the network.
3. It is widely used in the telephone network for cost-effectiveness.
4. This algorithm plays a very big role in Flight agenda.

Now, we understand this algorithm has an impact on our current life.  Let us see this algorithm to find the shortest Path tree.

Dijkstra’s ALGORITHM:

STEP 1:  Initially create a set that monitors the vertices which are included in the Shortest path tree. Make this set as empty first.

STEP 2: Initialize the value ‘0’  for the source vertex to make sure this is not picked first.

STEP 3: Other than the source node makes all the nodes distance as infinite.

STEP 4: Now select a vertex X which is not in the tree set and has minimum values.

STEP 5: Now include the vertex X in the Shortest path tree set.

STEP 6: Now start iterating through all the nodes of the vertex X. For every adjacent vertex Y, the distance from the source and the weight of edge X-Y is lesser than the distance of  Y then update the value of Y in the shortest path tree set.

Let us see how to implement this algorithm in Java programming. If you need to implement this algorithm in any other programming languages let us know in the comment section.

JAVA CODE:

//DIJKSTRA'S ALGORITHM USING JAVA BY www.geeks10.net

import java.util.*;
public class Solution
{
	 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();
	  Solution d = new Solution();
	  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");
	        } 
 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];
 }   
 } 
 }}

// CODED BY www.geeks10.net

The output of this program will be:

Use Your favoriteIDE to run this Program OR Just copy this code into notepad and save the file as Solution.java [Class name.java]. Then run this program using CMD. [Javac Solution.java and java Solution]

Conclusion

So that’s done with Dijkstra algorithm using java. Hope this article will help you to understand the Dijkstra’s Algorithm in 2020