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.
import java.util.HashSet; import java.util.InputMismatchException; import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; import java.util.Set; public class DijkstraQueue { private int distances[]; private Queue<Integer> queue; private Set<Integer> settled; private int number_of_nodes; private int adjacencyMatrix[][]; public DijkstraQueue(int number_of_nodes) { this.number_of_nodes = number_of_nodes; distances = new int[number_of_nodes + 1]; settled = new HashSet<Integer>(); queue = new LinkedList<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; } queue.add(source); distances = 0; while (!queue.isEmpty()) { evaluationNode = getNodeWithMinimumDistanceFromQueue(); settled.add(evaluationNode); evaluateNeighbours(evaluationNode); } } private int getNodeWithMinimumDistanceFromQueue() { int min ; int node = 0; Iterator<Integer> iterator = queue.iterator(); node = iterator.next(); min = distances[node]; for (int i = 1; i <= distances.length; i++) { if (queue.contains(i)) { if (distances[i] <= min) { min = distances[i]; node = i; } } } queue.remove(node); 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; } queue.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(); DijkstraQueue dijkstrasQueue = new DijkstraQueue(number_of_vertices); dijkstrasQueue.dijkstra_algorithm(adjacency_matrix, source); System.out.println("The Shorted Path to all nodes are "); for (int i = 1; i <= dijkstrasQueue.distances.length - 1; i++) { System.out.println(source + " to " + i + " is " + dijkstrasQueue.distances[i]); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scan.close(); } }
$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
Related posts:
Java Map With Case-Insensitive Keys
Hướng dẫn Java Design Pattern – Abstract Factory
Transactions with Spring and JPA
Understanding Memory Leaks in Java
Java Program to Implement the MD5 Algorithm
Java Program to Implement Gauss Seidel Method
Java Program to Implement Shunting Yard Algorithm
Hướng dẫn Java Design Pattern – Command
Java Program to Implement the Binary Counting Method to Generate Subsets of a Set
Java Program to Check Whether a Weak Link i.e. Articulation Vertex Exists in a Graph
Java – Reader to InputStream
String Joiner trong Java 8
Inject Parameters into JUnit Jupiter Unit Tests
Apache Camel with Spring Boot
Tiêu chuẩn coding trong Java (Coding Standards)
HttpClient 4 Cookbook
Server-Sent Events in Spring
Using JWT with Spring Security OAuth
Exploring the New Spring Cloud Gateway
Java Program to Implement Hamiltonian Cycle Algorithm
Java Program to Implement K Way Merge Algorithm
Java Program to implement Array Deque
Java NIO2 Path API
Comparing Arrays in Java
Java Program to Implement Quick Sort Using Randomization
Java Program to subtract two large numbers using Linked Lists
Mockito and JUnit 5 – Using ExtendWith
Java Program to Perform the Sorting Using Counting Sort
Spring – Injecting Collections
Custom Exception trong Java
ThreadPoolTaskExecutor corePoolSize vs. maxPoolSize
Send an email with an attachment