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:
Hướng dẫn Java Design Pattern – Factory Method
Spring Boot: Customize Whitelabel Error Page
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
Removing all duplicates from a List in Java
Spring Boot - Exception Handling
How to Get All Spring-Managed Beans?
Spring Boot - Batch Service
Receive email using IMAP
Introduction to Using Thymeleaf in Spring
Guide to CountDownLatch in Java
Hướng dẫn Java Design Pattern – Composite
Java Program to Find Maximum Element in an Array using Binary Search
Java Program to Implement Ford–Fulkerson Algorithm
A Guide to Queries in Spring Data MongoDB
Java Program to Implement Bellman-Ford Algorithm
Servlet 3 Async Support with Spring MVC and Spring Security
Java Program to Implement Double Ended Queue
Java Program to Implement Best-First Search
Giới thiệu SOAP UI và thực hiện test Web Service
Encode/Decode to/from Base64
Java Program to Implement Aho-Corasick Algorithm for String Matching
Receive email by java client
Spring Boot - Eureka Server
Spring Boot - Tracing Micro Service Logs
Java Program to Emulate N Dice Roller
Java 8 – Powerful Comparison with Lambdas
Spring WebClient and OAuth2 Support
Guide to Escaping Characters in Java RegExps
Check if a String is a Palindrome in Java
Creating Docker Images with Spring Boot
Java Program to Perform Inorder Recursive Traversal of a Given Binary Tree
Tránh lỗi ConcurrentModificationException trong Java như thế nào?