神野さんに言われました。

神野さんに言われました。

AIの勉強をしています @sesenosannko

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

常識だと思いますが、メモしておきます。

ベルマンフォード法は単一始点最短路問題をO(VE)(V:頂点の数、E:辺の数)で解くことが出来る手法です。ダイクストラ法と比較して、負の辺が含まれていても正しい解が求められることが特徴です。

ただし、始点から到達できる負閉路(含まれる辺のコストの和が負になる閉路)が存在する場合はいくらでもコストを小さくすることができるので、解を求めることはできません。そのため、負閉路を検出する必要があります。

以下のように(蟻本に書いてあるように)グラフを構成してベルマンフォード法を書いたとします。

#include<iostream>

using namespace std;

#define REP(i, n) for(int i=0; i<n; i++)
#define ll long long

struct edge{
    int from, to;
    ll cost;
};

ll INF = 10e17;
edge es[2000];
ll d[1000];
int V, E;

void shortest_path(int s){
    REP(i, V) d[i] = INF;
    d[s] = 0;
    REP(i, V){
        REP(j, E){
            edge e = es[j];
            if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;
            }
        }
    }
}

閉路を求める方法として、蟻本では以下のような方法が紹介されていますが、これを使うときは注意が必要です。

蟻本に明記されている通り、このコードは始点から到達可能か否かにかかわらずグラフ内に負閉路が存在すると真が返されます。問題において単一始点からの距離を求めたいだけであれば、到達できない負閉路を検出する必要はありません。

// type A
bool find_negative_loop(){
    REP(i, V) d[i] = 0;

    REP(i, V){
        REP(j, E){
            edge e = es[j];
            if(d[e.to]>d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;

                if(i == V-1) return true;
            }
        }
    }
    return false;
}

到達出来る閉路のみを求めたい場合はどうすれば良いでしょうか。

到達可能な負閉路が存在しない場合の最短路は最大でもV-1個の辺から成るのでV-1回の更新によって到達可能な頂点への最短距離が求められることがわかります。しかし、到達可能な負閉路が存在する場合は何回でも更新が起こるので、V回目の更新が発生します。よって、上記のベルマンフォード法の関数でV回目の更新が起こったら真の値を返すようにしておけば閉路を検出することができます。

// type B
bool shortest_path(int s){
    REP(i, V) d[i] = INF;
    d[s] = 0;
    REP(i, V){
        REP(j, E){
            edge e = es[j];
            if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;

                if(i == V-1) return true;
            }
        }
    }
    return false;
}

これで解決といいたいところですが、まだ注意すべき場合があります。それは、目的地が決まっている場合です。

ベルマンフォード法は到達可能な負閉路が存在しなければ単一始点から任意の点への最短距離を求めることができますが、ある点への最短距離が知りたいだけであれば到達可能な負閉路が存在していても距離を求めたい点が負閉路に含まれていない場合は正しく最短距離を求められます。

ある点が負閉路に含まれる場合は、高々V-1回の更新によって到達可能な全ての点への最短距離が求められたのちに、高々V回の更新によって再度その点の最短距離が更新されることになります。よって、V回目から2V回目の更新で目的地の最短距離が更新されなければ目的地を含む負閉路は存在しないことが分かります。よって、この場合には以下のコードによって負閉路を検出することができます。

// type C
bool shortest_path(int s, int t){ // t: destination
    REP(i, V) d[i] = INF;
    d[s] = 0;
    REP(i, 2*V){
        REP(j, E){
            edge e = es[j];
            if(d[e.from]!=INF && d[e.to]>d[e.from] + e.cost){
                d[e.to] = d[e.from] + e.cost;

                if(i>=V-1 && e.to==t) return true;
            }
        }
    }
    return false;
}

実際のグラフに対しては以下のように判定されます。いずれも始点が1、目的地が7です。

  • typeA:負閉路あり
  • typeB:負閉路なし
  • typeC:負閉路なし

f:id:sesenosannko:20170901214110p:plain

  • typeA:負閉路あり
  • typeB:負閉路あり
  • typeC:負閉路なし

f:id:sesenosannko:20170901214047p:plain

考えてみると当たり前ですが、問題を解くときに間違えないようにしたいですね。僕はさっき間違えました。