ベルマンフォード法
ベルマンフォード法
ベルマンフォード法とは
グラフのすべての頂点に対して、ある頂点からの最短距離を求めるアルゴリズム。
ダイクストラ法と違い、辺のコストが負でもよい。
ベルマンフォード法のアルゴリズム
- スタート地点の頂点からその頂点自身への距離は 0 とし、それ以外の頂点の距離は無限大としておく。
- 以下の操作を n-1 回 (頂点数: n) 行う。最後に、以下の操作をもう 1 回行う。
- すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。
- 最後の 1 回の操作で、[終点の距離] > [始点の距離+辺のコスト] である辺があった場合、与えられたグラフに負閉路が存在する、なかった場合、負閉路は存在しない。
例と説明
ベルマンフォード法の動き (GIF)
説明
スタート地点を頂点 0 とする。
スタート地点の距離は 0 で初期化する。
この時点で、スタート地点から各頂点へ 0 ステップ (0 回の移動) で行ける経路のうち最短の距離が求められている。([0 ステップで行ける = 移動しないで行ける] なので、頂点 0 のみ行ける (距離は ０)。)
(1回目) すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。(今回は、辺 (0,1), (0,2), (0,4), (2,1), …, (4,3) の順に更新しているが、順番は関係ない。)
この時点で、スタート地点から各頂点へ 1 ステップ以下で行ける経路の最短の距離以下の距離に更新されている。(もともと各頂点で 0 ステップで行ける経路の最短距離が求められている。辺を走査すれば +1 ステップの距離がわかるため、各頂点への距離は、少なくとも 0 ステップ または 0+1 ステップで行ける経路のうち最短の距離以下には更新される。(以下としているのは、辺の走査順によっては、+2 ステップ以上調べられる場合があるからである。(例えば、辺 (0,4) のあとに辺 (4,3) を調べているため、頂点 3 は、この時点で、2 ステップかかる 0 → 4 → 3 を通る経路が最短距離となっている。)))
(2回目) 同様に、すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。
同様に、この時点で、スタート地点から各頂点へ 2 ステップ以下で行ける経路の最短の距離以下の距離に更新されている。
(3回目) 同様に、(略)。
この時点で、スタート地点から各頂点へ 3 ステップ以下で行ける経路の最短の距離以下の距離に更新されている。
(4回目 = n-1 回目) ど (ry
今回は更新がなかったみたい。
この時点で、スタート地点から各頂点へ 4 ステップ以下で行ける経路の最短の距離以下の距離に更新されている。
(最後) もう 1 回、すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。
今回は、更新がなかったので、これで最短距離が求められました。
更新があった場合、負閉路があります。負閉路とは、以下の 1 → 2 → 3 → 1 のように、コストがマイナスでループできる経路です。コストがマイナスなので、ループし続ければ無限にコストを減らせます。
なぜ、最後の 1 回 (n 回目) の操作で負閉路を見つけられるのか
そもそも、最後の 1 回 (n 回目) で更新があった場合、なぜ負閉路が存在するのか。
n 回目に更新があるということは、n ステップ以上で行ける経路が、n-1 ステップ以下で行ける経路よりコストが低い、つまり、最短経路のステップ数が n 以上ということである。
最短経路のステップ数が n 以上ということは、スタート地点を含めて n+1 頂点通る、つまり、同じ頂点を2回以上通るということである。その頂点を u とおくと、経路は、
スタート地点→ … → x0 → u → x1 → … → y0 → u → y1 → … → 更新された頂点
である (x0,x1,y0,y1 は [1 回目の u の一個前の頂点],[1 回目の u の一個後の頂点],[2 回目の u の一個前の頂点],[2 回目の u の一個後の頂点]、x0≠x1≠y0≠y1)。これが
スタート地点→ … → x0 → u → y1 → … → 更新された頂点 (同じ頂点なし)
より距離が短いということである。つまり、
u → x1 → … → y0 → u
のコストが負であるということである。経路の始点と終点が同じなので、これは負閉路であるので、負閉路が存在するとわかる。
これで、[最後の 1 回で更新がある→負閉路が存在する] は、わかったが、逆に、[負閉路が存在する→最後の 1 回で更新がある] は、いえるのか。
仮に、k 回目 (k は自然数) の操作で更新がなかったとする。更新がなかったということは、どの頂点でも距離の更新がなかったということである。操作は毎回同じなので、操作前の距離が同じなら操作の結果も同じである。つまり、k 回目に更新がないということは、k+1 回目以降も更新がないということである。これは、k 回目に更新があれば 1, 2, …, k-1 回目にも更新があったともいえる。
負閉路があれば無限にコストを減らせるので、更新がなくなることはない。つまり、毎回更新があるということである。よって、[負閉路が存在する→最後の 1 回で更新がある] といえる。
よって、[最後の 1 回で更新がある↔負閉路が存在する] なので、最後の 1 回 (n 回目) の操作で負閉路を見つけられる。
結局ソースコードは？ (C++)
\(O(|E||V|)\)
#include<bits/stdc++.h>
using namespace std;
class BellmanFord{
public:
struct Edge{ // 辺 (コストあり)
int to; // 終点
long long cost; // コスト
Edge(int to, long long cost):to(to),cost(cost){}
};
private:
const long long INF=1ll<<60; // 無限 (最短距離としてあり得ない値)
int n;
vector<vector<Edge>> g; // 有向グラフ
vector<long long> d; // 距離
vector<int> prev; // 経路復元用
public:
BellmanFord(int v):n(v),g(v),d(v,INF),prev(v,-1){} // 頂点数 v で初期化
void edge(int from, int to, long long cost){ // [始点 from, 終点 to, コスト cost] の辺の追加 (無向グラフの場合は 2 方向の辺を追加してね)
g[from].emplace_back(to,cost);
}
bool solve(int s){ // スタート地点を s として、ベルマンフォード法を実行 (負閉路があれば true なければ false を返す)
d[s]=0; // スタート地点は距離 0
for(int i=0;i<n-1;i++){ // n-1 回操作を行う
for(int j=0;j<n;j++){ // すべての辺に対して
for(auto e:g[j]){
if(d[e.to]>d[j]+e.cost){ // [終点の距離] > [始点の距離+辺のコスト] なら
d[e.to]=d[j]+e.cost; // [終点の距離] を [始点の距離+辺のコスト] で更新
prev[e.to]=j; // 1 つ前の経路を保存
}
}
}
}
for(int j=0;j<n;j++){ // 最後の 1 回
for(auto e:g[j]){
if(d[e.to]>d[j]+e.cost)return true; // 更新があれば負閉路あり
}
}
return false; // 更新がなければ負閉路なし
}
vector<long long>getD(){ // 最短距離を取得
return d;
}
long long getD(int to){ // 頂点 to への最短距離を取得
return d[to];
}
vector<int> getPath(int to){ // 頂点 to までの経路を取得
vector<int> path;
for(int cur=to;cur!=-1;cur=prev[cur])path.push_back(cur);
reverse(path.begin(),path.end());
return path;
}
};ベルマンフォード法の改良
実は、辺の走査数は約半分でいい。
アルゴリズム
- スタート地点の頂点からその頂点自身への距離は 0 とし、それ以外の頂点の距離は無限大としておく。
- 以下の操作を n 回 (頂点数: n) 行う。最後に、以下の操作をもう 1 回行う。
- 操作が[奇数]回目なら、u < v であるすべての辺 (u,v) に対して、u = 0, 1, …, n-1 の順に、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。
- 操作が[偶数]回目なら、u > v であるすべての辺 (u,v) に対して、u = n-1, n-2, …, 1 の順に、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。
- 最後の 1 回の操作で、[終点の距離] > [始点の距離+辺のコスト] である辺があった場合、与えられたグラフに負閉路が存在する。
[u < v であるすべての辺 (u,v)] + [u > v であるすべての辺 (u,v)] = [すべての辺] なので、2 回の操作ですべての辺を 1 回ずつ走査している。そのため、走査数は約半分。
なぜ？
以下のような [始点: 頂点 0, 終点: 頂点 3] の 6 ステップの経路を例として考える。
1 回目の操作では、u = 0, 1, …, n-1 の順に、u < v であるすべての辺 (u,v) に対して調べる。経路は、0 < 1 < 6 なので、辺 (0,1) の後に 辺 (1,6) が走査され、0 → 1 → 6 まで調べられている。辺 (2,5) も走査されるが、0 → 1 → 6 → 2 が調べられていないので意味ない。 (u = 0, 1, …, n-1 の順でないと、辺 (0,1) の前に 辺 (1,6) に走査される可能性がある。その場合、頂点 1 の距離が更新される前に辺 (1,6) を調べてしまうため、0 → 1 → 6 を調べたことにならない。)
2 回目の操作では、u = n-1, n-2, …, 1 の順に、u > v であるすべての辺 (u,v) に対して調べる。0 → 1 → 6 まで調べられているので、辺 (6,2) を走査することで 0 → 1 → 6 → 2 が調べられる。辺 (5,4), 辺 (4,3) は意味ない。
3回目の操作は、u < v 。2 < 5, 5 > 4 だから 1 ステップ進む。
4回目の操作は、u > v 。5 > 4 > 3 だから 2 ステップ進む。
このようなことがグラフのすべての経路で起こる。
今見た通り、u < v のときは、a0 < … < ak 、u > v のときは、a0 > … > ak であれば経路
a0 → … → ak
を、1 回の操作で調べられる。また、
a0 → … → ak → b → …
上の経路で、1 回の操作で a0 → … → ak まで調べられ、a0 → … → ak → b までは調べられなかった場合、u < v のときは、a0 < … < ak かつ ak > b 、u > v のときは、a0 > … > ak かつ ak < b である。次の操作では、u と v の符号が逆になるので、a0 → … → ak → b までは調べられる。つまり、1 回の操作で +1 ステップ以上の経路を調べられる。よって、改良前のベルマンフォード法と同じ結果を出せる。ただし、1 回目の操作においては、スタート地点が a で a > b だった場合、
a → b → …
のような経路は、+0 ステップしか調べられない。なので、ベルマンフォード法と違い、操作回数は、n-1 回ではなく n 回。(負閉路チェック用の最後の 1 回は除く。)
ソースコード (C++)
\(O(|E||V|)\)
#include<bits/stdc++.h>
using namespace std;
class BellmanFord{
public:
struct Edge{ // 辺 (コストあり)
int to; // 終点
long long cost; // コスト
Edge(int to, long long cost):to(to),cost(cost){}
};
private:
const long long INF=1ll<<60; // 無限 (最短距離としてあり得ない値)
int n;
vector<vector<Edge>> gPlus; // 有向グラフ (u < v)
vector<vector<Edge>> gMinus; // 有向グラフ (u > v)
vector<long long> d; // 距離
vector<int> prev; // 経路復元用
public:
BellmanFord(int v):n(v),gPlus(v-1),gMinus(v),d(v,INF),prev(v,-1){} // 頂点数 v で初期化
void edge(int from, int to, long long cost){ // [始点 from, 終点 to, コスト cost] の辺の追加 (無向グラフの場合は 2 方向の辺を追加してね)
if(from<to)gPlus[from].emplace_back(to,cost);
else gMinus[from].emplace_back(to,cost);
}
bool solve(int s){ // スタート地点を s として、ベルマンフォード法を実行 (負閉路があれば true なければ false を返す)
d[s]=0; // スタート地点は距離 0
for(int i=0;i<n/2;i++){ // n/2*2 回操作を行う (u < v と u > v を交互に n/2 回ずつ) (n が奇数なら u < v は 1 回足りない)
for(int j=0;j<n-1;j++){
for(auto e:gPlus[j]){ // u < v であるすべての辺 (u,v) に対して
if(d[e.to]>d[j]+e.cost){ // [終点の距離] > [始点の距離+辺のコスト] なら
d[e.to]=d[j]+e.cost; // [終点の距離] を [始点の距離+辺のコスト] で更新
prev[e.to]=j; // 1 つ前の経路を保存
}
}
}
for(int j=n-1;j>0;j--){ // u > v であるすべての辺 (u,v) に対して
for(auto e:gMinus[j]){
if(d[e.to]>d[j]+e.cost){
d[e.to]=d[j]+e.cost;
prev[e.to]=j;
}
}
}
}
if(n&1){ // n が奇数なら
for(int j=0;j<n-1;j++){ // 回数が足りてないのでもう 1 回
for(auto e:gPlus[j]){
if(d[e.to]>d[j]+e.cost){
d[e.to]=d[j]+e.cost;
prev[e.to]=j;
}
}
}
for(int j=n-1;j>0;j--){ // 最後の 1 回
for(auto e:gMinus[j]){
if(d[e.to]>d[j]+e.cost)return true; // 更新があれば負閉路あり
}
}
}
else {
for(int j=0;j<n-1;j++){ // 最後の 1 回
for(auto e:gPlus[j]){
if(d[e.to]>d[j]+e.cost)return true; // 更新があれば負閉路あり
}
}
}
return false; // 更新がなければ負閉路なし
}
vector<long long>getD(){ // 最短距離を取得
return d;
}
long long getD(int to){ // 頂点 to への最短距離を取得
return d[to];
}
vector<int> getPath(int to){ // 頂点 to までの経路を取得
vector<int> path;
for(int cur=to;cur!=-1;cur=prev[cur])path.push_back(cur);
reverse(path.begin(),path.end());
return path;
}
};SPFA (Shortest Path Faster Algorithm)
ベルマンフォード法って、頂点 u が更新されなければ、頂点 u から出ている辺を調べても前回と変わらなくない？
⇒更新された頂点から出てる辺だけ調べよう！
という話。ということでソースコードは以下。
ソースコード (C++)
\(O(|E||V|)\)
#include<bits/stdc++.h>
using namespace std;
class SPFA{
public:
struct Edge{ // 辺 (コストあり)
int to; // 終点
long long cost; // コスト
Edge(int to, long long cost):to(to),cost(cost){}
};
private:
const long long INF=1ll<<60; // 無限 (最短距離としてあり得ない値)
int n;
vector<vector<Edge>> g; // 有向グラフ
vector<long long> d; // 距離
vector<int> prev; // 経路復元用
public:
SPFA(int v):n(v),g(v),d(v,INF),prev(v,-1){} // 頂点数 v で初期化
void edge(int from, int to, long long cost){ // [始点 from, 終点 to, コスト cost] の辺の追加 (無向グラフの場合は 2 方向の辺を追加してね)
g[from].emplace_back(to,cost);
}
bool solve(int s){ // スタート地点を s として、ベルマンフォード法を実行 (負閉路があれば true なければ false を返す)
vector<bool> inQ(n,false); // 頂点がキューに入っているか
queue<int> q; // 走査する頂点
int Qnum=1; // 今回の操作で走査する頂点の数
int nxtQnum=0; // 次の操作で走査する頂点の数
d[s]=0; // スタート地点は距離 0
q.emplace(s); // スタート地点を走査する頂点とする
inQ[s]=true;
int v;
for(int i=0;i<n-1;i++){ // n-1 回操作を行う
while(--Qnum){ // 走査する頂点の数だけ
v=q.front();
q.pop();
inQ[v]=false;
for(auto e:g[v]){
if(d[e.to]>d[v]+e.cost){ // [終点の距離] > [始点の距離+辺のコスト] なら
d[e.to]=d[v]+e.cost; // [終点の距離] を [始点の距離+辺のコスト] で更新
prev[e.to]=v; // 1 つ前の経路を保存
if(!inQ[e.to]){ // 頂点がキューに入っていないなら
q.emplace(e.to); // キューに入れる
inQ[e.to]=true;
++nxtQnum; // 次の操作で走査する頂点の数を増やす
}
}
}
}
Qnum=nxtQnum;
nxtQnum=0;
}
while(--Qnum){ // 最後の 1 回
v=q.front();
q.pop();
for(auto e:g[v]){
if(d[e.to]>d[v]+e.cost)return true; // 更新があれば負閉路あり
}
}
return false; // 更新がなければ負閉路なし
}
vector<long long>getD(){ // 最短距離を取得
return d;
}
long long getD(int to){ // 頂点 to への最短距離を取得
return d[to];
}
vector<int> getPath(int to){ // 頂点 to までの経路を取得
vector<int> path;
for(int cur=to;cur!=-1;cur=prev[cur])path.push_back(cur);
reverse(path.begin(),path.end());
return path;
}
}; グラフが疎 (頂点に対して辺の数が少ない) なら、かなり高速で動くっぽい。毎回ほぼ全頂点が更新されるようなら、ベルマンフォード法と走査する辺の数が変わらないので、処理が多い SPFA のほうが遅くなることもあり得る。
終わり！
.png)
コメント
コメントを投稿