Dijkstra使用PriorityQueue的Java中最短路径算法

给定一个带有邻接表表示节点之间边缘的图形, 任务是实现Dijkstra的算法对于单源最短路径使用优先队列在Java中。

给定一个图和图中的一个源顶点, 找到从源到给定图中所有顶点的最短路径。

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

我们已经讨论了Dijkstra最短的Path实现, 例如Dijkstra的邻接矩阵表示算法(时间复杂度为O(v2)

以下是Dijkstra算法使用优先级队列的Java实现：

//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 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

---