アルゴリズム・データ構造図鑑 · 基礎から応用へ

Floyd–Warshall法:経由してよい頂点を一つずつ増やす

全点対の距離を行列で更新し、経由頂点のループ順、無限大、負の閉路を理解する。

この記事をロゲイアに質問する確認問題3問に進むこれまでの誤答を復習する

更新日

この記事の目次
  1. 全点対の距離を行列に持つ
  2. AからCへの距離を更新する
  3. 負の辺と負の閉路は別
  4. 密な問題に向く費用構造
  5. この記事をロゲイアに質問する理解を確かめる

全点対の距離を行列に持つ

Floyd–Warshall法は全頂点の組について最短距離を求めます。行列d[i][j]を、直接辺の重み、同じ頂点への0、辺がない場合の無限大で初期化します。多重辺があるなら最小の重みを使い、負の自己ループを初期化で消さないようにします。k番目の段階では、経路の途中に使ってよい頂点をkまでへ広げ、d[i][k]+d[k][j]で改善できるかを調べます。単に三重ループなら何でもよいのではなく、どの集合を許した距離かが証明の中心です。

AからCへの距離を更新する

A→Bが3、B→Cが−1、A→Cが5で逆方向の辺がない例では、Bを経由してよい段階でAからCは3+(−1)=2へ改善します。CからAは到達不能のままです。無向グラフのつもりで行列を勝手に対称化すると別の問題になります。標準のその場更新では、経由頂点kを最外側に置いて、その段階の全i、jの組を更新します。iやjを最外側へ入れ替える単純な変更は、同じ不変条件を維持せず、一般に正しい全点対距離を保証しません。

負の辺と負の閉路は別

負の重みを持つ辺自体は扱えますが、負の閉路を経由できる組には有限な最短距離が存在しません。更新後にd[k][k]<0となる頂点は、負の閉路に関係しています。iからそのkへ到達でき、kからjへ到達できるなら、負の閉路を繰り返し通ることで、iからjへの経路の費用をいくらでも小さくできます。負の対角要素を見つけたからといって、到達不能な別成分まで全部同じ扱いにする必要はありません。実装が単に閉路の有無だけを報告するのか、各組を分類するのかも区別します。

密な問題に向く費用構造

V×Vの行列を保持し、各kで全てのi、jを処理するため時間O(V³)、距離行列の領域O(V²)です。経路そのものを復元するには、次の頂点や前駆頂点の行列なども用意します。無限大同士の足し算や整数オーバーフローを避ける条件を入れ、有限の二つの距離だけから候補を作ります。少数の始点や疎な巨大グラフには別の方法が適することがあります。一方、小規模で密な全点対問題では、行列の単純な更新規則が扱いやすいという利点があります。

読了と問題の結果を、言語ごとにこのブラウザへ保存します。

コースの順番に沿って学ぶ

CS基礎を固める · STEP 11

学習コースから次を選ぶ