우선 순위 대기열에 elemenet이 있음에도 불구하고 우선 순위 대기열에 포함 된 메소드가 항상 false를 반환합니다.

Question

우선 순위 대기열에 포함 된 요소가 우선 순위 대기열에 있지만 항상 우선 순위 대기열에 포함 된 메소드가 항상 false를 반환합니다. 나는 compare 메소드를 어떻게 그리고 어디에서 대체해야하는지 알지 못한다. adjacency List를 사용하는 Dijkstra 알고리즘을위한 프로그램입니다. 이 코드에서 @Override 비교 메서드를 구현하는 방법.

import java.util.*; 
class dijkstra{ 
class AdjListNode{ 
    private int vertex,weight; 
    AdjListNode(int v,int w){vertex=v;weight=w;} 
    int getv(){return vertex;} 
    int getw(){return weight;}   
@Override 
    public boolean equals(AdjListNode obj){ 
     return (obj.getv() == this.vertex && obj.getw()==this.weight); 
    } 
} 
class Graph{ 
    private int V; 
    private LinkedList<AdjListNode> adj[]; 
    Graph(int v){ 
     V=v; 
     adj=new LinkedList[v]; 
     for(int i=0;i<V;i++){ 
      adj[i]=new LinkedList<AdjListNode>(); 
     } 
    } 
    void addEdge(int u,int v,int w){ 
     //undirected graph so edges are added bothways 
     AdjListNode node1=new AdjListNode(v,w); 
     adj[u].add(node1); 
    } 
    void print(){ 
     for(int i=0;i<V;i++){ 
      Iterator<AdjListNode> itr=adj[i].listIterator(); 
      System.out.print(i+"==>"); 
      while(itr.hasNext()){ 
       AdjListNode node=itr.next(); 
       System.out.print("("+node.getv()+","+node.getw()+") "); 
      } 
      System.out.println(); 
     } 
    } 
    void sssp(int src){ 
     PriorityQueue<AdjListNode> q = new PriorityQueue<AdjListNode>(V, new Comparator<AdjListNode>() { 
       @Override 
       public int compare(AdjListNode node1, AdjListNode node2) { 
        return Integer.compare(node1.getw(), node2.getw()); 
       } 
     }); 
     q.add(new AdjListNode(0,0)); 
     int dist[]=new int[V]; 
     Arrays.fill(dist,Integer.MAX_VALUE); 
     dist[src]=0; 
     while(q.size()!=0){ 
      AdjListNode node=q.peek(); 
      Iterator<AdjListNode> itr=adj[node.getv()].listIterator(); 
      q.poll(); 
      while(itr.hasNext()){ 
       AdjListNode temp=itr.next(); 
       if(dist[temp.getv()]>dist[node.getv()]+temp.getw()){ 
        int oldweight=dist[temp.getv()]; 
        dist[temp.getv()]=dist[node.getv()]+temp.getw(); 
        //System.out.println(node.getv()+" "+temp.getv()+" "+oldweight+" "+q.contains(new AdjListNode(temp.getv(),oldweight))); 
        if(q.contains(new AdjListNode(temp.getv(),oldweight))){ 
         System.out.println("yes"); 
         q.remove(new AdjListNode(temp.getv(),oldweight)); 
         q.add(new AdjListNode(temp.getv(),dist[temp.getv()])); 
        }       
        else{ 
         q.add(new AdjListNode(temp.getv(),dist[temp.getv()])); 
         //System.out.println(q.contains(new AdjListNode(temp.getv(),dist[temp.getv()]))); 
        } 
       } 
      } 
     } 
     for(int i=0;i<V;i++) 
      System.out.print(dist[i]+" "); 
    } 

} 
Graph newGraph(int vertices){ 
    return new Graph(vertices); 
} 
public static void main(String[] args){ 
    dijkstra d=new dijkstra(); 
    Graph g=d.newGraph(6); 
    g.addEdge(0,1,2); 
    g.addEdge(0,3,30); 
    g.addEdge(0,5,40); 
    g.addEdge(0,4,5); 
    g.addEdge(0,2,60); 
    g.addEdge(1,4,11); 
    g.addEdge(1,3,5); 
    g.addEdge(1,2,2); 
    g.addEdge(1,5,4); 
    g.addEdge(2,1,3); 
    g.addEdge(2,3,1); 
    g.addEdge(2,4,3); 
    g.addEdge(3,4,3); 
    g.addEdge(3,5,11); 
    g.addEdge(4,3,2); 
    g.addEdge(4,5,12); 
    g.print(); 
    g.sssp(0); 
} 

}

출력은 에러를 도시하고 정확한 결과를 반환하지만 거기에 가고 약간의 오차이며, 방법은 작동하지 포함되지 않는다. 올바른 접근 방식을 제안하십시오.

Answer 1

당신은이 특별한 경우에 나는 방법은 직접 호출되지 않습니다 생각하지만, 당신의 equals 구현과 일치하는 방식으로,뿐만 아니라 AdjListNode (및 hashCode에 equals 메서드를 재정의해야하지만, 그것은 좋은 습관이다 그 앞으로 많은 문제를 예방할 것입니다.)

contains 메서드는 큐의 두 객체가 동일한 지 확인하기 위해이 메소드가 필요하며 객체의 기본 구현은 해당 객체가 정확한 인스턴스인지 여부 만 확인합니다 (알고리즘의 경우는 제외).)