ワーシャル-フロイド法

概要

ワーシャル-フロイド法(Warshall-Floyd Algorithm)は，重み付きグラフを入力することで，任意の２つの頂点のペアを始点と終点とする場合の最短距離とその経路を出力するアルゴリズムである．

なお，グラフは始点を除くどの頂点も始点から到達可能であるとする．

アルゴリズム

$d_{ij}$を$v_i$から$v_j$への（暫定）距離，$\mathrm{cost}(e_{ij})$を$e_{ij}$のコスト（重み）とする．

入力

頂点の集合$V$
辺の集合$E$（重みの情報も含む）

出力

任意の$i,j$に対して，$v_i$から$v_j$への最短距離とその経路

STEP1　初期化

任意の$i,j$に対して，$d_{ij}$を次のように初期化する． \begin{equation} d_{ij}=\left\{ \begin{array}{cl} \mathrm{cost}(e_{ij})&v_i\mbox{から}v_j\mbox{への辺が存在する場合}\\ \infty &v_i\mbox{から}v_j\mbox{への辺が存在しない場合} \end{array} \right. \end{equation}

STEP2　距離の更新の反復

$k=1$から$k=|V|$まで順番に以下を繰り返す．

任意の$i,j$について，$d_{ij}>d_{ik}+d_{kj}$のとき， \begin{equation} d_{ij}:=d_{ik}+d_{kj}\mbox{　（更新）} \end{equation} （$:=$はここでは「右辺を左辺に代入する」くらいの意味）

$d_{ij}\leq d_{ik}+d_{kj}$のとき（$\leq$は「小なりイコール」）は更新しない．

STEP3　終了

STEP2が終了したら，任意の２頂点の間の最短距離$d_{ij}$とその経路を出力し終了する．