ベルマンフォード法について

間違ってたら教えてください。

ベルマンフォード法はいつ使うの?

負の大きさの辺を含んでも良いグラフについて、単一始点最短経路問題をとくアルゴリズムです。

計算量はO(VE)で、ダイクストラ法よりも遅いですが、ダイクストラ法はグラフが負の大きさの辺を含む場合には正しく動作しないので、負の大きさの辺を含む時に代わりに使うのに便利です。

どんなアルゴリズム?

その前に....

定義の説明と前提

・記号について

この記事では。グラフG=(V,E)が与えられた時、v∈Vについて、始点sからvまでの暫定の最短距離をv.d、暫定の最短路上でのvの先行点をv.πと表す。

※先行点:v1->v2のように頂点v1,v2がつながってる時,v2の先行点をv1という。ここから最短経路を復元する。

・緩和(relaxtion)

辺(u,v)の緩和はuを経由することでvへの基地の最短路を改善できるか否か判定し、改善できるならばv.dとv.πを更新すること。

要は最短経路を更新するってことだと思います。

・最短路は閉路を含まない

・負の閉路の時

負の閉路を回ることを繰り返せば、いくらでも小さい重みを持つ道を構成できるので、この実装においては不適とします。
ベルマンフォード法では、負の閉路の存在を検出できます。

・正の閉路の時
これは一般に成立します。

ある最短路cが正の閉路を含むと仮定すると、その正の閉路を取り除くことで、最短路を改善することができるので、cが最短路であることに矛盾。
故に最短路が正の閉路を含むことはない。

どんなアルゴリズム?

グラフG=(V,E)について、すべての辺を|V|-1回緩和すれば、最短路がわかるというアルゴリズムです。

なぜ、高々|V|-1回緩和すれば最短路がわかるかというと、最短路は閉路を含まないので、最短路は高々|V|-1本の辺で構成されるからです。

この問題をテストケースにしてください。
onlinejudge.u-aizu.ac.jp

サンプルソース

汚いソースコードで申し訳ないです...
C++14で動作します。上記の問題の解法となります。

#include <bits/stdc++.h>
using namespace std;
///////////////////////////////////////////
const long long int INF = INT64_MAX;
using ll = long long int; 
using Vi = vector<long long int>;
#define pb(x) push_back(x)
#define rep(i,N) for(ll i=0;i<N;i++)
template<class T>bool chmin(T &former, const T &b) { if (b<former) { former=b; return true; } return false; }
void princ(auto x){cout<<x<<" ";}; void print(auto x){cout<<x<<"\n";};
///////////////////////////////////////////////////////////////////////////////////

ll v,e,r;

struct edge{/*重み付き,有向*/
    int to , cost;/*toは接続先*/
    edge(ll to_ ,ll cost_ = 1){ to=to_; cost=cost_; };/*全てのcost=1 <=> 無向グラフ*/
};
bool operator<(edge e1 ,edge e2){return e1.cost < e2.cost; }
bool operator>(edge e1 ,edge e2){return e1.cost > e2.cost; }
using graph =  vector< vector<edge> >;
bool ch_min(graph &g,ll j,ll k,Vi &dist,Vi &from){//頂点jから出るk番目の辺の緩和
    if(chmin(dist[g[j][k].to],dist[j] + g[j][k].cost)){
        from[g[j][k].to]=j;
        return true;
    }
    return false;
}
bool bellman_ford(graph &g,Vi &dist,Vi &from,ll source){//distは最短距離,fromは先行点
    bool flag = false;
    ll siz_ = g.size();
    dist.resize(siz_); from.resize(siz_);
    rep(i,siz_)dist[i]=INF;
    dist[source]=0;
    from[source]=-1;
    rep(i,siz_)rep(j,siz_)rep(k,g[j].size()){
        if(dist[j]!=INF)if(ch_min(g,j,k,dist,from) && i==siz_-1){//chminは<(<=はだめ)
            flag = true;
        }
    }
    return flag;
}

graph gg;
Vi dis,from;


int main(){
    cin.tie(0);ios::sync_with_stdio(false);
    cin>>v>>e>>r;
    ll s,t,d;
    gg.resize(v);
    rep(i,e){
        cin>>s>>t>>d;
        gg[s].pb(edge(t,d));
    }
    if(bellman_ford(gg,dis,from,r)){
        print("NEGATIVE CYCLE");
    }else{
        rep(i,dis.size()){
            if(dis[i]!=INF)print(dis[i]);
            else print("INF");
        }
    }
    return 0;
}