ベルマンフォード法について　～負閉路の扱い～

グラフの単一始点最短経路問題を解くアルゴリズムとして、ベルマンフォード法が知られている。ダイクストラ法と比較すると、計算量を犠牲にして、コストが負の辺にも対応させたというような格好になっている。コストが負の辺は、単にコストが負というだけならあまり厄介ではないのだが、グラフにコストの総和が負である閉路（以下負閉路）を存在せしめるときに厄介な存在になる。この扱いについて軽くまとめる。

ベルマンフォード法とは

まず、簡単にベルマンフォード法についての説明をする。ベルマンフォード法は、辺を1本ずつ見て、この辺を使ったときに始点から辺の終点へのコストをより小さくできるかを確認していくアルゴリズムである。これをコストの更新が完了するまで繰り返すことで、始点からの最小コストを求めることができる。負閉路に関して、以下の4つのケースが考えられる。

Case 1 負閉路が存在しない場合

これは更新がなくなるまでループを回せばよい。蟻本95ページの中程に載っている実装で十分である。

Case2 負閉路が存在する可能性があり、それを検出したい場合

負閉路が存在するとき、更新がなくなるまでループを回そうとすると、いつまでも更新が止まらなそうである（実際はオーバーフローで止まるかも・・・？）。なので、工夫が必要である。負閉路が存在しないとき、任意の頂点から他の任意の頂点への最短路に含まれる辺の数は、頂点数をVとして高々V-1である。したがって、コストを格納する配列を0で初期化し、ループ回数をカウントし、V回目の更新が起きるかどうかを調べればよい。蟻本95ページ～96ページにかけて掲載されている実装で十分である。

Case3 始点から到達可能な負閉路が存在する可能性があり、それを検出したい場合

始点から到達可能な負閉路が存在するかどうか調べたいときは、コストを格納する配列を始点以外は十分大きい数で初期化しておくとよい。これでV回目の更新が起こるかどうかを調べる。蟻本95ページをぐりぐり読み込むと、中程に載っている実装にV回目の更新が起こるかどうかの判定を加えるだけで実装できることがわかる。

Case4 始点から到達可能であり、終点へ到達可能な閉路がある可能性があり、それを検出したい場合

この記事を書いた理由はこれを書きたかったからである。蟻本にも載っていないし、私のgoogling力が低いのか記事があまり見当たらない（あったら教えてください）（個々の問題に対しての記事ならいくつか存在を確認している）。
このような負閉路は

始点から到達可能である
負閉路中のいずれかの頂点から終点へ到達可能である

という2つの条件を満たす。これを検出するにはどうすればよいか。始点から到達可能な負閉路はCase3で述べたとおり、V回目の更新が起こるかどうかを調べればよい。そこから特定の終点への最短路に含まれる辺の数は高々V-1本であるため、全体としてはV回目から2V回目までのループ中に終点の更新が起こるかどうかを調べればよさそうである。しかし、これは間違いである。というのも、以下の図のようなグラフを考えるとわかる。

頂点1を始点、頂点5を終点とする。頂点数は5であるから、10回ループを回すことになる。1回目のループで頂点5の最小コストは-10000000となる。2→3→4→2は重みの総和が-1の負閉路であるが、この負閉路を10回通るとその重みの総和は-10である。これでは到底頂点5の更新が起こり得ず、失敗してしまう。
解決する方法は3つ考えられる。

負閉路の伝播専用の配列を作る
終点へ到達可能な頂点およびそのような頂点のみを結ぶ辺を予め調べ、Case3に帰着する
V回目以降の更新ではその頂点のコストを十分小さい値にして、V回目から2V回目までのループ中に終点の更新が起こるかどうか調べる

1つ目の方法の解説はここでは省略する。また、2つ目はCase3を参照すればよいため、3つ目についてのみ述べる。V回目の更新である頂点のコストを十分小さい値にしたとする。V回目の更新が起こったため、その頂点へは始点から到達可能な負閉路から到達可能である。その頂点から到達可能な頂点のコストは、以降のV-1回の更新の間に十分小さい値に更新されるはずである。ここで終点の更新が起こる場合は、先ほどの負閉路から終点へ到達可能である。よって、この方法で条件を満たす閉路を調べることができる。実装は以下の通りである。
GitHub - https://github.com/mhrb-minase/competitive_programming/blob/master/Graph/bellman_ford.cpp

#include<vector>
#include<algorithm>
using namespace std;

// 辺を表す構造体
struct edge{
    int from, to;
    long long cost;
};

// v:=頂点数 es:=辺の集合 cost:=始点からの最短経路のコストを格納する配列
// s:=始点(指定しなければ頂点0) g:=終点(指定しなければ頂点v-1)
// 始点から到達可能で、かつ終点へ到達可能な負閉路が検出された場合falseを、それ以外の場合trueを返す
bool bellman_ford(int v, const vector<edge>& es, vector<long long>& cost, int s = 0, int g = -1){
    if(g == -1){
        g = v - 1;
    }

    constexpr long long INF = 1LL << 61;

    cost.assign(v, INF);
    cost[s] = 0;

    for(int i = 0 ; i < v * 2 ; ++i){
        for(auto& e : es){
            if(cost[e.from] < INF && cost[e.from] + e.cost < cost[e.to]){
                if(i >= v - 1 && e.to == g){
                    return false;
                }else if(i >= v - 1){
                    cost[e.to] = -INF;
                }else{
                    cost[e.to] = cost[e.from] + e.cost;
                }
            }
        }
    }

    return true;
}

正直1つ目の方法や2つ目の方法で十分な気がするが、既存のライブラリに少し手を加えるだけでできるということに3つ目の方法の利点を見出すことにしておく。

橋梁管理日誌

日誌と言いながら日次での更新はされない模様