ホームに戻る
ベルマンフォード

// 通常はダイクストラを使うほうが処理が早い。
// ただし、ダイクストラは負のコストに対応していない。
// よって、負のコストがある場合にはベルマンフォードを用いる。
// ただし、負の閉路がある場合は無限ループする(永久にコストを減らせるので)。
// 負の閉路があれば検出して終了する方法もある。

// 計算量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;
}

inserted by FC2 system