全点対間最短路 (Johnson)

説明

負辺がない場合の全点対間最短路問題には Dijkstra 法をすべての頂点から走らせる O( VE log V ) のアルゴリズムがある．Johnson のアルゴリズムは，負辺がある場合にも一度 Bellman Ford を実行することで負辺を消去するポテンシャルを得て，上記のアルゴリズムを走らせるものである．

具体的には次のように行う: グラフ g に対し超頂点 s を追加したグラフを考える．s からすべての頂点に重み 0 の辺を張ってそれを始点とする Bellman Ford を行い，得られた距離を h とする．次にすべての辺 (u,v) の重み w を w' = w + h[u] - h[v] と置き換える．これによって任意の (u,v) に対して重み w' >= 0 が成立するので，すべての点から Dijkstra を実行するアルゴリズムが実行できる．こうして得られた結果を d(u,v) = d'(u,v) - h[u] + h[v] によって重みを変更する前の距離に変換する．

計算量

• 前処理 O(V E)．
• 中間処理 O(V E log V)．
• 後処理 O(V^2)．

ソースコード

bool shortestPath(const Graph &g,
    Matrix &dist, vector<vector<int> > &prev) {
  int n = g.size();
  Array h(n+1);
  REP(k,n) REP(i,n) FOR(e,g[i]) {
    if (h[e->dst] > h[e->src] + e->weight) {
      h[e->dst] = h[e->src] + e->weight;
      if (k == n-1) return false; // negative cycle
    }
  }
  dist.assign(n, Array(n, INF));
  prev.assign(n, vector<int>(n, -2));
  REP(s, n) {
    priority_queue<Edge> Q;
    Q.push(Edge(s, s, 0));
    while (!Q.empty()) {
      Edge e = Q.top(); Q.pop();
      if (prev[s][e.dst] != -2) continue;
      prev[s][e.dst] = e.src;
      FOR(f,g[e.dst]) {
        if (dist[s][f->dst] > e.weight + f->weight) {
          dist[s][f->dst] = e.weight + f->weight;
          Q.push(Edge(f->src, f->dst, e.weight + f->weight));
        }
      }
    }
    REP(u, n) dist[s][u] += h[u] - h[s];
  }
}
vector<int> buildPath(const vector< vector<int> >& prev, int s, int t) {
  vector<int> path;
  for (int u = t; u >= 0; u = prev[s][u])
    path.push_back(u);
  reverse(ALL(path));
  return path;
}

Verified

• ...