This Java program,to Implement Dijkstra’s algorithm using Priority 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 Priority 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.PriorityQueue; import java.util.Scanner; import java.util.Set; public class DijkstraPriorityQueue { private int distances[]; private Set<Integer> settled; private PriorityQueue<Node> priorityQueue; private int number_of_nodes; private int adjacencyMatrix[][]; public DijkstraPriorityQueue(int number_of_nodes) { this.number_of_nodes = number_of_nodes; distances = new int[number_of_nodes + 1]; settled = new HashSet<Integer>(); priorityQueue = new PriorityQueue<Node>(number_of_nodes,new Node()); 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; } priorityQueue.add(new Node(source, 0)); distances = 0; while (!priorityQueue.isEmpty()) { evaluationNode = getNodeWithMinimumDistanceFromPriorityQueue(); settled.add(evaluationNode); evaluateNeighbours(evaluationNode); } } private int getNodeWithMinimumDistanceFromPriorityQueue() { int node = priorityQueue.remove(); 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; } priorityQueue.add(new Node(destinationNode,distances[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(); DijkstraPriorityQueue dijkstrasPriorityQueue = new DijkstraPriorityQueue(number_of_vertices); dijkstrasPriorityQueue.dijkstra_algorithm(adjacency_matrix, source); System.out.println("The Shorted Path to all nodes are "); for (int i = 1; i <= dijkstrasPriorityQueue.distances.length - 1; i++) { System.out.println(source + " to " + i + " is " + dijkstrasPriorityQueue.distances[i]); } } catch (InputMismatchException inputMismatch) { System.out.println("Wrong Input Format"); } scan.close(); } } class Node implements Comparator<Node> { public int node; public int cost; public Node() { } public Node(int node, int cost) { this.node = node; this.cost = cost; } @Override public int compare(Node node1, Node node2) { if (node1.cost < node2.cost) return -1; if (node1.cost > node2.cost) return 1; return 0; } }
$javac DijkstraPriorityQueue.java $java DijkstraPriorityQueue 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:
Spring Data JPA @Modifying Annotation
HTTP Authentification and CGI/Servlet
Java Program to Check whether Graph is a Bipartite using 2 Color Algorithm
Spring Boot Actuator
Java Program to Implement TreeMap API
Chuyển đổi từ HashMap sang ArrayList
Java Program to Implement Merge Sort on n Numbers Without tail-recursion
Java Program to Show the Duality Transformation of Line and Point
Introduction to Spliterator in Java
Java Program to Implement Nth Root Algorithm
Java Program to Implement Adjacency List
Consumer trong Java 8
Java Collections Interview Questions
Map Serialization and Deserialization with Jackson
Introduction to Spring Data REST
Java Program to implement Array Deque
What is Thread-Safety and How to Achieve it?
Spring Boot Gradle Plugin
Java Program to Implement Meldable Heap
Java Program to Find the Peak Element of an Array O(n) time (Naive Method)
Java Program to Solve Knapsack Problem Using Dynamic Programming
Life Cycle of a Thread in Java
A Guide to Java HashMap
Java Program to Implement Suffix Tree
Vector trong Java
Spring Boot - Admin Server
Java TreeMap vs HashMap
Working with Kotlin and JPA
Spring Boot - Tomcat Port Number
Java Program to Implement Bit Array
Java Stream Filter with Lambda Expression
Java Program to Compare Binary and Sequential Search