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.

```
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[source] = 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

Sanfoundry Global Education & Learning Series – 1000 Java Programs.

If you wish to look at all Java Programming examples, go to Java Programs.

« Prev - Java Program for Topological Sorting in Graphs

» Next - Java Program to Implement Dijkstra’s Algorithm using Queue

Related Posts:

Recommended Articles: