Java Program to Implement Dijkstra’s Algorithm using Queue

«
»
This Java program,to Implement Dijkstra’s algorithm using Queue.Dijkstra’s algorithm is a graph search algorithm that solves the single-source shortest path problem for a graph with non-negative edge path costs, producing a shortest path tree.

Here is the source code of the Java program to implement Dijkstra’s algorithm using Queue. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. import java.util.HashSet;
  2. import java.util.InputMismatchException;
  3. import java.util.LinkedList;
  4. import java.util.Queue;
  5. import java.util.Scanner;
  6. import java.util.Set;
  7.  
  8. public class DijkstraQueue
  9. {
  10.     private int distances[];
  11.     private Queue<Integer> queue;
  12.     private Set<Integer> settled;
  13.     private int number_of_nodes;
  14.     private int adjacencyMatrix[][];
  15.  
  16.     public DijkstraQueue(int number_of_nodes)
  17.     {
  18.         this.number_of_nodes = number_of_nodes;
  19.         distances = new int[number_of_nodes + 1];
  20.         settled = new HashSet<Integer>();
  21.         queue = new LinkedList<Integer>();
  22.         adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];
  23.     }
  24.  
  25.     public void dijkstra_algorithm(int adjacency_matrix[][], int source)
  26.     {
  27.         int evaluationNode;
  28.         for (int i = 1; i <= number_of_nodes; i++)
  29.             for (int j = 1; j <= number_of_nodes; j++)
  30.                 adjacencyMatrix[i][j] = adjacency_matrix[i][j];
  31.  
  32.         for (int i = 1; i <= number_of_nodes; i++)
  33.         {
  34.             distances[i] = Integer.MAX_VALUE;
  35.         }
  36.  
  37.         queue.add(source);
  38.         distances[source] = 0;
  39.  
  40.         while (!queue.isEmpty())
  41.         {
  42.             evaluationNode = getNodeWithMinimumDistanceFromQueue();
  43.             settled.add(evaluationNode);
  44.             evaluateNeighbours(evaluationNode);
  45.         }
  46.     }
  47.  
  48.     private int getNodeWithMinimumDistanceFromQueue()
  49.     {
  50.         int min ;
  51.         int node = 0;
  52.         Iterator<Integer> iterator = queue.iterator();
  53.         node = iterator.next();
  54.         min = distances[node];
  55.  
  56.         for (int i = 1; i <= distances.length; i++)
  57.         {
  58.             if (queue.contains(i))
  59.             {
  60.                 if (distances[i] <= min)
  61.                 {
  62.                     min = distances[i];
  63.                     node = i;			
  64.                 }
  65.             }
  66.         }
  67.         queue.remove(node);
  68.         return node;
  69.     }
  70.  
  71.     private void evaluateNeighbours(int evaluationNode)
  72.     {
  73.         int edgeDistance = -1;
  74.         int newDistance = -1;
  75.  
  76.         for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
  77.         {
  78.             if (!settled.contains(destinationNode))
  79.             {
  80.                 if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
  81.                 {
  82.                     edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
  83.                     newDistance = distances[evaluationNode] + edgeDistance;
  84.                     if (newDistance < distances[destinationNode])
  85.                     {
  86.                         distances[destinationNode] = newDistance;
  87.                     }
  88.                     queue.add(destinationNode);
  89.                 }
  90.             }
  91.         }
  92.     }
  93.  
  94.     public static void main(String... arg)
  95.     {
  96.         int adjacency_matrix[][];
  97.         int number_of_vertices;
  98.         int source = 0;
  99.         Scanner scan = new Scanner(System.in);
  100.  
  101.         try
  102.         {
  103.             System.out.println("Enter the number of vertices");
  104.             number_of_vertices = scan.nextInt();
  105.             adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
  106.  
  107.             System.out.println("Enter the Weighted Matrix for the graph");
  108.             for (int i = 1; i <= number_of_vertices; i++)
  109.             {
  110.                 for (int j = 1; j <= number_of_vertices; j++)
  111.                 {
  112.                     adjacency_matrix[i][j] = scan.nextInt();
  113.                     if (i == j)
  114.                     {
  115.                         adjacency_matrix[i][j] = 0;
  116.                         continue;
  117.                     }
  118.                     if (adjacency_matrix[i][j] == 0)
  119.                     {
  120.                         adjacency_matrix[i][j] = Integer.MAX_VALUE;
  121.                     }
  122.                 }
  123.             }
  124.  
  125.             System.out.println("Enter the source ");
  126.             source = scan.nextInt();
  127.             DijkstraQueue dijkstrasQueue = new DijkstraQueue(number_of_vertices);
  128.             dijkstrasQueue.dijkstra_algorithm(adjacency_matrix, source);
  129.  
  130.             System.out.println("The Shorted Path to all nodes are ");
  131.             for (int i = 1; i <= dijkstrasQueue.distances.length - 1; i++)
  132.             {
  133.                 System.out.println(source + " to " + i + " is " + dijkstrasQueue.distances[i]);
  134.             }
  135.         } catch (InputMismatchException inputMismatch)
  136.         {
  137.             System.out.println("Wrong Input Format");
  138.         }
  139.         scan.close();
  140.     }
  141. }

$javac DijkstraQueue.java
$java DijkstraQueue 
Enter the number of vertices
5
Enter the Weighted Matrix for the graph
0 7 0 0 2
0 0 1 0 2
0 0 0 4 0
0 0 5 0 0
0 3 8 5 0
Enter the source 
1
The Shorted Path to all nodes are 
1 to 1 is 0
1 to 2 is 5
1 to 3 is 6
1 to 4 is 7
1 to 5 is 2

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement
If you wish to look at all Java Programming examples, go to Java Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.