ei1333's page

ホーム > Wiki

全点対間最短路(Warshall-Floyd)

説明

隣接行列で表されるグラフの全点間最短路を求めるアルゴリズム。負辺路が存在する場合はそれも検出する(ある頂点 $k$ から $k$ への最短路が負ならば負閉路が存在)。

使い方

隣接行列 $g$ の各要素は最初に $INF$ で初期化しておく必要がある。ただし $INF \ge 2^{30}$ のときオーバーフローするので注意。

計算量

$O(V^3)$

$V$: 頂点数

実装例

templete< typename T = int >
void Warshall(vector< vector< T > > &g)
{
  for(int k = 0; k < g.size(); k++) {
    for(int i = 0; i < g.size(); i++) {
      for(int j = 0; j < g.size(); j++) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}

応用 1: 辺の追加

現在のグラフに辺を追加する場合に限り, 更新を$O(N^3)$ ではなく $O(N^2)$ で行える. 追加した辺に影響する範囲のみを更新するようにする.

template< typename T = int >
void AddEdge(vector< vector< T > > &g, int s, int t, T cost)
{
  g[s][t] = g[t][s] = min(g[s][t], cost);
  for(int k : {s, t}) {
    for(int i = 0; i < g.size(); i++) {
      for(int j = 0; j < g.size(); j++) {
        g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
      }
    }
  }
}

問題例

参考資料