DijkstraのアルゴリズムでPriorityQueueを実装するにはどうすればよいですか？

Question

私は別のクラスを作成できなかったので、Dijkstraのアルゴリズムの優先キューの実装に関して質問があります。したがって、優先度キューにノード（整数）を追加する方法を見つけようとしていますが、キューは、ノード内の重みをソートしますが、ノード自体はソートしません。例えば

、私は3つのノード（0,1,2）を有し、ノード0は、10の重量を有し、ノード1 15を有し、ノード2は、これは私を与えるべきである5

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の出力。 これは別のクラスを作成せずに可能ですか？それとも、プライオリティキューの他に私が使用できる別のアプローチがありますか？

ありがとうございます!!!!!!どんな助けも大いにありがとう！

私が考えることができる1つの解決策は、ノードを追加するたびに通常のキューをソートすることです。したがって、ノード2,0,1がキューにあり、8の重みを持つノード3を追加したい場合キューに収まるまでキューの最上位要素とウェイトを比較する必要があります。したがって、キュー内に2,3,0,1となるでしょうが、これは非効率的です。

Answer 1

は、2つのオプションがあります。

1. 独自のNodeクラスを作成し、それがComparable<Node>インターフェイスを実装します。クラスはweight属性を持ち、その重みに基づいてNodeを比較できます。これによりNodesのnatural orderingが作成され、PriorityQueueが使用されます。

2. PriorityQueue(Comparator<? super E> comparator)コンストラクタを使用して優先度キューを作成します。 2つの項目を比較する比較機能（Comparator）が必要です。したがって、ノードの重みを使用してその関数を比較することができます（同じキューに保持する必要はありません。動的に計算されるか、別のデータ構造に保持されます）。