二種類のDijkstra法とグラフの負辺

最近，最短路アルゴリズムについて新しく知ったことがあるのでメモ．内容にそんなに自信はないので間違っているかも．

グラフ $G=(V, E)$ 上の二点間の最短路問題と言えば

辺の長さが全て非負→Dijkstra法
負の長さの辺がある→Bellman-Ford法

というような使い分けを行うことが常識になっていると思います． Bellman-Ford法の計算量は $O(|V||E|)$ ，Dijkstra法の計算量は二分ヒープを使って $O(|E| \log |V|)$ なので，条件さえ満たされればDijkstra法を使いたいわけです．

さて，この記事の主題は「負辺があるグラフにDijkstra法を使うとどうなるのか？」ということです．

まず，僕は最近知ったのですが，Dijkstra法の実装の方法には大きく分けて二つの方法があります．

Dijkstra1

一つ目の実装は以下です．

const int INF = 1e9;
const int MAX_V = 101010;

struct edge{
    int to, cost;
    edge(int to, int cost): to(to), cost(cost) {}
};

typedef vector<edge> edges;
typedef vector<edges> graph;
typedef pair<int, int> P;

vector<int> Dijkstra1(graph &G, int r){
    int V = G.size();
    vector<int> dist(V, INF);
    vector<bool> check(V, false);
    priority_queue<P, vector<P>, greater<P> > pq;
    pq.push(P(0, r));

    while(!pq.empty()){
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if(!check[v]){
            check[v] = true;
            dist[v] = p.first;
            for(int i=0;i<G[v].size();i++){
                edge e =  G[v][i];
                if(dist[e.to] <= p.first + e.cost) continue;
                pq.push(P(p.first + e.cost, e.to));
            }
        }
    }
    return dist;
}

個人的にはこの実装の方が直感的にアルゴリズムを理解しやすいです．というのも「まだ距離が確定していない頂点の中で，一番距離が短いものを確定させる→確定させた頂点から距離を伝播」という手順を全頂点の距離が確定するまで繰り返す，という動きをそのまま実装しているからです． checkという配列でその頂点までの距離が確定したかどうかを管理しています．

Dijkstra2

もう一つの実装は以下です．

vector<int> Dijkstra2(graph &G, int r){
    int V = G.size();
    vector<int> dist(V, INF);
    priority_queue<P, vector<P>, greater<P> > pq;
    dist[r] = 0;
    pq.push(P(0, r));

    while(!pq.empty()){
        P p = pq.top();
        pq.pop();
        int v = p.second;
        if(dist[v]<p.first) continue;
        for(int i=0;i<G[v].size();i++){
            edge e = G[v][i];
            if(dist[e.to] <= dist[v] + e.cost) continue;
            dist[e.to] = dist[v] + e.cost;
            pq.push(P(dist[e.to], e.to));
        }
    }
    return dist;
}

蟻本などはこちらの実装になっています．一つ目のアルゴリズムの一番大きな違いは，頂点までの距離が確定したかどうかをcheckなどの配列を用いて明に管理していない点です．こちらの方が無駄のない洒落た実装になっている気がします．

二つのDijkstra法の挙動の違い

さて，これらのアルゴリズムは辺の長さが全て非負ならば同じ解を返しますが，実は負辺がある場合は異なる挙動になります．

負閉路がない→Dijkstra1は間違った答えを返す，Dijkstra2は正しい答えを返す
負閉路がある→Dijkstra1は間違った答えを返す，Dijkstra2は停止しない

つまり，Dijkstra2は負閉路がないことさえ分かっていれば問題なく動いてしまうのです！

こういうケースは，例えば最小費用流問題を解くために残余グラフ上での最短路問題を解くときなどに現れます．最小費用流問題を解く際は，普通はポテンシャルという値を各頂点について管理し，負辺を打ち消すことでDijkstra法を適用できるようにします．しかし，負閉路がないことが保証されれば，実はDijkstra2を使えばポテンシャル管理を行わなくても問題なく正しい解を出力してしまうのです！

Dijkstra2 がうまくいかない場合

さて，それでは負辺はあるが負閉路はないことがわかっている場合ならばBellman-Ford法じゃなくてDijkstra2を使っちゃえばいいじゃん？？ってなるかというと実はそれはダメです．というのも，負閉路はなくてもDijkstra2だと指数時間かかってしまうケースが作れてしまうのです．

どういうケースかというと，辺の長さが以下のような行列 $W_n$ で表されるケースです．

$W_{2, 1} = -2$
$W_{i+1, 1} = W_{i, 1} - (2^{i-2}+1) \quad (2 \leq i \leq n)$
$W_{i, j+1} = W_{i, j} + 1 \quad (1 \lt j+1 \lt i \leq n)$
$W_{i, j+1} = 2^n \quad (1 \leq i \lt j \leq n)$

例えば $n=4$ のとき，

$W_4 = \begin{pmatrix} 0 & 16 & 16 & 16 \\\ -2 & 0 & 16 & 16 \\\ -4 & -3 & 0 & 16 \\\ -7 & -6 & -5 & 0 \end{pmatrix}$

です．このとき， $W_n$ は負閉路を含みませんが，Dijkstra2では $n$ に関して指数回の更新が必要になってしまうようです．詳しくは次の論文を参照して下さい

dl.acm.org

それに対し，Bellman-Ford法ならばちゃんと $O(n^3)$ 程度の計算量で済むので問題ありません．ということで，結局負閉路がないとわかっている場合もBellman-Ford法を使った方が良さそうです．ただ，ここで挙げたケースはかなり極端な感じがするので，普通に使う分には問題なかったりするのかもしれません（よく分からない）

まだよくわかっていない点

最小費用流問題で，最短路探索にDijkstra2を使いポテンシャルを管理しない場合，指数時間かかるケースは作れるか？（作れそう）
Dijkstra2がヤバいケースは辺の長さが $O(2^n)$ になっていたが，そこまで大きな数を使わなくてもヤバいケースは作れるか？
負閉路さえなければDijkstra2は実用的には結構速いのではないか？

何か知っていたら教えていただけるとありがたいです．

追記(2019/9/9)

Y.Y. さんが「まだよくわかっていない点」の二つ目に対して有用な意見を下さいました．ありがとうございます！

面白い記事でした
「そこまで大きな数を使わなくてもヤバいケースは作れるか？」に関して、頂点 v が pq に k 回 push されるためには dist(v) の値が k 回真に下がらないといけないので、整数値ならその値を用いて計算量が評価できそう（擬多項式時間）
実数値で収束しない例は作れるのかな？
— Y.Y.🌸 (@ygussany) September 8, 2019

負閉路が無ければ候補は有限なので、収束しないとかありえんかったわ🙃
— Y.Y.🌸 (@ygussany) September 8, 2019

確かに．この議論に従えば，辺の長さに関する多項式時間（つまり擬多項式時間）の計算量が保証できそうです．実用的にも困らない場面は多そう．

私と理論

数学の話を主に書きます