重み付き有向グラフの全2点間の距離を求める Warshall–Floyd 法を python で書いてみる

ワーシャル＝フロイド法とは

今回は有向グラフの情報が与えられたとき, 全ての始点から全ての終点までの最短距離をワーシャル＝フロイド(Warshall–Floyd)法と呼ばれるアルゴリズムで求めていきます. 有向グラフの最短距離を求めるアルゴリズムのうち, ベルマン＝フォード法は以前紹介しました:
wakabame.hatenablog.com

今回紹介するワーシャル＝フロイド法では, 頂点の集合を $V$ としたとき, 任意の頂点 $i,j$ に対してその間の最短距離を一挙に計算してしまいます. その代わり, 計算量は $O(|V|^3)$ とやや大量になってしまいます.

隣接行列

グラフの情報をどのように理解するかですが, ここでは隣接行列を使って話を進めていきます(重みがない場合は, 隣接リストを用いることもあります). 隣接行列とは $|V|$ 行 $|V|$ 列の正方行列 $A=(A[i][j])_{ij}$ であり, $A[i][j]$ は頂点 $i$ から頂点 $j$ が隣接している場合の距離を辺の情報によって与えています. 後の議論のため, 頂点 $i$ から頂点 $j$ を結ぶ辺がない場合は距離を無限大として初期化されているものとしてください. 無向グラフの場合は頂点 $i$ から頂点 $j$ への距離は頂点 $j$ から頂点 $i$ への距離と常に等しいため, 対称行列となります. したがって下三角成分だけを見れば十分です.
また, 重みがない場合は辺があるなら距離は $1$ , そうでないなら距離は $0$ として実装する場合もあります.

考え方

頂点 $i$ から頂点 $j$ への最短距離を求めることを考えていきます. 残りの頂点は $|V|-2$ 個あり, その全ての順列を計算して最小のものを選んでは計算量は頂点の個数に指数関数的に比例してしまいます. そこで, 頂点 $i$ と頂点 $j$ のほかには頂点 $0$ しかないグラフを考えます. すると, このグラフの頂点 $i$ と頂点 $j$ へ移動する方法は, 頂点 $i$ から直接頂点 $j$ にいく道と, 頂点 $0$ を経由する道が考えられます. したがって最短距離は
\begin{equation}
\min{(A[i][j], A[i][0]+A[0][j])}
\end{equation}
です.
そこで, 任意の $i,j$ についてグラフの辺を緩和します.
次は頂点 $i$ と頂点 $j$ のほかに頂点 $0$ と頂点 $1$ があり, グラフの辺の情報は先ほどのステップで緩和されているものを考えます. すると, 頂点 $i$ と頂点 $j$ へ移動する方法は, 頂点 $i$ から頂点 $j$ に頂点 $1$ を経由しない道と経由する道が考えられます. したがって最短距離は
\begin{equation}
\min{(A[i][j], A[i][1]+A[1][j])}
\end{equation}
です.
ここでも, 任意の $i,j$ についてグラフの辺を緩和します.
以後はこのステップを頂点の個数分だけ繰り返していきます. pythonのコードは以下のようになります:

def Warshall_Floyd(edges,N):
  for k in range(N):
    for i in range(N):
      for j in range(N):
        edges[i][j]=min(edges[i][j],edges[i][k]+edges[k][j])
  return edges

forループが3重になっていますが, 非常にシンプルですね.

『プログラミングコンテストチャレンジブック第二版』P.98によると, ワーシャルフロイド法は一種の動的計画法とみなすことが出来ます. すなわち,
$\textrm{dp}[k+1][i][j]$
を頂点 $i$ , $j$ および頂点 $0,1,\cdots,k$ に制限されたグラフでの頂点 $i$ から頂点 $j$ までの最短距離とすると, 漸化式
$\textrm{dp}[k+1][i][j]=\min{(\textrm{dp}[k][i][j],\textrm{dp}[k][i][k]+\textrm{dp}[k][k][j])}$
が成立します. 初期化条件を,
$\textrm{dp}[0][i][j]=A[i][j]$
とし, 任意の $i,j$ について緩和した後に $k$ をインクリメントして緩和を繰り返していきます.
また, 漸化式の右辺に $\textrm{dp}[k][i][j]$ しか含まれていないことから, この動的計画法では二次元配列を使いまわしても支障なく動きます. このように上記のコードを理解することもできます.