ホームに戻る
ベルマンフォード
// 通常はダイクストラを使うほうが処理が早い。
// ただし、ダイクストラは負のコストに対応していない。
// よって、負のコストがある場合にはベルマンフォードを用いる。
// ただし、負の閉路がある場合は無限ループする(永久にコストを減らせるので)。
// 負の閉路があれば検出して終了する方法もある。
// 計算量O(E*V)。
// グラフにおいて start 地点から i 地点への最小移動コストを求める。
// ae(from,to,cost)でエッヂを追加。
// MAX_V に最大のノード数を設定。INF は十分大きな値。
// すべてのエッヂを追加し b_ford(start,V)を呼ぶ。
// start はスタート地点、V はノードの数。
// 答えは mn[i] に存在する。
#define MAX_V 50
#define INF 1000000000
struct edge{int from, to, cost;};
vector<edge> es;
int mn[MAX_V];
void ae(int from, int to, int cost){
edge e = {from,to,cost};
es.push_back(e);
}
void b_ford(int start, int V){
for(int i = 0; i < V; i++)mn[i] = INF;
mn[start] = 0;
for(;;){
int flag = 0;
for(int i = 0; i < es.size(); i++){
edge e = es[i];
if(mn[e.from]!=INF&&mn[e.to]>mn[e.from]+e.cost){
mn[e.to]=mn[e.from]+e.cost;
flag = 1;
}
}
if(flag == 0)break;
}
}
// 負の閉路の検出
// グラフ内に負の閉路があれば処理を中断し -1 を返す。
// -1 を返した場合は mn[i] の値に意味は無いので注意。
#define MAX_V 50
#define INF 1000000000
struct edge{int from, to, cost;};
vector<edge> es;
int mn[MAX_V];
void ae(int from, int to, int cost){
edge e = {from,to,cost};
es.push_back(e);
}
int b_ford(int start, int V){
for(int i = 0; i < V; i++)mn[i] = INF;
mn[start] = 0;
for(int i = 0; i < V; i++){
int flag = 0;
for(int j = 0; j < es.size(); j++){
edge e = es[j];
if(mn[e.from]!=INF&&mn[e.to]>mn[e.from]+e.cost){
mn[e.to]=mn[e.from]+e.cost;
flag = 1;
if(i == V-1){
// 負の閉路を検出
return -1;
}
}
}
if(flag == 0)break;
}
return 1;
}