# Java Program to Implement Dijkstra’s Algorithm using Priority_queue

«
»
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.

1. `import java.util.HashSet;`
2. `import java.util.InputMismatchException;`
3. `import java.util.PriorityQueue;`
4. `import java.util.Scanner;`
5. `import java.util.Set;`
6. ` `
7. `public class DijkstraPriorityQueue`
8. `{`
9. `    private int distances[];`
10. `    private Set<Integer> settled;`
11. `    private PriorityQueue<Node> priorityQueue;`
12. `    private int number_of_nodes;`
13. `    private int adjacencyMatrix[][];`
14. ` `
15. `    public  DijkstraPriorityQueue(int number_of_nodes)`
16. `    {`
17. `        this.number_of_nodes = number_of_nodes;`
18. `        distances = new int[number_of_nodes + 1];`
19. `        settled = new HashSet<Integer>();`
20. `        priorityQueue = new PriorityQueue<Node>(number_of_nodes,new Node());`
21. `        adjacencyMatrix = new int[number_of_nodes + 1][number_of_nodes + 1];`
22. `    }`
23. ` `
24. `    public void dijkstra_algorithm(int adjacency_matrix[][], int source)`
25. `    {`
26. `        int evaluationNode;`
27. `        for (int i = 1; i <= number_of_nodes; i++)`
28. `            for (int j = 1; j <= number_of_nodes; j++)`
29. `                adjacencyMatrix[i][j] = adjacency_matrix[i][j];`
30. ` `
31. `        for (int i = 1; i <= number_of_nodes; i++)`
32. `        {`
33. `            distances[i] = Integer.MAX_VALUE;`
34. `        }`
35. ` `
36. `        priorityQueue.add(new Node(source, 0));`
37. `        distances[source] = 0;`
38. `        while (!priorityQueue.isEmpty())`
39. `        {`
40. `            evaluationNode = getNodeWithMinimumDistanceFromPriorityQueue();`
41. `            settled.add(evaluationNode);`
42. `            evaluateNeighbours(evaluationNode);`
43. `        }`
44. `    } `
45. ` `
46. `    private int getNodeWithMinimumDistanceFromPriorityQueue()`
47. `    {`
48. `        int node = priorityQueue.remove();`
49. `        return node;`
50. `    }`
51. ` `
52. `    private void evaluateNeighbours(int evaluationNode)`
53. `    {`
54. `        int edgeDistance = -1;`
55. `        int newDistance = -1;`
56. ` `
57. `        for (int destinationNode = 1; destinationNode <= number_of_nodes; destinationNode++)`
58. `        {`
59. `            if (!settled.contains(destinationNode))`
60. `            {`
61. `                if (adjacencyMatrix[evaluationNode][destinationNode] != Integer.MAX_VALUE)`
62. `                {`
63. `                    edgeDistance = adjacencyMatrix[evaluationNode][destinationNode];`
64. `                    newDistance = distances[evaluationNode] + edgeDistance;`
65. `                    if (newDistance < distances[destinationNode])`
66. `                    {`
67. `                        distances[destinationNode] = newDistance;`
68. `                    }`
69. `                    priorityQueue.add(new Node(destinationNode,distances[destinationNode]));`
70. `                }   `
71. `            }`
72. `        }`
73. `    }`
74. ` `
75. `    public static void main(String... arg)`
76. `    {`
77. `        int adjacency_matrix[][];`
78. `        int number_of_vertices;`
79. `        int source = 0;`
80. `        Scanner scan = new Scanner(System.in);`
81. `        try`
82. `        {`
83. `            System.out.println("Enter the number of vertices");`
84. `            number_of_vertices = scan.nextInt();`
85. `            adjacency_matrix = new int[number_of_vertices + 1][number_of_vertices + 1];`
86. ` `
87. `            System.out.println("Enter the Weighted Matrix for the graph");`
88. `            for (int i = 1; i <= number_of_vertices; i++)`
89. `            {`
90. ` 	        for (int j = 1; j <= number_of_vertices; j++)`
91. `                {`
92. `                    adjacency_matrix[i][j] = scan.nextInt();`
93. `		    if (i == j)`
94. `                    {`
95. `                        adjacency_matrix[i][j] = 0;`
96. `                        continue;`
97. `                    }`
98. `                    if (adjacency_matrix[i][j] == 0)`
99. `                    {`
100. `                        adjacency_matrix[i][j] =  Integer.MAX_VALUE;`
101. `                    }`
102. `                }`
103. `            }`
104. ` `
105. `            System.out.println("Enter the source ");`
106. `            source = scan.nextInt();`
107. ` `
108. `            DijkstraPriorityQueue dijkstrasPriorityQueue = new DijkstraPriorityQueue(number_of_vertices);`
109. `            dijkstrasPriorityQueue.dijkstra_algorithm(adjacency_matrix, source);`
110. ` `
111. `            System.out.println("The Shorted Path to all nodes are ");`
112. `            for (int i = 1; i <= dijkstrasPriorityQueue.distances.length - 1; i++)`
113. `            {`
114. `                System.out.println(source + " to " + i + " is " + dijkstrasPriorityQueue.distances[i]);`
115. `            }`
116. `        } catch (InputMismatchException inputMismatch)`
117. `        {`
118. `            System.out.println("Wrong Input Format");`
119. `        }`
120. `        scan.close();`
121. `    }	`
122. `}`
123. `class Node implements Comparator<Node>`
124. `{`
125. `    public int node;`
126. `    public int cost;`
127. ` `
128. `    public Node()`
129. `    {`
130. `    }`
131. ` `
132. `    public Node(int node, int cost)`
133. `    {`
134. `        this.node = node;`
135. `        this.cost = cost;`
136. `    }`
137. ` `
138. `    @Override`
139. `    public int compare(Node node1, Node node2)`
140. `    {`
141. `        if (node1.cost < node2.cost)`
142. `            return -1;`
143. `        if (node1.cost > node2.cost)`
144. `            return 1;`
145. `        return 0;`
146. `    }`
147. `}`

```\$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```

Sanfoundry Global Education & Learning Series – 1000 Java Programs. 