Dijkstra在Java上使用優先級隊列的算法

Question

我需要在Java中使用優先級隊列來實現Dijkstra算法。這裏是我的代碼到目前爲止：

public class Node { 
     long idNum; 
     String label; 
     HashSet<Edge> outEdges; 
     HashSet<Edge> inEdges; 
     int indegree; 
     int outdegree; 

     int inNum, outNum; 
     HashMap<Node, Edge> incoming, outgoing; 

     Node(String label, Long idNum) { 
      this.label = label; 
      this.idNum = idNum; 

      inNum =0; 
      outNum=0; 
      incoming = new HashMap<Node, Edge>(); 
      outgoing = new HashMap<Node, Edge>(); 

     } 
     Node(String Label){ 
      this.label=label; 
     } 

     public void addOutgoing(Node n, Edge e){ 
      if(n==null) return; 
      outgoing.put(n,e); 
      outNum++; 
     } 
     public void addIncoming(Node n, Edge e){ 
      if(n==null) return; 
      incoming.put(n, e); 
      inNum++; 
     } 
     public void delIn(Node n){ 
      incoming.remove(n); 
      inNum--; 
     } 
     public void delOut(Node n){ 
      outgoing.remove(n); 
      outNum--; 
     } 

     public int getinNum(){ 
      return this.inNum; 
     } 
     public boolean containsEdge(Edge e){ 
      if(incoming.containsValue(e) || outgoing.containsValue(e)){ 
       return true; 
      } 
      return false; 
     } 

     String getLabel(){ 
      return this.label; 
     } 


    } 

    public class Edge { 

     long idNum, weight; 
     String sLabel, dLabel, eLabel; 
     Node sNode, dNode; 
     Node from; 
     Node to; 
     int distance; 

     public Edge(long idNum, String sLabel, String dLabel, String eLabel) { 
      this.idNum = idNum; 
      // this.weight=weight; 
      this.sLabel = sLabel; 
      this.dLabel = dLabel; 
      this.eLabel = eLabel; 
     } 

     public Edge(Node from, Node to) { 
      this.from = from; 
      this.to = to; 
     } 

     long getidNum() { 
      return this.idNum; 
     } 

     public int getDistance() { 
      return this.distance; 
     } 

    } 


public class DiGraph implements DiGraph_Interface { 
    // private Map<Node, Edge> digraph = new HashMap<Node, Edge>(); 
    private Map<String, Long> nodes = new HashMap<String, Long>(); 
    private Set<Node> nodes1 = new HashSet<Node>(); 
    private Set<Edge> edges = new HashSet<Edge>(); 
    private Map<Node, Node> edges1 = new HashMap<Node, Node>(); 
    private Set<Long> edge_ids = new HashSet<Long>(); 

    public long numEdges = 0; 
    public long numNodes = 0; 

    public DiGraph() { // default constructor 
     // explicitly include this 
     // we need to have the default constructor 
     // if you then write others, this one will still be there 

    } 

    @Override 
    public boolean addNode(long idNum, String label) { 
     Node node = new Node(label, idNum); 
     if(nodes.containsKey(label) || idNum <0 || label==null || nodes.containsValue(idNum)){ 
      return false; 
     } 
     nodes.put(label, idNum); 
     nodes1.add(node); 
     numNodes++; 
     return true; 

    } 

    @Override 
    public boolean addEdge(long idNum, String sLabel, String dLabel, long weight, String eLabel) { 
     Edge e = new Edge(idNum, sLabel, dLabel, eLabel); 
     Node n1 = new Node(sLabel, idNum); 
     Node n2 = new Node(dLabel, idNum); 
     if(edge_ids.contains(idNum)){ 
      return false; 
     } 
     for(Node n: nodes1){ 
      if(n.containsEdge(e)){ 
       return false;} 
     } 
     for(Edge edge: edges){ 
      if(edge.dLabel == dLabel && edge.sLabel == sLabel){return false;} 
     } 

     boolean check1=false; 
     boolean check2=false; 
     for(Node n: nodes1){ 
      if(n.label.equals(sLabel)){ 
       e.sNode=n; 
       check1=true; 
      } 
      if(n.label.equals(dLabel)){ 
       e.dNode=n; 
       check2=true; 
      } 
     } 
     if(!check1 || !check2){return false;} 

     e.sNode.addOutgoing(e.dNode, e); 
     e.dNode.addIncoming(e.sNode,e); 

     n1.addOutgoing(n2, e); 
     n2.addIncoming(n1, e); 
     edge_ids.add(idNum); 
     edges.add(e); 
     numEdges++; 
     return true; 

    } 

    @Override 
    public boolean delNode(String label) { 
     Node node = new Node(label); 
     if (!nodes.containsKey(label)) { 
      return false; 
     } 
     if (nodes.containsKey(label) || nodes1.contains(node)) { 
      nodes.remove(label, nodes.get(label)); 
      nodes1.remove(node); 
      numNodes--; 
      return true; 
     } 
     Set<Edge> remainingEdges = new HashSet<Edge>(); 
     for(Edge edge : edges){ 
      if(!node.containsEdge(edge)){ 
       remainingEdges.add(edge); 
      } 
     } 
     edges = remainingEdges; 
     numNodes--; 
     return true; 
    } 

    @Override 
    public boolean delEdge(String sLabel, String dLabel) { 
     if(!nodes.containsKey(dLabel)|| !nodes.containsKey(sLabel)){ 
      return false; 
     } 
     for(Edge edge: edges){ 
      if(edge.dLabel == dLabel && edge.sLabel == sLabel){ 
       edge.sNode.delOut(edge.dNode); 
       edge.dNode.delIn(edge.sNode); 
       long idNum = edge.getidNum(); 
       numEdges--; 
       edges.remove(edge); 
       edge_ids.remove(idNum); 
       return true; 
      } 
     } 
     return false; 
    } 


    @Override 
    public long numNodes() { 
     return this.numNodes; 
    } 

    @Override 
    public long numEdges() { 
     return this.numEdges; 
    } 

    @Override 
    public String[] topoSort() { 


     ArrayList<Node> nodeArray = new ArrayList<Node>(); 
     Stack<Node> nodeStack = new Stack<Node>(); 
     for(Node n: nodes1){ 
      nodeArray.add(n); 
     } 
     String[] topoSort = new String[(int) numNodes]; 
     int counter=0; 

     int i=0; 
     //for(int i=0; i< numNodes; i++){ 
      for(Node n: nodes1){ 

       if(n.inNum==0){ 
        nodeStack.push(n); 
       } 
       if(nodeStack.isEmpty()){ 
        return null; 
       } 
       while(!nodeStack.isEmpty()){ 
        nodeStack.pop(); 
        nodeArray.remove(n); 
       if(n.incoming==null){ 
        topoSort[i]=n.getLabel(); 
        counter++; 
        i++; 
       } 
       } 
      //} 
     } 
     if(counter != numNodes){ 
      return null; 
     } 
     return topoSort; 
    } 

    @Override 
    public ShortestPathInfo[] shortestPath(String label) { 
     Node startNode = new Node(label); 

     return null; 
    } 
} 

我需要填寫shortestPath方法並返回一個節點數組。但是，我不確定如何去做這件事。我知道我需要在某個時候建立一個優先隊列，但有人可以向我解釋如何？我已經創建了startNode，並且我知道需要爲其分配距離值0，其餘節點的距離值爲無窮大。還有一個可比較的地方呢？

Answer 1

您可以使用java.util.TreeSet作爲優先級隊列。它包含用於將元素放入隊列的方法add（）和用於取出具有最低值的元素的pollFirst（）。

爲了便於比較，您可以將要放入隊列的類對象（最有可能不是簡單的Node，而是包含對Node的引用以及恢復所需的其他信息的附加類路徑）實現接口Comparable或創建一個Comparator，並將其作爲參數傳遞給TreeSet構造函數。在任何一種情況下，您都需要實現方法compareTo（），它將按照距離比較節點，這是算法所要求的。

Answer 2

與Node類開始：

public class Node { 
    // add a parent attribute to the class 
    // this will be used in your shortestPath method 
    // i have explained it below 
    private Node parent; 
} 

的Edge類：

public class Edge { 
    // why do you have four of these? You only need two 
    private Node sNode, dNode; 
    private Node from; 
    private Node to; 
} 

你有向圖類看起來太複雜了我。你可以把它簡化一點：

public class DiGraph implements DiGraph_Interface { 

    private LinkedList<Node>[] adjList; 
    private HashSet<Edge> edges; 

    // implement the interface methods as you have done 
} 

的搜索方法，在DiGraph：

@Override 
public ShortestPathInfo[] shortestPath(String label) { 
    PriorityQueue<Node> queue = new PriorityQueue<>(new Comparator() { 
     @Override 
     public int compare(Object o1, Object o2) { 
      Node n1 = (Node) o1; 
      Node n2 = (Node) o2; 
      // this assumes that lower number is higher priority 
      // also, this compare method compares the two string values 
      // from the two nodes. If n1.label is lexicographically smaller 
      // then n1 will be added high up in the queue 
      // you can compare based on the node's idNum too 
      // you should implement it based on your requirements 
      return n1.label.compareTo(n2.label); 
     } 
    }); 

    // create a method getScrNode() 
    // in that method, traverse the linkedList to find the srcNode 
    // You can do this easily if you keep Map of nodes, like you did in your code 
    // but that just takes too much memory 
    Node start = getSrcNode(label); 
    queue.add(start); 
    while (!queue.isEmpty()) { 
     /*This is your main exercise. You should solve it yourself. 
     Somewhere here you should set the parent of a node 
     */    
    } 

    // print the path 
    if (done) { 
     while (current.getParent() != null) 
      System.out.println(current.getLabel()); 
    } 
    return null; 
}