単一始点最短路 (Bellman Ford)

説明

Bellman Fordは負辺があってもかまわない場合の単一始点全点間最短距離を求め，同時に負閉路の存在を検出するアルゴリズムである．

これは動的計画法に基づくアルゴリズムで，k 回目の更新によって始点から k ステップ以下で進む場合の最短距離が計算される．もし n 回目にもまだ更新があるのならば，経路はどこかに負の閉路を含んでいるので，その頂点への経路には負閉路が存在するとして距離を負の無限大に設定する．

計算量

O(V E)．

使い方

const Graph &g

グラフ．

int s

始点．

vector<Weight> &dist

各頂点までの距離が入る．経路に負閉路を含む場合，負の無限大となる．

vector<int> &prev

最短路木の親頂点が入る．

戻り値

負閉路が存在しない(グラフが正常)のとき true，そうでないとき false．

ソースコード

bool shortestPath(const Graph g, int s,
    vector<Weight> &dist), vector<int> &prev) {
  int n = g.size();
  dist.assign(n, INF+INF); dist[0] = 0;
  prev.assign(n, -2);
  bool negative_cycle = false;
  REP(k, n) REP(i, n) FOR(e,g[i]) {
    if (dist[e->dst] > dist[e->src] + e->weight) {
      dist[e->dst] = dist[e->src] + e->weight;
      prev[e->dst] = e->src;
      if (k == n-1) {
        dist[e->dst] = -INF;
        negative_cycle = true;
      }
    }
  }
  return !negative_cycle;
}
vector<int> buildPath(const vector<int> &prev, int t) {
  vector<int> path;
  for (int u = t; u >= 0; u = prev[u])
    path.push_back(u);
  reverse(path.begin(), path.end());
  return path;
}

Verified

• UVA 10449