競プロ本、地元の図書館に現在ないけど
要望出したら入荷してくれるかなあ・・・？

蟻本って一部だけならグーグルの書籍検索でも読めるんだね
2chのスレでワーシャルフロイドの話あってちょろっと見てみた
中々簡潔に書かれてて読むの大変そう

なるほどdp[k][i][j]の頂点0～kのk+1個の頂点を使った場合のiとjの最短経路をあらわすのか

dp[k-1][i][j]は頂点0～(k-1)のk個の頂点だけを使ったときのiとjの最短経路か
そこに頂点kを加えたときのiとjの最短経路dp[k][i][j]を求めるってこととか
頂点(k-1)までを使った最短経路は求まっているのだから頂点kを経由する経路についてだけ新たに考えればよいと

dp[k-1][i][k]+dp[k-1][k][j]は
iとkのどこも経由しない直通と
kとjのどこも経由しない直通との和になってるはず(ここまでのDPでは頂点kについては考慮してないはずだから)

min(dp[k-1][i][j],dp[k-1][i][k]+dp[k-1][k][j])は
頂点kを一切経由しない最短経路と
頂点kのみを経由する経路とで
最小のほうを選択して頂点0～k個使う場合のiとjの最短経路を求めている・・・

dp[k-1][i][j]は
i -> j の可能性もあるし
i -> a -> b -> j の可能性もある
その中での最短経路、そこに頂点kを加える
i -> k -> j と比較するわけだけど
例えば i -> a -> k -> j のほうが短くなったりしないのだろうか

そうか、本にあるコードは(k-1)を省略した2次元のほうのコードだから
それをそのままdp[k-1][i][j]の3次元のコードとして捉えちゃダメなんだな
使用する頂点の数を考慮する場合は本のとは違うコードにならなければならないのか

これ2次元版と3次元版のコードでは大掛かりな変形が必要な感じがする

これ3次元版から2次元版に落とし込むための理屈はかなり複雑になる気がする

3次元版のときは最初に頂点kを始点あるいは終点とした最短経路を求めてから頂点kを経由する最短経路を求める必要があるのかな？

もし>>81の考え方が合ってるなら蟻本の説明が不適切なん気がするよ・・・

まぁでもワーシャルフロイド法って蟻本でなくても学習できることだし
メジャーなアルゴリズムの説明ならもっと分かりやすく説明してる本やサイトを探すのが解決には早そう

人によって説明の仕方が違うから
一人の人の説明だけに頼らず色んな人の説明を参考にしたほうが
多少時間や手間がかかっても理解には直結しやすいと思うけど

2次元版のは
全ての頂点(0～V)においてiからjまでの頂点0～(k-1)を経由する可能性のある最短経路に対して
頂点kをi,jにおいてそれぞれの頂点0～(k-1)を経由する可能性のある最短経路で経由させた場合に新たなiとjの最短経路になるかっていう感じ

あ、そうか、>>85を考えると>>81は間違いだわ
蟻本の「使う」の言葉の意味の解釈の問題だわ

蟻本の「頂点0～kのみを使う」というのは「最短経路の経由点として使う」という意味なのか
>>73での間違い解釈はi,jに関しては0～(k-1)を使うと思ってたけどそうではなく0～Vを使う
「頂点0～kとi,jのみを使う」って一文、何か不自然さを感じてたけど、「と」による区切れがi,jは0～Vを使うという意味が含まれてたのか

>>73-81までの解釈は完全に間違いだということを理解した

つまり3次元版のdp[k][i][j]は頂点0～kを経由する可能性のあるi間j(頂点0～V)の最短経路を表す

>>73も>>89も間違いがあって
dp[k+1][i][j]が頂点0～kの範囲で
dp[k][i][j]は頂点0～(k-1)だった

3次元を2次元に落とし込める理由は

入力側の頂点(k-1)を1度経由させる経路は
dp[k-1][i][k-1]もdp[k-1][k-1][j]もどちらも頂点(k-1)以降を経由しない(頂点0～(k-2)を経由する可能性のある)最短経路が保証され
2次元のdp[i][k-1]もdp[k-1][j]も同様のことが言える

更新される側の
2次元の場合、dp[i][j]が更新されていくわけで入力側に何らかの影響がありそうな雰囲気を感じることがあるのかもしれないけど
入力に影響がありそうに見えるのはこのiかjがどちらかが(k-1)だった場合、
つまり始点か終点が頂点(k-1)であり、それの最短経路の経由点に頂点(k-1)を含むことはないので入力に全く影響を与えない
3次元で言うと
dp[k][i][k-1]=min(dp[k-1][i][k-1],dp[k-1][i][k-1]+dp[k-1][k-1][k-1])これは常にdp[k][i][k-1]=dp[k-1][i][k-1] (どう見ても自明)
同様にdp[k][k-1][j]についてもいえる
i!=k-1かつj!=k-1のときはdp[k-1][][]からdp[k][][]への計算に再利用はされないから
3次元の最初の次元である使用する頂点の数というのを分けて考える必要ないから2次元に落とし込める

だめだ、俺も日本語下手だわ

>>72-91をもってワーシャルフロイド法の学習修了
競プロ本番ではこれを使う問題に遭遇する機会が少なそうだから
たぶん実際に出題されたタイミングではワーシャルフロイド法のことド忘れしてそう

ワーシャルフロイドでツイッター検索かけると競プロerばかりで競プロでしか使われないのかと思った