プリム法だと思った？残念，ダイクストラでした！

0. 導入

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　やつを追う前に言っておくッ！
　　　　　　　　 ,. -‐'''''""¨¨¨ヽ
　　　　　　 (.＿＿_,,,... -ｧァﾌ|　　　　　　　　　あ…ありのまま今　起こった事を話すぜ！
　　　　　 |i i|　　 }!　}} /／|
　　　　　　 |l､{　　j}　/,,ｨ//｜　　　　　　　『おれはプリム法を書いていたと
　　　　　　　 i|:!ヾ､_ﾉ／ u {:}//ﾍ　　　　　　　　　　　　　　思ったらいつのまにかダイクストラが書きあがっていた』
　　　　　　　 |ﾘ u' }　 ,ﾉ　_,!V,ﾊ |
　　　　／´fト､_{ﾙ{,ィ'ｅﾗ　, ﾀ人　　　　　　な…　何を言ってるのか　わからねーと思うが
　　　　 /' 　ヾ|宀| {´,)⌒`/ |<ヽﾄiゝ　　　　　　おれも何をされたのかわからなかった…
　　　　,ﾞ　／ )ヽ iLﾚ　u' |　| ヾｌﾄﾊ〉
　　　 |／_／　ﾊ !ニ⊇　'／:} 　V:::::ヽ　　　　　　　　頭がどうにかなりそうだった…
　　　 /／二二二7'T'' ／u'　__ /:::::::/｀ヽ
　　　/'´r　-―一ｧ‐ﾞＴ´　'"´ ／::::／-‐ 　＼　　　　催眠術だとか超スピードだとか
　　 / // 　广¨´ 　/'　　／:::::／´￣｀ヽ ⌒ヽ　そんなチャチなもんじゃあ　断じてねえ
　　ﾉ ' /　ノ:::::`ー-､___／:::::／/ 　　　ヽ　　}
_／｀　/::::::::::::::::::::::::::￣`ー-{:::...　　　　　　ｲもっと恐ろしいものの片鱗を味わったぜ…

この記事は「競プロ!!」競技プログラミング Advent Calendar 2017の19日目の記事です．さて，競プロのアルゴリズムの中で比較的人気の低い（要出典）古典的アルゴリズムに，プリム法というものがあります．

プリム法

アルゴリズムの概略を説明すると，

ある頂点vを一つ選ぶ．v１つからなる集合をSとする．
Sから到達可能なS以外の頂点のうち，もっとも近い頂点を選び，これをSに加える．
2を実施できる限り2を繰り返す．実施できなくなった時にSがもとのグラフの最大全域木になる

という，証明はさておき標語的にはすごく分かりやすいアルゴリズムです．

コードで書くと（細部は適当ですスミマセン）

class edge{
    int from;
    int to;
    int cost;
}

// 最小全域木を構成する辺のリストを返すメソッド
List<edge> MinimumSpanningTree() {
    PriorityQueue<edge> Q;    // 優先度つきキュー(edge のコストが小さい順に取り出せる）
    bool[] used;              // Sに含まれたかをbool で持つ
    int[] min;                // min[v] は 各タイミングでのSからvへの最小cost
                              //  全要素をinfで初期化しておく
    Edges[] E;                // E[v] には vを始点とするedge (from := v, to, cost) が入っている
    
    used[v0] = true;
    min[v0] = 0;
    foreach(edge e in Edges[v0]) {
        Q.Enqueue(e);
    }
    
    List<edge> MST;    // Sに追加する際に張った辺を入れるリスト
    int tot =  0;      // 各時点での Sを構成するcostの合計
    
    while(!Q.IsEmpty) {
        edge e    = Q.Dequeue();
        int  from = e.from;
        int  to  = e.to;
        int  cost = e.cost
        if(used[to] == true) continue;    //行き先が既にSに含まれている場合は何もしない
        
        used[to] = true;
        min[to] = tot + cost;
        MST.Add(e);
        
        foreach(edge e in Edges[nxt]) {
            if(!used[e.to]){
                Q.Enqueue(e);
            }
        }
    }
    return MST;
}

ところが，このプリム法のコードがダイクストラ法のコードに似ていることが，しばしば話題になることがあります．

class pair{
    int pos;
    int cost;
}
class edge{
    int to;
    int cost;
}

// 始点 v0 からの 単一始点最小コストの全点リストを返す．
int[] Dijkstra(int v0) {
    PriorityQueue<pair> Q;    // 優先度つきキュー(pair のコストが小さい順に取り出せる）
    bool[] used;              // Sに含まれたかをbool で持つ
    int[] min;                // min[v] は 各タイミングでのSからvへの最小cost
                              //  全要素をinfで初期化しておく
    Edges[] E;                // E[v] には vを始点とするedge (to, cost) が入っている
    
    used[v0] = true;
    min[v0] = 0;
    Q.Enqueue(new pair(v0, 0);
    
    while(!Q.IsEmpty) {
        pair p    = Q.Dequeue();
        int  now  = p.pos;
        int  cost = p.cost
        if(used[now] == true) continue;    //行き先が既に最小確定している場合は何もしない
        
        used[now] = true;
        min[now] = cost;
        
        foreach(edge e in Edges[now]) {
            if(!used[e.to]){
                Q.Enqueue(new pair(e.to, min[now] + e.cost));
            }
        }
    }
    return min;
}

差分は，優先度付きキューに辺を入れて取り出すのか，経路長を入れて取り出すのか．なので，結構違うことをやっているのですが，確かに紛らわしいです．

紛らわしさと，それに比べて分かりやすく実装量ももう少し少ないクラスカル法の方が人々には好まれているような気がしますが，今回は記事ネタとして，そこで敢えてプリム法に迫ってみたいと思います．

1. もし，1ミリも最小全域木を求めるアルゴリズムを知らないときに，以下の問題に出会ったら

N 個の頂点からなるグラフが与えられる．各頂点間にはコストを持つ辺がある．

このグラフの辺をいくつか選び，N個の頂点が連結になるようにしたい．

コストの総和を最小にしたいとき，その最小値を求めよ

制約　N ≤ 15, 辺のコスト ≤ 100000

さて，まず考察すると

N頂点なのでN-1回つなぐのが最小コストを実現する必要条件．木になるね．
あるk頂点の木があったとして，k+1番目の頂点を追加するとしたら，一番短い辺でつなげばよさそう．
頂点をつないでいく順番で，出来上がる木は違ってそうだけど，k+1番目をつなぐのに際してはそれは関係ない．
k頂点の木がどの頂点で構成されているかだけが問題になりそう．
制約，Nが小さいな．ビットで管理すればいいか．

というような感じで，下図をみます．右側のようなコスト付きグラフを与えられたときに，最大全域木を見つけに行くためにこのようなDAGを考えることができます． f:id:kuuso1:20171226011756p:plain

さて今回の本題，ここでダイクストラをやってみます．プリム法に則って，最初にひとつ頂点を選ぶところは今回は頂点0を選んだところからスタートします． f:id:kuuso1:20171226012319p:plain

各頂点から次の頂点に向かう辺は，DAG上では1本になっていますが，実際には集合 $\{ V_i | i = 1, \dots ,k \}$ から $\{ V_i | i = 1, \dots ,k, k+1 \}$ に向かうDAG上の辺コストは $\{ V_i | i = 1, \dots ,k \}$ の各頂点から $V_{k+1}$ に伸びる元のグラフの辺の最も短い辺コストになっています．では実際にやってみますと，

ダイクストラ法は最小コストとなるノードが確定していくアルゴリズムで，赤で囲まれたノードが各ターンでの確定ノードです．真に最小値が更新されたときに各ノードのコストが青字になっています．最小全域木が確かに求まっています．

2. 考察が埋まらなかった．

上のダイクストラによって各ノードが確定していく様子を見ているとあることに気づきます．

最小コストは1度しか真に更新されない

一番近いところを選んでいけばいいというプリム法が成り立つことから考えると，これは確かに当たり前なのですが，逆に考えるとこの性質がグラフの構成法から従うことが示せれば，つまりプリム法は冪集合DAG上のダイクストラが凄くうまくいく性質を持っていると言えるので，「いやープリム法書くつもりがダイクストラ書いちゃってたわー冪集合上でドヤァ」と言える気がしたのでした．

結局これは正しいとは思うのですが，explicitな証明がつけられなかったのというのが今回大失敗だったという記事でした．なんという低クオリティ．

3. 蛇足：プリム法で得られる最小全域木のサイズが初期値 $V_0$ に依らない説明

とはいっても，上のダイクストラで最小全域木が求まるということは依然として正しい（ただし計算量がアレ）なので，それを使ってプリム法の初期値が何でもいいということだけ説明しておこうと思います．

f:id:kuuso1:20171226020354p:plain

さて， $\phi$ から1つ頂点を選ぶのをコスト0の辺であらわしていますが，この冪集合DAG全体でダイクストラをしても，結果は1つに定まります．そして，そのようにして得られた最小全域木を経路復元で一つ決めます．全体でダイクストラした場合は以下のようになります． f:id:kuuso1:20171226025203p:plain

さて，これは最初の1頂点 $v_0 = 1$ から始めた場合の初期値＝頂点1バージョンとみなすこともできます．そこで，他の頂点 $v_i$ に対して，もしこの全体ダイクストラで終点=最小全域木から出発して，ノード $\{v_i$ \}を経て $\phi$ に戻るような経路復元ができるならば，その $v_i$ を初期値にして求めた最小全域木のサイズは元の最小全域木のサイズに一致します．

これは実は簡単にできます．最初に $v_0$ から作った最小全域木の根として $v_i$ を選び，あとは葉となっているノードを切り離していくことを考えると，このような辺の選び方に対応するDAGの経路は必ず存在するからです．上の絵では，例えば最後に追加された頂点は2ですが，0を取り除いて11110に移動することもできる，という具合です．根は最後まで取り除かれないので，求める復元経路が得られたことになります．これによって，プリム法が初期値に依らないことが示せたことになります．