# Java Program to Implement Dijkstra’s Algorithm using Queue

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.

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

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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.