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:
Registration with Spring Security – Password Encoding
Converting String to Stream of chars
Hướng dẫn sử dụng Java String, StringBuffer và StringBuilder
Guide To CompletableFuture
Spring Boot - Apache Kafka
Java Program to Solve TSP Using Minimum Spanning Trees
Java Program to Generate All Subsets of a Given Set in the Lexico Graphic Order
Spring Cloud – Bootstrapping
Java Program to Encode a Message Using Playfair Cipher
HttpAsyncClient Tutorial
Guava CharMatcher
An Introduction to ThreadLocal in Java
Converting Strings to Enums in Java
Java Program to Implement Wagner and Fisher Algorithm for online String Matching
Java Program to Implement Shoelace Algorithm
Tips for dealing with HTTP-related problems
Lập trình mạng với java
Java Program to Implement Patricia Trie
Xử lý ngoại lệ đối với trường hợp ghi đè phương thức trong java
Spring Data JPA and Null Parameters
The Guide to RestTemplate
Spring Boot - Build Systems
Spring Boot - Cloud Configuration Client
Java Map With Case-Insensitive Keys
Assert an Exception is Thrown in JUnit 4 and 5
Reactive Flow with MongoDB, Kotlin, and Spring WebFlux
Java 8 Stream findFirst() vs. findAny()
REST Web service: Basic Authentication trong Jersey 2.x
Java Program to Check Multiplicability of Two Matrices
How to Read a File in Java
The Modulo Operator in Java
Java Program to Implement Borwein Algorithm