Java’s Dijkstra Algorithm: Shortest Paths with PriorityQueue

Given a graph with adjacency tables representing the edges between nodes, the task is to implement Dijkstra’s algorithm for a single-source shortest path using a priority queue in Java.

Given a graph and a source vertex in the graph, find the shortest path from the source to all vertices in a given graph.

Input : Source = 0
Output : 
     Vertex   Distance from Source
        0                0
        1                4
        2                12
        3                19
        4                21
        5                11
        6                9
        7                8
        8                14

We have already discussed the shortest path implementation of Dijkstra, such as Dijkstra’s adjacency matrix representation algorithm (time complexity O(v2)

The following is a Java implementation of Dijkstra’s algorithm using priority queues:

//Java implementation of Dijkstra's Algorithm 
//using Priority Queue
import java.util.*;
public class DPQ {
     private int dist[];
     private Set<Integer> settled;
     private PriorityQueue<Node> pq;
     private int V; //Number of vertices
     List<List<Node>> adj;
  
     public DPQ( int V)
     {
         this .V = V;
         dist = new int [V];
         settled = new HashSet<Integer>();
         pq = new PriorityQueue<Node>(V, new Node());
     }
  
     //Function for Dijkstra's Algorithm
     public void dijkstra(List<List<Node>> adj, int src)
     {
         this .adj = adj;
  
         for ( int i = 0 ; i <V; i++)
             dist[i] = Integer.MAX_VALUE;
  
         //Add source node to the priority queue
         pq.add( new Node(src, 0 ));
  
         //Distance to the source is 0
         dist[src] = 0 ;
         while (settled.size() != V) {
  
             //remove the minimum distance node 
             //from the priority queue 
             int u = pq.remove().node;
  
             //adding the node whose distance is
             //finalized
             settled.add(u);
  
             e_Neighbours(u);
         }
     }
  
     //Function to process all the neighbours 
     //of the passed node
     private void e_Neighbours( int u)
     {
         int edgeDistance = - 1 ;
         int newDistance = - 1 ;
  
         //All the neighbors of v
         for ( int i = 0 ; i <adj.get(u).size(); i++) {
             Node v = adj.get(u).get(i);
  
             //If current node hasn't already been processed
             if (!settled.contains(v.node)) {
                 edgeDistance = v.cost;
                 newDistance = dist[u] + edgeDistance;
  
                 //If new distance is cheaper in cost
                 if (newDistance <dist[v.node])
                     dist[v.node] = newDistance;
  
                 //Add the current node to the queue
                 pq.add( new Node(v.node, dist[v.node]));
             }
         }
     }
  
     //Driver code
     public static void main(String arg[])
     {
         int V = 5 ;
         int source = 0 ;
  
         //Adjacency list representation of the 
         //connected edges
         List<List<Node>> adj = new ArrayList<List<Node>>();
  
         //Initialize list for every node
         for ( int i = 0 ; i <V; i++) {
             List<Node> item = new ArrayList<Node>();
             adj.add(item);
         }
  
         //Inputs for the DPQ graph
         adj.get( 0 ).add( new Node( 1 , 9 ));
         adj.get( 0 ).add( new Node( 2 , 6 ));
         adj.get( 0 ).add( new Node( 3 , 5 ));
         adj.get( 0 ).add( new Node( 4 , 3 ));
  
         adj.get( 2 ).add( new Node( 1 , 2 ));
         adj.get( 2 ).add( new Node( 3 , 4 ));
  
         //Calculate the single source shortest path
         DPQ dpq = new DPQ(V);
         dpq.dijkstra(adj, source);
  
         //Print the shortest path to all the nodes
         //from the source node
         System.out.println( "The shorted path from node :" );
         for ( int i = 0 ; i <dpq.dist.length; i++)
             System.out.println(source + " to " + i + " is "
                                + dpq.dist[i]);
     }
}
  
//Class to represent a node in the graph
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 ;
     }
}

The output is as follows:

The shorted path from node :
0 to 0 is 0
0 to 1 is 8
0 to 2 is 6
0 to 3 is 5
0 to 4 is 3