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:
Giới thiệu Google Guice – Dependency injection (DI) framework
Apache Commons Collections SetUtils
Java Program to Generate Random Numbers Using Probability Distribution Function
Sử dụng Fork/Join Framework với ForkJoinPool trong Java
Spring Boot Actuator
Rate Limiting in Spring Cloud Netflix Zuul
Spring Boot - Zuul Proxy Server and Routing
Java Program to Implement Stack using Two Queues
Java Program to Implement Hash Trie
Introduction to Spring Cloud Netflix – Eureka
Intro to Inversion of Control and Dependency Injection with Spring
Apache Commons Collections BidiMap
Java Program to Implement Queue using Two Stacks
Tính kế thừa (Inheritance) trong java
Partition a List in Java
Show Hibernate/JPA SQL Statements from Spring Boot
Java Program to Implement Variable length array
Java – Generate Random String
Multi Dimensional ArrayList in Java
Java Program to Implement Sorting of Less than 100 Numbers in O(n) Complexity
Cơ chế Upcasting và Downcasting trong java
A Guide to BitSet in Java
Base64 encoding và decoding trong Java 8
Một số ký tự đặc biệt trong Java
Java Program to Implement Sorted Circularly Singly Linked List
Spring Boot - Securing Web Applications
Java Program to Implement Floyd-Warshall Algorithm
A Guide to Spring Boot Admin
Converting String to Stream of chars
Limiting Query Results with JPA and Spring Data JPA
Implementing a Binary Tree in Java
Introduction to Spring Cloud CLI