【ワーシャルフロイド法】数学一切できない文系Fラン卒の俺が全点対最短経路問題(APSP)系のコードを解説する

#まえがき

皆さん、競技プログラミングをはじめて素数だとか約数だとか基本的な数字を出すためのロジックを勉強された後は、やっぱりいろんなかっこいい名前の付いた手法を勉強したくなりますよね。
そしてやっぱり最短経路問題とか、迷路とか、なんかかっこいい問題やりたいですよね。
でもなんかダイクストラ法とか難しそうだしなぁとか、DPってなんなんだろうなぁ、グラフ理論ってなんなんだよぉということに頭を悩ませてやる気がなくなってしまうこともあるかと思います。

というわけで、今回はアホ糞簡単なロジックで全点対最短経路問題が解けてしまうワーシャルフロイド法について解説していこうと思います。

今回は専門用語や前提知識がめっちゃ多くて難しかったですが、参考資料などは読まなくても理解できるよう勧めていければと思います。

#最短経路問題とは

グラフ理論における最短経路問題（さいたんけいろもんだい、英: shortest path problem）とは、重み付きグラフの与えられた2つのノード間を結ぶ経路の中で、重みが最小の経路を求める最適化問題である。

まぁよくわからないですよね。
グラフ理論についてはあとで軽く触れます。（というか軽くしかしらない）

簡単に言うと、いくつかの町とそれを結ぶ道があって、どの道を通ると何分かかるよというコストが与えられているわけです。
場合によっては道を通れる方向に制限があったり、時刻に制限があったり色々する中で、最短の経路を求めましょうという問題の総称がグラフ理論における最短経路問題ということです。

#最短経路問題の種類

####2頂点対最短経路問題
特定の2つのノード間の最短経路問題。一般的に単一始点最短経路問題のアルゴリズムを使用する。

####単一始点最短経路問題 (SSSP：Single Source Shortest Path)
特定の1つのノードから他の全ノードとの間の最短経路問題。この問題を解くアルゴリズムとしては、ダイクストラ法やベルマン-フォード法がよく知られている。

####全点対最短経路問題
グラフ内のあらゆる2ノードの組み合わせについての最短経路問題。この問題を解くアルゴリズムとしては、ワーシャル-フロイド法が知られている。

本当はダイクストラ法とワーシャルフロイド法を両方紹介できたらよかったのですが、ワーシャルフロイド法を理解するのに思った以上に時間がかかってしまったので今回はワーシャルフロイド法のみの解説となります。

全点対最短経路問題に対応しているので当然単一始点最短経路問題も解けるのですが、アルゴリズムの実行に時間がかかるのでTLEになったりなんなりと、結局単一始点最短経路問題はそれはそれで勉強する必要があることに注意してください。

#グラフ理論とは

グラフ理論

グラフは頂点と辺から構成され、辺は二つの頂点を結ぶものです。
つまり、○をいくつか書いて、それを線で結んだ物を想像してください。
もっと言えば、複数の場所と、それをつなげる道でできた図と考えていただければ問題ありません。

グラフはG=(V,E)として表現されます（まだ全然わからなくてOK）
V = {v, b, x, z, a, y }
E = { (b,y), (b,y), (y,v), (z,a), (x,x), (b,x), (x,v), (a,z) }
G = (V, E)

Vは頂点の集合体であり、有限集合（元の数が有限で0~nまでの数字って感じ）です。
要はすべての行きたい場所の集合で、行きたい場所は無限にあっちゃだめということです。
集合論

EはVの二項関係です。つまり、Vの要素を２つ並べたものです。どの場所からどの場所へ移動できるかということです。
二項関係

つまり、G（グラフ）はすべての頂点Vと、どの頂点からどの頂点へ移動できるかのEで表されるということです。
このとき、Vを頂点（ノード）集合と呼び、Eを辺やエッジと呼びます。

#グラフの種類

####有向グラフ

経路として移動できる方向が限られているものです。東京から大阪にはいけるが、大阪から東京にはいけないというイメージです。
uからvにしか行けないので、(u,v)だけをEに渡すことで表現できます。

####無向グラフ
経路として移動できる方向が限られていないものです。東京と大阪を行き来できることをイメージしてください。
無向グラフでは (u,v)と(v,u)両方をEに渡しておけば表現できます。
もちろん(u,v)だけで表現してもいいですが、有向グラフで実装して両方向をEとして与えるほうが実装を共通化しやすいということですね。

#ワーシャルフロイド法とは
全点対最短経路問題において、有向無向グラフどちらでも使える手法です。

事前準備として、ある頂点iから頂点jへ移動するときにかかるコストを事前に用意しておきます。
つまり、グラフのEを事前に用意しておきます。

それをもとにある頂点から移動可能なすべての頂点への移動コストを２次元リストで表現するということを実装していきます。
以下記事の「実際に確かめてみよう」の章にある表を作るイメージですね。
こちらの記事も参考になるかと思いますので良ければご覧ください。
https://qiita.com/okaryo/items/8e6cd73f8a676b7a5d75

つまり、すべてのiから移動可能なすべてのjへのコストを全部出したリストを作るということです。
全探索なので計算量が多いですが、あらゆる最短経路問題に対応できます。（速度が必要な時は、都度最適なアルゴリズムを使う必要があります。）

#DP 動的計画法とは
一発で全体最適な答えが出るわけではない問題で、局所的最適解を積み上げて全体最適となる答えを求めに行く手法のこと。
ワーシャルフロイド法もDPの一種。
ナップザック問題や、迷路などでも使われる。

#実装解説
以下の問題を例として解説します。
Python3だとTLEして、PyPyだとACしたので注意してください。
遅い言語だと通らないです。
ABC012 D https://atcoder.jp/contests/abc012/tasks/abc012_4

#n = 頂点の数
#m = 経路の数
n,m=map(int,input().split())

#float("inf")は無限を表現できる。
#到達不可能なものはコスト∞として評価する。
ans=float("inf") 

#まず二次元のリストを作り、全辺における移動コストの表を作成する。
#つまりグラフにおけるEの値だけコストを埋めたリストを作る。
#それ以外の移動コスト（頂点の中継が必要なもの）についてはいったん到達不可能=∞とする。
#コストはaからbに移動する時のものなので、インデックスをd[a][b]と表現するため二次元になっている。

#頂点の数nだけ、無限を入れたlistをn個つくる。 n=3なら[inf,infi,inf],[inf,infi,inf],[inf,infi,inf]
#無限になっているのは、コストの最大値が1000なので経路が存在しない場合はそれより大きい数字にしたいが、最大コストを求めてそれ以上にするのが面倒なので∞にしている。
d=[[float("inf") for i in range(n)] for i in range(n)] 


#まず最初に、同じ頂点同士の移動はコストがかからないので0とする。
#aからのa bからのbなど。
for i in range(n):
    d[i][i]=0

#つぎに、Eとして与えられている隣接する頂点の移動コストを入力する。
#移動経路を一つずつ取り出して、コストを入力していく。
for i in range(m):
    #バス停a,bとコストtをうけとり、バス停の数字に対応するインデックスにコストを突っ込んでいく。
    #以後、aからbへの移動コストが欲しい場合はd[a][b]で取り出すことができるようになる。
    #経路が存在しない場合、dを初期化した時点で無限が入っているので、コストは無限となる。
    #このとき、無向グラフであればd[a][b]もd[b][a]も入力するし、有向グラフであれば片方だけでよい。
    #今回は双方向の移動が可能なので、無向グラフとして実装する。
    a,b,t=map(int,input().split())
    d[a-1][b-1]=t
    d[b-1][a-1]=t

#ワーシャルフロイド法により、上で作った「隣接する頂点同士の移動コストの表」から、「全始点から全終点までの経路コストの表」を作成する。
#これもdd[a][b]の形でアクセスしたいので、２次元配列になる 例 [[0, 12, 26, 27, 18], [12, 0, 14, 21, 30], [26, 14, 0, 7, 16], [27, 21, 7, 0, 9], [18, 30, 16, 9, 0]]
#コスト0は同じ頂点同士の移動コスト。
#この関数は解説が長くなるので後述する。
warshall_floyd(d)

#最後に最悪のケースを想定しないといけないので、
#各頂点を始点としたとき最も数字が大きい値（最悪のケース）をすべて取り出し、これが最も小さい値を答えとする。
for i in range(n):
  ans=min(ans,max(d[i]))

print(ans)

以下ワーシャルフロイド関数
引用元　Pythonで競技プログラミング 〜基本的なアルゴリズム 〜

def warshall_floyd(d):
  for k in range(n):# 中継点
    for i in range(n):# 始点
      for j in range(n):# 終点
        # 繰り返し見ていくので、現時点の i から j へ向かうコスト と 今検証している k を経由して j に向かうコスト の小さい方を i から j へ向かうコストとして登録する
            d[i][j] = min(d[i][j],d[i][k] + d[k][j])
  return d

#この関数がワーシャルフロイド法。
#移動コスト一覧表dと、頂点の数nがあれば動作する。

#iとjが始点と終点で、それをすべてのkを通る形ですべての始点と終点を全検索しているのですべての経路を検証網羅している。
#この時、k（中継点）を使わないなら d[i][j] そのまま、k を使うとd[i][k] + d[k][j] が最短となる。
#（ぜんぜんわからん）

#私はこれだと理解できなかったので、もう少し解説する。

#【中継点kって一つだけにしか対応していないの？】
#中継点はいくつあっても対応しています。
#このロジックはAから直接移動できる場所へのコストをすべてだして、Bから直接移動できる場所へのコストをすべてだして...AからBを経由してCに移動するコストを出して...
#という順にコストを割り出していくんですが、この時すべての中継点を通る組み合わせで何度も同じ始点iから終点jまでの経路を検証していきます。
#そうすると、最初の１回目はAから直接移動できる範囲までのコストしか割り出せなかった状況が変わります。
#
#例えば、AからB、BからC、CからDに移動できることがわかっているとします。
#そのあとに中継点を通るルートの検証を開始します。
#BからCを経由してDという経路を検索した際、BとDは直接つながっていませんので最初の検証ではコストを算出できませんでしたが、
#中継点Cを通る検証を行うときには、Cから直接移動できる場所へのコストが明らかになっているので、BDのコストを算出することができます。
#このBDのコストはd[B][D]に代入されますが、後の検証でCを中継する場合が6で、Eを中継する場合が5というように最短経路の更新が入った場合はd[B][D]も更新されます。
#これを続けていくと、A(i)からB(k)を経由してD(j)というルートの検証は、最初はAからDを直接移動できなかったので見ることができませんでしたが、
#BDのコストが算出された前提であれば算出することができます。
#このとき、中継点kとして与えられるのはBですが、BDのコストはCやEを経由することが含まれた上での最短経路となっているため、このロジックで複数の中継点に対応できていることがわかります。

#【i,jを求めるタイミングで中継点って常に最短になるの？】
#疑問をもう少しちゃんと表現します。

# 例えばABCDEの頂点があり、DからしかアクセスできないEがあり、AEを求めたいとします
# 始点A 中継点D 終点E を求めるタイミングで、AD=A→C→Dが最適であるとわかっていない場合、AからDに隣接していないのでたどり着けず中継点= DのときのAE=∞になります。
# 始点A　中継点B　終点Eのときには、ABが隣接しているため移動できますが、BE=B→C→D→Eが最適であるとわかっていない場合Eにたどり着けないので中継点= BのときにAE = ∞になります
# 始点A　中継点C　終点EのときにもACは移動できますが、CE=C→D→Eが最適であるとわかっていない場合にたどり着けないので中継点= CのときにAE = ∞になります
# 当然AやEが中継点でも同様です。
# 上記の検証の後にBEやAD、CEが求められたとしても、もう一度同じ中継点でAEを評価するタイミングが無ければ答えを出すことができません。
# AEのときにはわからなくても一周してEAの時にわかるかもしれないと思うかもしれませんが、有向グラフの場合復路が許容されないので判別することができない可能性があります。
#
#解説　https://www.slideshare.net/chokudai/abc012　スライド44～
#スライドの例にあわせて、AB（最短経路A→C→F→D→E→B）を求めたいとする。
#まず、ワーシャルフロイドはすべての中継点を起点として、すべての始点終点を全探索する実装である
#ABの最短経路を探索する場合、中継点A~Fそれぞれを経由する場合のABを毎回確認している。Aを経由するAB Bを経由するAB Cを経由するAB...
#当然最初は中継点の最短距離がでていないため、AからBにたどり着くことすらできない。
#ただし、ABの最短距離において中継点はCFDEがあるわけなので、
#ABの最短経路を確認するには、一番最後に見る中継点FのABを見るときに、それ以外の経路が最短になっていれば問題ない。
#
#では、中継点Fを終点として経路を確認してみよう。
#最短経路をABではなくAFの観点から見てみと、ACFとなりACもAFも直接移動できるので、中継点Cを見たタイミングでAFの最短経路が求まっていることがわかる。
#つぎにFBをみてみると、これは複数経由しているので難しく見えるが、AFBと考え方は同じでもう一度分解して直接移動できる範囲を見ていけばいい。
#FDEはDの中継点を見た時点で求まっているし、DEBもEの中継点を見た時点で求まっている。
#これにより、Fの中継点を見るタイミングで、Fより前の最短経路は求まっていることが証明できる。
#つまり、ある経路ABの最短経路を求める場合、ABのなかで一番最後に確認する中継点を検証するタイミングで、
#それ以前にでてくる中継点については最短経路が求まっているといえる。
#これにより、【i,jを求めるタイミングで中継点って常に最短になるの？】で定義した疑問でAEをみる時、
#その中継点BEやAD CEは、中継点Dを見る時点で時点で最短経路が出ているので、ADEを検証する時にAEの最短経路を求めることが可能となっていると証明できる。

#【kijのループ順番を間違えても上手く動くの？】
#例えばikj jikなど
#
#解説 https://qiita.com/tmaehara/items/f56be31bbb7a468a04ed
#うごかないけど最大３回繰り返せば上手く動くらしい。
#とりあえず中継点を全て求める必要があるから、中継点を一番外側のループに置く必要があると覚えておくこと。

#　あとがき

ワーシャルフロイド法ってただの３重ループなのに、これが本当に問題ないのかを理解するためにどんだけ知識がいるんや...

今回は理系の知り合い３人くらい動員して数日かかって理解しました。
もはや自分が何をわかっていないのかを言語化するだけでも苦労して、みんなには迷惑をかけたなぁと思います。
いや本当いま学生でじぇんじぇん勉強していない奴がいたら言いたい。

勉強しないならエンジニアにはなるな！！死ぬぞ！！

エンジニアはすごいですね。
アルゴリズムを理解する数学力、ロジックを理解する論理的思考能力、自分の疑問や理解を伝える国語力、グローバルなドキュメントにアクセスするための英語力に読解力...すべてを兼ね備えたスーパーマンなんだなぁと思いました。
僕もスーパーマンでありたいと思ったけど、今の感じじゃサイドキックにしかなれなさそうだ。

あとこれはどうでもいいんですけど、先週勉強して、ちょうどその週のABCに出た問題が最短経路問題だったんで、C問題飛ばしてついつい解こうとしちゃったんだけど、開始即あぁこれ単一始点最短経路問題だからダイクストラ法だってなってすごい悔しかったですね。
知ってて何もできないのが一番無力感味わうので最悪でした。
皆さんはこれをみたらダイクストラ法も勉強しましょうね。
僕は...来週かな...

このロジックって頻出するのかというとワーシャルフロイド法が直接役に立ったことはないんだけど、３重ループで全探索みたいな考え方がいろんなシーンでスッと出るようになったのはこの勉強したおかげだなぁと思ってる。