Java Program to Find the Shortest Path using Dijkstra’s Algorithm

This is a Java Program to perform Dijkstra’s Shortest path algorithm. For a given source vertex (node) in the graph, the algorithm finds the path with lowest cost (i.e. the shortest path) between that vertex and every other vertex. It can also be used for finding costs of shortest paths from a single vertex to a single destination vertex by stopping the algorithm once the shortest path to the destination vertex has been determined. For example, if the vertices of the graph represent cities and edge path costs represent driving distances between pairs of cities connected by a direct road, Dijkstra’s algorithm can be used to find the shortest route between one city and all other cities.

Here is the source code of the Java Program to Find the Shortest Path Between Two Vertices Using Dijkstra’s Algorithm. The Java program is successfully compiled and run on a Windows system. The program output is also shown below.

  1. //This is a java program to find the shortest path between source vertex and destination vertex
  2. import java.util.HashSet;
  3. import java.util.InputMismatchException;
  4. import java.util.Iterator;
  5. import java.util.Scanner;
  6. import java.util.Set;
  7.  
  8. public class Dijkstras_Shortest_Path
  9. {
  10.     private int          distances[];
  11.     private Set<Integer> settled;
  12.     private Set<Integer> unsettled;
  13.     private int          number_of_nodes;
  14.     private int          adjacencyMatrix[][];
  15.  
  16.     public Dijkstras_Shortest_Path(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.         unsettled = new HashSet<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.         unsettled.add(source);
  38.         distances[source] = 0;
  39.         while (!unsettled.isEmpty())
  40.         {
  41.             evaluationNode = getNodeWithMinimumDistanceFromUnsettled();
  42.             unsettled.remove(evaluationNode);
  43.             settled.add(evaluationNode);
  44.             evaluateNeighbours(evaluationNode);
  45.         }
  46.     }
  47.  
  48.     private int getNodeWithMinimumDistanceFromUnsettled()
  49.     {
  50.         int min;
  51.         int node = 0;
  52.  
  53.         Iterator<Integer> iterator = unsettled.iterator();
  54.         node = iterator.next();
  55.         min = distances[node];
  56.         for (int i = 1; i <= distances.length; i++)
  57.         {
  58.             if (unsettled.contains(i))
  59.             {
  60.                 if (distances[i] <= min)
  61.                 {
  62.                     min = distances[i];
  63.                     node = i;
  64.                 }
  65.             }
  66.         }
  67.         return node;
  68.     }
  69.  
  70.     private void evaluateNeighbours(int evaluationNode)
  71.     {
  72.         int edgeDistance = -1;
  73.         int newDistance = -1;
  74.  
  75.         for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)
  76.         {
  77.             if (!settled.contains(destinationNode))
  78.             {
  79.                 if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)
  80.                 {
  81.                     edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];
  82.                     newDistance = distances[evaluationNode] + edgeDistance;
  83.                     if (newDistance < distances[destinationNode])
  84.                     {
  85.                         distances[destinationNode] = newDistance;
  86.                     }
  87.                     unsettled.add(destinationNode);
  88.                 }
  89.             }
  90.         }
  91.     }
  92.  
  93.     public static void main(String... arg)
  94.     {
  95.         int adjacency_matrix[][];
  96.         int number_of_vertices;
  97.         int source = 0, destination = 0;
  98.         Scanner scan = new Scanner(System.in);
  99.         try
  100.         {
  101.             System.out.println("Enter the number of vertices");
  102.             number_of_vertices = scan.nextInt();
  103.             adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];
  104.  
  105.             System.out.println("Enter the Weighted Matrix for the graph");
  106.             for (int i = 1; i <= number_of_vertices; i++)
  107.             {
  108.                 for (int j = 1; j <= number_of_vertices; j++)
  109.                 {
  110.                     adjacency_matrix[i][j] = scan.nextInt();
  111.                     if (i == j)
  112.                     {
  113.                         adjacency_matrix[i][j] = 0;
  114.                         continue;
  115.                     }
  116.                     if (adjacency_matrix[i][j] == 0)
  117.                     {
  118.                         adjacency_matrix[i][j] = Integer.MAX_VALUE;
  119.                     }
  120.                 }
  121.             }
  122.  
  123.             System.out.println("Enter the source ");
  124.             source = scan.nextInt();
  125.  
  126.             System.out.println("Enter the destination ");
  127.             destination = scan.nextInt();
  128.  
  129.             Dijkstras_Shortest_Path dijkstrasAlgorithm = new Dijkstras_Shortest_Path(
  130.                     number_of_vertices);
  131.             dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source);
  132.  
  133.             System.out.println("The Shorted Path from " + source + " to " + destination + " is: ");
  134.             for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++)
  135.             {
  136.                 if (i == destination)
  137.                     System.out.println(source + " to " + i + " is "
  138.                             + dijkstrasAlgorithm.distances[i]);
  139.             }
  140.         } catch (InputMismatchException inputMismatch)
  141.         {
  142.             System.out.println("Wrong Input Format");
  143.         }
  144.         scan.close();
  145.     }
  146. }

Output:

$ javac Dijkstras_Shortest_Path.java
$ java Dijkstras_Shortest_Path
 
Enter the number of vertices
5
Enter the Weighted Matrix for the graph
0 9 6 5 3 
0 0 0 0 0
0 2 0 4 0
0 0 0 0 0
0 0 0 0 0
Enter the source 
1 
Enter the destination 
4
The Shorted Path from 1 to 4 is: 
1 to 4 is 5

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

advertisement
advertisement

Here’s the list of Best Books in Java Programming, Data Structures and Algorithms.

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 & discussions at Telegram SanfoundryClasses.