This Java program,to Implement Dijkstra’s algorithm using Set.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 Set. The Java program is successfully compiled and run on a Linux system. The program output is also shown below.
import java.util.HashSet; import java.util.InputMismatchException; import java.util.Iterator; import java.util.Scanner; import java.util.Set; public class DijkstraAlgorithmSet { private int distances[]; private Set<Integer> settled; private Set<Integer> unsettled; private int number_of_nodes; private int adjacencyMatrix[][]; public DijkstraAlgorithmSet(int number_of_nodes) { this.number_of_nodes = number_of_nodes; distances = new int[number_of_nodes + 1]; settled = new HashSet<Integer>(); unsettled = new HashSet<Integer>(); adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1]; } public void dijkstra_algorithm(int adjacency_matrix[][], int source) { int evaluationNode; for (int i = 1; i <= number_of_nodes; i++) for (int j = 1; j <= number_of_nodes; j++) adjacencyMatrix[i][j] = adjacency_matrix[i][j]; for (int i = 1; i <= number_of_nodes; i++) { distances[i] = Integer.MAX_VALUE; } unsettled.add(source); distances = 0; while (!unsettled.isEmpty()) { evaluationNode = getNodeWithMinimumDistanceFromUnsettled(); unsettled.remove(evaluationNode); settled.add(evaluationNode); evaluateNeighbours(evaluationNode); } } private int getNodeWithMinimumDistanceFromUnsettled() { int min ; int node = 0; Iterator<Integer> iterator = unsettled.iterator(); node = iterator.next(); min = distances[node]; for (int i = 1; i <= distances.length; i++) { if (unsettled.contains(i)) { if (distances[i] <= min) { min = distances[i]; node = i; } } } return node; } private void evaluateNeighbours(int evaluationNode) { int edgeDistance = -1; int newDistance = -1; for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++) { if (!settled.contains(destinationNode)) { if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE) { edgeDistance = adjacencyMatrix[evaluationNode][destinationNode]; newDistance = distances[evaluationNode] + edgeDistance; if (newDistance < distances[destinationNode]) { distances[destinationNode] = newDistance; } unsettled.add(destinationNode); } } } } public static void main(String... arg) { int adjacency_matrix[][]; int number_of_vertices; int source = 0; Scanner scan = new Scanner(System.in); try { System.out.println("Enter the number of vertices"); number_of_vertices = scan.nextInt(); adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1]; System.out.println("Enter the Weighted Matrix for the graph"); for (int i = 1; i <= number_of_vertices; i++) { for (int j = 1; j <= number_of_vertices; j++) { adjacency_matrix[i][j] = scan.nextInt(); if (i == j) { adjacency_matrix[i][j] = 0; continue; } if (adjacency_matrix[i][j] == 0) { adjacency_matrix[i][j] = Integer.MAX_VALUE; } } } System.out.println("Enter the source "); source = scan.nextInt(); DijkstraAlgorithmSet dijkstrasAlgorithm = new DijkstraAlgorithmSet(number_of_vertices); dijkstrasAlgorithm.dijkstra_algorithm(adjacency_matrix, source); System.out.println("The Shorted Path to all nodes are "); for (int i = 1; i <= dijkstrasAlgorithm.distances.length - 1; i++) { System.out.println(source + " to " + i + " is "+ dijkstrasAlgorithm.distances[i]); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scan.close(); } }
$javac DijkstraAlgorithmSet.java $java DijkstraAlgorithmSet 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 to all 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
Related posts:
Java Program to Find Number of Spanning Trees in a Complete Bipartite Graph
Spring WebClient vs. RestTemplate
Guide to BufferedReader
Java Program to Find Inverse of a Matrix
Exception Handling in Java
Java Program to Implement Hash Trie
Java Program to Implement Hash Tables Chaining with Doubly Linked Lists
Java Program to Find the Peak Element of an Array O(n) time (Naive Method)
Java Program for Douglas-Peucker Algorithm Implementation
Exploring the New Spring Cloud Gateway
Ignore Null Fields with Jackson
Java Program to Implement Rolling Hash
Java Program to Implement Find all Cross Edges in a Graph
Spring Boot - Flyway Database
Automatic Property Expansion with Spring Boot
Introduction to Spring Security Expressions
Java – Combine Multiple Collections
Spring Boot - Actuator
Setting a Request Timeout for a Spring REST API
Java 8 StringJoiner
Java Program to Find the Minimum Element of a Rotated Sorted Array using Binary Search approach
Câu lệnh điều khiển vòng lặp trong Java (break, continue)
Java Program to Check the Connectivity of Graph Using DFS
Finding the Differences Between Two Lists in Java
Java Program to Implement PriorityBlockingQueue API
Java Program to Implement Sieve Of Sundaram
Java 9 Stream API Improvements
Check If a File or Directory Exists in Java
SOAP Web service: Authentication trong JAX-WS
How to use the Spring FactoryBean?
Spring MVC Setup with Kotlin
Concrete Class in Java