こんにちは！しゅんです！
この記事ではワーシャルフロイド法について解説しています。
ワーシャルフロイド法は負閉路を検知することができるアルゴリズムです。では実際に負閉路があるグラフに対してワーシャルフロイド法を適用するとどうなるのでしょうか。
前回の記事でワーシャルフロイド法の手順を詳しく説明したのでこの記事ではあまり詳しく説明しません。
ワーシャルフロイド法の手順はこちらの記事で解説しています！
この記事では具体例を使って負閉路があるグラフに対してワーシャルフロイド法を適用したときにどうなるのかを確かめていきます！
それではやっていきましょう！
普段は組合せ最適化の記事を書いてたりします。
ぜひ他の記事も読んでみてください！
このブログの簡単な紹介はこちらに書いてあります。
興味があったら見てみてください。
このブログでは経営工学を勉強している現役理系大学生が、経営工学に関することを色々話していきます！
ぼくが経営工学を勉強している中で感じたことや、興味深かったことを皆さんと共有出来たら良いなと思っています。
そもそも経営工学とは何なのでしょうか。Wikipediaによると
経営工学（けいえいこうがく、英: engineering management）は、人・材料・装置・情報・エネルギーを総合したシステムの設計・改善・確立に関する活動である。そのシステムから得られる結果を明示し、予測し、評価するために、工学的な分析・設計の原理・方法とともに、数学、物理および社会科学の専門知識と経験を利用する。
引用元 : 経営工学 – Wikipedia
長々と書いてありますが、要は経営、経済の課題を理系的な観点から解決する学問です。
ワーシャルフロイド法の手順
結論ワーシャルフロイド法の手順は以下のようになります。
記号の定義\(G = (V,E)\)：有向グラフ\(d_{ij}^{(k)}\)：頂点集合\(V\)の部分集合\(\{1,2,…,k\}\)のみを通れるときの、頂点\(i\)から頂点\(j\)への最短距離アルゴリズムの手順STEP 0 グラフの重み付き隣接行列を用意する（最短距離の初期値\(d_{ij}^{(0)}\)の設定）STEP 1 \(k = 1\)とし、全ての\(i,j \in V\)に対して\(d_{ij}^{(1)}\)を以下のように更新する。
\(d_{ij}^{(1)} = \min\{d_{ij}^{(0)}, d_{i1}^{(0)} + d_{1j}^{(0)}\}\)
STEP 2 \(k = 2\)とし、全ての\(i,j \in V\)に対して\(d_{ij}^{(2)}\)を以下のように更新する。
\(d_{ij}^{(2)} = \min\{d_{ij}^{1)}, d_{i2}^{(1)} + d_{1j}^{(1)}\}\)
STEP 3 \(k = 3\)とし、全ての\(i,j \in V\)に対して\(d_{ij}^{(3)}\)を以下のように更新する。
\(d_{ij}^{(3)} = \min\{d_{ij}^{(2)}, d_{i3}^{(2)} + d_{3j}^{(2)}\}\)
・ ・ ・
STEP n \(k = n\)とし、全ての\(i,j \in V\)に対して\(d_{ij}^{(n)}\)を以下のように更新する。
\(d_{ij}^{(n)} = \min\{d_{ij}^{(n-1)}, d_{in}^{(n-1)} + d_{nj}^{(n-1)}\}\)
前回の記事で詳しく説明したのでこの記事ではワーシャルフロイド法の手順の紹介だけにします。
ワーシャルフロイド法の手順はこちらの記事で解説しています！
ワーシャルフロイド法は負閉路を検知できる
上図のような負閉路を持つグラフの場合、その負閉路を通ればいくらでも距離を小さくすることができてしまうのでグラフが負閉路を持つかどうかはけっこう重要な要素なんです。
ワーシャルフロイド法は負閉路を検知することができます。どうやって検知するかと言うと
「得られた答え（行列）の対角成分に負の値を持てば負閉路を持つ」
という風に検知することができます。文字だけだと分かりづらいので具体例を使って解説します。
具体例を使って考えてみる
それでは上のグラフにワーシャルフロイド法を適用してみましょう。上のグラフは頂点→頂点2→頂点3→頂点1の負閉路を持ちます。
辺\((1,2)\)の重み：1
辺\((2,3)\)の重み：2
辺\((3,1)\)の重み：-4
よって閉路1→2→3→1の重みは
\(1+2-4=-1<0\)
となるのでこの閉路は負閉路となります。
STEP 0
まず最初に重み付き隣接行列を用意します。重み付き隣接行列の\((i,j)\)成分は辺\((i,j)\)があれば辺\((i,j)\)の重み、なければ\(\infty\)とします。(重み付き隣接行列の\((i,j)\)成分は\(d_{ij}^{(0)}\)と一致します。)
上のグラフで言うと例えば辺\((2,4)\)の重みは4なので行列の\((2,4)\)成分は4となります。逆に辺\((1,4)\)は存在しないので行列の\((1,4)\)成分は\(\infty\)となります。
\(d_{24}^{(0)}=4\)
\(d_{14}^{(0)}=\infty\)
STEP 1
（上図の左側の行列の\((i,j)\)成分は\(d_{ij}^{(0)}\)を表しており、右側の行列の\((i,j)\)成分は\(d_{ij}^{(1)}\)を表しています。）
STEP 1では\(d_{ij}^{(1)}\)、つまり
「通って良い頂点が頂点1の場合における2頂点間の最短距離」
を求めていきます。結論以下の式に従って\(d_{ij}^{(1)}\)の値を決めていけばOKです。
\(d_{ij}^{(1)} = \min\{d_{ij}^{(0)}, d_{i1}^{(0)} + d_{1j}^{(0)}\}\)
変化があった成分の所だけ解説します。
始点：頂点3
\(d_{32}^{(1)} = \min\{d_{32}^{(0)}, d_{31}^{(0)} + d_{12}^{(0)}\}=\min\{\infty, -4+1\}=-3\)
\(d_{33}^{(1)} = \min\{d_{33}^{(0)}, d_{31}^{(0)} + d_{13}^{(0)}\}=\min\{\infty, -4+6\}=2\)
例えば\((i,j) = (3,2)\)について考えてみましょう。このとき
\(d_{32}^{(0)} = \infty\)
\(d_{31}^{(0)} = -4, d_{12}^{(0)} = 1\)
なので
\(d_{32}^{(1)} = \min\{\infty, -4+1\} = 3\)
となります。これは途中で通っても良い頂点が頂点1のとき、頂点3～頂点2間の最短経路が頂点3→頂点2→頂点1であることを表しています。
STEP 1で得られた行列の\((i,j)\)成分は\(d_{ij}^{(1)}\)となっており、\(d_{ij}^{(1)}\)は頂点1しか通れないときの\(i\)～\(j\)間の最短距離を表しています。つまりこの行列は
「全ての2頂点間における、頂点1しか通れないときの最短距離」
をまとめた行列となっているんです。
STEP 2
（上図の左側の行列の\((i,j)\)成分は\(d_{ij}^{(1)}\)を表しており、右側の行列の\((i,j)\)成分は\(d_{ij}^{(2)}\)を表しています。）
STEP 2では\(d_{ij}^{(2)}\)、つまり
「通って良い頂点が頂点1と頂点2の場合における2頂点間の最短距離」
を求めていきます。結論以下の式に従って\(d_{ij}^{(2)}\)の値を決めていけばOKです。
\(d_{ij}^{(2)} = \min\{d_{ij}^{(1)}, d_{i2}^{(1)} + d_{2j}^{(1)}\}\)
変化があった成分の所だけ解説します。
始点：頂点1
\(d_{13}^{(2)} = \min\{d_{13}^{(1)}, d_{12}^{(1)} + d_{23}^{(1)}\}=\min\{6, 1+2\}=3\)
\(d_{14}^{(2)} = \min\{d_{14}^{(1)}, d_{12}^{(1)} + d_{24}^{(1)}\}=\min\{\infty, 1+4\}=5\)
始点：頂点3
\(d_{33}^{(2)} = \min\{d_{33}^{(1)}, d_{32}^{(1)} + d_{23}^{(1)}\}=\min\{2, -3+2\}=-1\)
\(d_{34}^{(2)} = \min\{d_{34}^{(1)}, d_{32}^{(1)} + d_{24}^{(1)}\}=\min\{5, -3+4\}=1\)
始点：頂点4
\(d_{43}^{(2)} = \min\{d_{43}^{(1)}, d_{42}^{(1)} + d_{23}^{(1)}\}=\min\{\infty, -3+2\}=-1\)
\(d_{44}^{(2)} = \min\{d_{44}^{(1)}, d_{42}^{(1)} + d_{24}^{(1)}\}=\min\{\infty, -3+4\}=1\)
例えば\((i,j) = (1,3)\)について考えてみましょう。このとき
\(d_{13}^{(1)} = 6\)
\(d_{12}^{(1)} = 1, d_{23}^{(1)} = 2\)
なので
\(d_{13}^{(2)} = \min\{6, 1+2\} = 3\)
となります。これは途中で通っても良い頂点が頂点1と頂点2のとき、頂点1～頂点3間の最短経路が頂点1→頂点2→頂点3であることを表しています。
STEP 2で得られた行列の\((i,j)\)成分は\(d_{ij}^{(2)}\)となっており、\(d_{ij}^{(2)}\)は頂点1と頂点2しか通れないときの\(i\)～\(j\)間の最短距離を表しています。つまりこの行列は
「全ての2頂点間における、頂点1と頂点2しか通れないときの最短距離」
をまとめた行列となっているんです。
STEP 3
（上図の左側の行列の\((i,j)\)成分は\(d_{ij}^{(2)}\)を表しており、右側の行列の\((i,j)\)成分は\(d_{ij}^{(3)}\)を表しています。）
STEP 3では\(d_{ij}^{(3)}\)、つまり
「通って良い頂点が頂点1と頂点2と頂点3の場合における2頂点間の最短距離」
を求めていきます。結論以下の式に従って\(d_{ij}^{(3)}\)の値を決めていけばOKです。
\(d_{ij}^{(3)} = \min\{d_{ij}^{(2)}, d_{i3}^{(2)} + d_{3j}^{(2)}\}\)
始点：頂点1
\(d_{11}^{(3)} = \min\{d_{11}^{(2)}, d_{13}^{(2)} + d_{31}^{(2)}\}=\min\{\infty, 3-4\}=-1\)
\(d_{12}^{(3)} = \min\{d_{12}^{(2)}, d_{13}^{(2)} + d_{32}^{(2)}\}=\min\{1, 3-3\}=0\)
\(d_{13}^{(3)} = \min\{d_{13}^{(2)}, d_{13}^{(2)} + d_{33}^{(2)}\}=\min\{3, 3-1\}=2\)
\(d_{14}^{(3)} = \min\{d_{14}^{(2)}, d_{13}^{(2)} + d_{34}^{(2)}\}=\min\{5, 3+1\}=4\)
始点：頂点2
\(d_{21}^{(3)} = \min\{d_{21}^{(2)}, d_{23}^{(2)} + d_{31}^{(2)}\}=\min\{\infty, 2-4\}=-2\)
\(d_{22}^{(3)} = \min\{d_{22}^{(2)}, d_{23}^{(2)} + d_{32}^{(2)}\}=\min\{\infty, 2-3\}=-1\)
\(d_{23}^{(3)} = \min\{d_{23}^{(2)}, d_{23}^{(2)} + d_{33}^{(2)}\}=\min\{2, 2-1\}=1\)
\(d_{24}^{(3)} = \min\{d_{24}^{(2)}, d_{23}^{(2)} + d_{34}^{(2)}\}=\min\{4, 2+1\}=3\)
始点：頂点3
\(d_{31}^{(3)} = \min\{d_{31}^{(2)}, d_{33}^{(2)} + d_{31}^{(2)}\}=\min\{-4, -1-4\}=-5\)
\(d_{32}^{(3)} = \min\{d_{32}^{(2)}, d_{33}^{(2)} + d_{32}^{(2)}\}=\min\{-3, -1-3\}=-4\)
\(d_{33}^{(3)} = \min\{d_{33}^{(2)}, d_{33}^{(2)} + d_{33}^{(2)}\}=\min\{-1, -1-1\}=-2\)
\(d_{34}^{(3)} = \min\{d_{34}^{(2)}, d_{33}^{(2)} + d_{34}^{(2)}\}=\min\{1, -1+1\}=0\)
始点：頂点4
\(d_{41}^{(3)} = \min\{d_{41}^{(2)}, d_{43}^{(2)} + d_{31}^{(2)}\}=\min\{\infty, -1-4\}=-5\)
\(d_{42}^{(3)} = \min\{d_{42}^{(2)}, d_{43}^{(2)} + d_{32}^{(2)}\}=\min\{-3, -1-3\}=-4\)
\(d_{43}^{(3)} = \min\{d_{43}^{(2)}, d_{43}^{(2)} + d_{33}^{(2)}\}=\min\{-1, 2-1\}=-2\)
\(d_{44}^{(3)} = \min\{d_{44}^{(2)}, d_{43}^{(2)} + d_{34}^{(2)}\}=\min\{1, -1+1\}=0\)
例えば\((i,j) = (1,1)\)について考えてみましょう。このとき
\(d_{11}^{(2)} = \infty\)
\(d_{12}^{(2)} = 3, d_{23}^{(2)} = -4\)
なので
\(d_{11}^{(3)} = \min\{\infty, 3-4\} = -1\)
となります。これは途中で通っても良い頂点が頂点1と頂点2と頂点3のとき、頂点1～頂点3間の最短経路が頂点1→頂点2→頂点3→頂点1であることを表しています。
STEP 3で得られた行列の\((i,j)\)成分は\(d_{ij}^{(3)}\)となっており、\(d_{ij}^{(3)}\)は頂点1と頂点2と頂点3しか通れないときの\(i\)～\(j\)間の最短距離を表しています。つまりこの行列は
「全ての2頂点間における、頂点1と頂点2と頂点3しか通れないときの最短距離」
をまとめた行列となっているんです。
STEP 4
（上図の左側の行列の\((i,j)\)成分は\(d_{ij}^{(3)}\)を表しており、右側の行列の\((i,j)\)成分は\(d_{ij}^{(4)}\)を表しています。）
STEP 34は\(d_{ij}^{(3)}\)、つまり
「通って良い頂点が頂点1と頂点2と頂点3と頂点4の場合における2頂点間の最短距離」
を求めていきます。結論以下の式に従って\(d_{ij}^{(4)}\)の値を決めていけばOKです。
\(d_{ij}^{(4)} = \min\{d_{ij}^{(3)}, d_{i4}^{(3)} + d_{4j}^{(3)}\}\)
今回のグラフの場合は任意の\(i,j \in V\)に対して\(d_{ij}^{(3)}=d_{ij}^{(4)}\)だったので計算の説明は省略します。
STEP 4で得られた行列の\((i,j)\)成分は\(d_{ij}^{(4)}\)となっており、\(d_{ij}^{(4)}\)は頂点1と頂点2と頂点3と頂点4しか通れないときの\(i\)～\(j\)間の最短距離を表しています。つまりこの行列は
「全ての2頂点間における、頂点1と頂点2と頂点3と頂点4しか通れないときの最短距離」
をまとめた行列となっているんです。要は
「全ての2頂点間における最短距離」
を表しています。
得られた行列の対角成分を見る
それではワーシャルフロイド法によって得られた行列の対角成分を見てみましょう。上の行列を見ると、\((1,1),(2,2),(3,3)\)成分が負の値を取っていますね。これが「グラフが負閉路を持つ」サインです。
なぜ対角成分に負の値があると負閉路を持つのかは次の節で説明します。
なぜ対角成分に負の値があると負閉路を持つの？
それでは最後になぜワーシャルフロイド法で得られた行列の対角成分に負の値があると負閉路を持つのかを簡単に説明します。
上の行列の\((1,1)\)成分を見てみましょう。\((1,1)\)成分は
「頂点1から頂点1への最短距離」
を表しています。つまり頂点1を含む閉路の最短距離となります。これが負の値を取るということは
「頂点1を含む負閉路が存在する」
ということを表しています。
上のグラフだと頂点1→頂点2→頂点3→頂点1の閉路は、辺の重みの合計が-1なので負閉路となります。
ワーシャルフロイド法をあるグラフに適用したときに「そのグラフが負閉路を持つ」ことの必要十分条件は「ワーシャルフロイド法で得られた行列の対角成分に負の値がある」であることが知られています。証明しようするともっとちゃんと書かないといけないですがイメージとしては上のような感じです。
おわりに
いかがでしたか。
今回の記事ではワーシャルフロイド法と負閉路について解説していきました。
今後もこのような組合せ最適化に関する記事を書いていきます！
最後までこの記事を読んでくれてありがとうございました。
