Java Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time

«
»
This Java program is to Implement weighted graph and find shortest path from one source vertex to every other vertex. Dijkstra’s Algorithm can be used to achieve this goal.

Here is the source code of the Java Program to Find the Shortest Path from Source Vertex to All Other Vertices in Linear Time. 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 from one vertex to all other 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 Shortest_Path_to_AllVertex
  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 Shortest_Path_to_AllVertex(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 shortestPath(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;
  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.             Shortest_Path_to_AllVertex sp = new Shortest_Path_to_AllVertex(
  127.                     number_of_vertices);
  128.             sp.shortestPath(adjacency_matrix, source);
  129.  
  130.             System.out.println("The Shorted Path from " + source
  131.                     + " to all other nodes are: ");
  132.             for (int i = 1; i <= sp.distances.length - 1; i++)
  133.             {
  134.  
  135.                 System.out.println(source + " to " + i + " is "
  136.                         + sp.distances[i]);
  137.             }
  138.         } catch (InputMismatchException inputMismatch)
  139.         {
  140.             System.out.println("Wrong Input Format");
  141.         }
  142.         scan.close();
  143.     }
  144. }

Output:

$ javac Shortest_Path_to_AllVertex.java
$ java Shortest_Path_to_AllVertex
 
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
The Shorted Path from 1 to all other nodes are: 
1 to 1 is 0
1 to 2 is 8
1 to 3 is 6
1 to 4 is 5
1 to 5 is 3

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
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 & technical discussions at Telegram SanfoundryClasses.