Dijkstra 알고리즘에 대해 PriorityQueue를 어떻게 구현합니까?

Question

우선 순위 큐에 노드 (정수)를 추가하는 방법을 찾으려고 노력하고 있으므로 다른 클래스를 만들 수 없으므로 Dijkstra 알고리즘의 우선 순위 큐 구현에 관한 질문이 있습니다. 대기열을 사용하여 노드 내부의 가중치를 정렬하지만 노드 자체는 정렬하지 않습니다. 예를 들어

, I 3 개 노드 (0,1,2)가 노드 0 (10)의 중량을 가지며, 노드 1 (15)을 가지며, 노드 2는 본 내게 줘야 제

Queue<Integer> queue = new PriorityQueue<Integer>(); 
queue.add(0); 
queue.add(1); 
queue.add(2); 

while(!queue.isEmpty()){ 
    System.out.println(queue.poll()); 
} 

갖는다 2,0,1의 출력. 다른 클래스를 만들지 않고도이 작업을 수행 할 수 있습니까? 아니면 우선 순위 대기열 외에 다른 접근법을 사용할 수 있습니까?

미리 감사드립니다 !!!!!! 어떤 도움을 많이 주시면 감사하겠습니다!

내가 생각할 수있는 한 가지 해결책은 노드를 추가 할 때마다 일반 큐를 정렬하는 것입니다. 따라서 큐에 노드 2,0,1이 있고 8의 가중치를 가진 노드 3을 추가하고 싶습니다. 큐에 들어갈 때까지 큐의 최상위 요소와 가중치를 비교해야 할 것이므로 큐에 2,3,0,1이 될 것입니다.하지만 이것은 비효율적 인 종류의 일종입니다.

Answer 1

당신은 두 가지 옵션이 있습니다

1. 자신의 Node 클래스를 생성하고,이 Comparable<Node> 인터페이스를 구현합니다. 이 클래스는 weight 속성을 가지며 그 무게에 따라 Node을 비교할 수 있습니다. 이렇게 Nodes의 natural ordering이 생성되어 PriorityQueue이 사용하게됩니다.

2. PriorityQueue(Comparator<? super E> comparator) 생성자를 사용하여 우선 순위 큐를 만듭니다. 두 항목을 비교하는 비교 기능 (Comparator)이 필요합니다. 따라서 노드의 가중치를 사용하여 비교할 수 있습니다 (동일한 대기열에 보관할 필요가 없습니다. 동적으로 계산되거나 별도의 데이터 구조로 유지 될 수 있습니다).