PriorityQueue, 隣接リストを使ったダイクストラ法で困ったところ(java)

プログラミングの練習をと思って始めた競技プログラミングが案の定練習になる。

学んだこと

• PriorityQueueの使い方
• Comparatorインターフェースの使い方
• Cloneableインターフェースの使い方

以上に関して困った点とその解決。

やりたかったこと

ALDSの最小経路木問題Cを解こうとした。
隣接リストを使ったダイクストラ法。

例えば以下の画像のようなテストケースが与えられて、各ノードに0番ノードからたどり着く最短の距離を出力する。0は距離0,1は距離1,3は距離5などとなる。

手順

0を距離0で探索済みのノードとして初期化。探索済みのノード群から一番近い未探索ノードを探索していくループ。未探索ノードを1つ探索済みにすると、そこに隣接したノードの最短距離が変わりうる。従って、各ノードの距離を更新しながら探索していく。画像の場合は0→1→2→5→4→3→6→7→8の順で探索済みになり、例えば3は距離13(0探索後)→5(4探索後)と更新される。

1. 以下のプロパティでNodeクラスを定義

   class Node{
       int id;            //ノード番号
       int d=INFTY;             //0番ノードからの最短距離←これを更新しながら求める
       int color=0;         //初期値0,探索済みの場合1
       TreeMap<Integer,Integer> child =new TreeMap<>();  //{id:辺の重さ}形式の隣接ノードリスト
   }
   

2. main()メソッド内で以下の変数を定義

   • queue: Nodeオブジェクトをdの順に格納する優先度つきキュー (困った1)
   • nodes[]: 最新状態の各ノードを保存しておく配列

3. 0の距離を0とし(nodes[0].d=0;)、優先度つきキューに入れる。現在queueには0ノードのみ入っている。

4. u=queue.poll()して選択。uを探索済みにし、隣接するノードのdが更新できるなら更新。(困った2)
   画像の図だと1回目は以下のように更新される。

   nodes[1].d=1;
   nodes[3].d=13;
   

5. 優先度つきキューに隣接ノード(未探索)を入れる。
   1回目だと、この時点でqueueにはnodes[i](i=1,3)への参照がdの小さい順に並んでいる。

6. queueからdの小さいノードを取り出して選択。以降4~6を繰り返す。 (困った3)

なぜ困ったのか？

• (困った1) PriorityQueueにオブジェクトを入れるのが下手で警告が出た(ローカルでは動作したがオンラインジャッジではコンパイルエラーになった)
• (困った2) PriorityQueueは同じオブジェクトを参照しているデータが複数入りうる
• (困った3) PriorityQueueは参照先を更新しても順序が再構築されてくれない(=順番がバラバラになる)

↓詳細

PriorityQueueにオブジェクトを入れるのが下手で警告が出た(ローカルでは動作したがオンラインジャッジではコンパイルエラーになった)

以下で正しい。これでNodeがdの小さい順にキューの先頭に格納される。

class MyComparator implements Comparator<Node>{
    @Override
    public int compare (Node n1, Node n2) {
        int d1 = n1.d;
        int d2 = n2.d;

        if (d1 > d2) {
            return 1;
        } else if (d1 < d2) {
            return -1;
        } else{
            return 0;
        }
    }
}
//以下main()メソッド内で
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

さっきまでラムダ式がおぼつかなかったので伝統あるインターフェース実装を探したところ以下のようにジェネリクスを使ってないサイトが多かったので、失敗した。

class MyComparator implements Comparator {
    public int compare (Object o1, Object o2){//処理}
}//以下main()メソッド内で
Queue<Node> queue = new PriorityQueue<>(new MyComparator());

/*Object → Nodeの型変換は安全じゃないとかなんとかとローカルで警告
    Type safety: The expression of type PriorityQueue needs unchecked conversion to conform to Queue<Node>
AOJではしっかりのコンパイルエラー
    rep/Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
*/

openjdk version "11.0.3" 2019-04-16

PriorityQueueは同じオブジェクトを参照しているデータが複数入りうる

当然といえば当然だが、これのせいで大量に同じオブジェクトがキューに入るようになってしまった。途中で

nodes[1].d=1
nodes[3].d=13;
queue.add(nodes[1]);
queue.add(nodes[3]);

となるが、その後nodes[3].d=5;と更新される。これもキューに入れて、{id=3, d=5}, {id=3, d=13}の2種類のデータをキューに入れようとした。しかし、キュー内の2つのデータは同一オブジェクトnodes[3]を参照しているので、id3で距離5のデータが2つ入るだけ。
解決自体は簡単で、同一idのノードがキューに存在したら新たにaddしないとすればよい。が、汚い(for文でキューのidを調べた)。でも次の問題があって結局これではだめだった。
sortに使ってないプロパティがキューに入ってるかどうかってどうすればいいのか。

PriorityQueueは参照先を更新しても順序が再構築されてくれない(=順番がバラバラになる)

(困った2)を解決してもこれのせいでwrong answerとなる。

nodes[2].d=2;
nodes[3].d=3;
queue.add(nodes[2]);
queue.add(nodes[3]);
queue.peek();       //取り出さずにtopを見るとnodes[2]
nodes[3].d=1;
queue.peek();       //これもnodes[2]

(ノード3(現時点ではd=5)のキュー内での位置はd=13でソートされた位置なので、ノード4を選択した後のノード選択で、3と7(d=8の位置)の二択で7がキューから取り出されてしまう)
つまり、標準のPriorityQueueは中身のプロパティを更新しながら扱うことはできない。

以下のようにして解決。
1. nodes[]は最新版(距離が最新)を管理するだけにして、キューへの格納を参照ではなくオブジェクトそのものとする
2. (困った2)で実現できなかった複数バージョンのノード管理({id=3, d=5}, {id=3, d=13}の両方をキューに入れる)が実現されているので、キューからuとして選択した時点でu.d>nodes[id]なら無視することにする。

その際にObject.clone()を使ってみたのでそれに関してメモ
Cloneableインターフェースを実装してclone()メソッドをオーバーライドしたクラスはオブジェクトが複製できる。clone()にはディープコピー(コピーするオブジェクト内のオブジェクトメンバもコピー)とシャローコピー(コピーするオブジェクト内のオブジェクトメンバはオリジナルと同じ参照)があり、以下はシャローコピー(今回はディープが必要ないので)。TreeMapオブジェクトが全オブジェクト同一のものを参照しているが、今回はここは更新しないので問題なし。

class Node implements Cloneable{
    int id;
    int d;
    int color=0;
    TreeMap<Integer,Integer> child = new TreeMap<>();  //{id:重さ}の隣接リスト

    @Override
    protected Node clone() throws CloneNotSupportedException {
    Node  node = (Node)super.clone();
    return node;
}//以下main()メソッド内で
try{
    queue.add(nodes[0].clone());
} catch (CloneNotSupportedException e){//エラー処理}

ディープコピーにするならclone()をオーバーライドするときにnode.child=this.child.clone();を追加する。

まとめ

java標準のPriorityQueueは中身のオブジェクトを更新すると一般に順序は保たれない。
ダイクストラしたいときはclone()でオブジェクトを複製して更新前のオブジェクトも全部優先度つきキューに入れ、最新状態以外のものを取り出したときは処理をスキップするような仕組みにする。