ダイクストラ法の計算量

蟻本とかにあるpriority_queueを使ったダイクストラ法の計算量の見積もりがよくわかってなかったので，メモ． 詳しい実装は蟻本を見てもらうとして，問題となるコードは大体以下の通り．

while(!que.empty()){
    P p = que.top(); que.pop(); // (1)
    int v = p.second;
    if(d[v] < p.first) cotinue; // (2)

    for(auto e : G[v]){ // (3)
        if(d[e.to] > d[v] + e.cost){
            d[e.to] = d[v] + e.cost; 
            que.push(P(d[e.to], e.to)); // (4)
        }
    }
}

まず，優先度付きキューには暫定コストと次の行き先のペアが格納されるが，これはアルゴリズム全体を考えると，このキューには高々E個の要素しか入らない． これはあるエッジは高々1回しか見ないことから言える． よってwhileループはE回しか回らない．

(1)の処理にかかる計算量は，優先度付きキューの要素がEのオーダーなので，logE．外側のwhileと合わせてO(ElogE)

(2)の処理を考えると，これは次の最短経路木に入れるノードを確定させる処理である．すなわち，これより下を通る処理はVしかない．

(3)の処理にかかる計算量は，全てのノードについて，そのノードから出る辺を足し合わせたものに等しい．エッジには端点が2個しかないことから，これも結局はO(E)で抑えられる

(4)の処理にかかる計算量は，ElogE

以上より，優先度付きキューを用いたダイクストラ法の計算量はO(ElogE) = O(ElogV)である．(E <= 2V(V-1))