Javaで優先キューを使用するDijkstraのアルゴリズム

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（）を含んでいます。

比較のために、キューに入れるクラスオブジェクトを作成することができます（ほとんどの場合、単純にノードではなく、ノードへの参照と復元に必要な追加情報を含む追加のクラスです）ルート）は、インターフェイスComparableを実装するか、Comparatorを作成し、それをTreeSetコンストラクタのパラメータとして渡します。どちらの場合でも、アルゴリズムによって必要とされるようにノードを距離で比較するメソッドcompareTo（）を実装する必要があります。あなたのNodeクラスを皮切り

Answer 2

：

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; 
} 

あなたはそれを少し簡略化することができます