ワーシャルフロイド法がなぜ2点間で最短といえるのか

Question

前提

競プロをしている際に気になったので。
解いていた問題(ABC051 D問題)

ワーシャルフロイド法の理解

自分の理解では始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。
という手順と理解しています。

疑問点

なぜ、点kという一点のみ経由しただけで始点iと終点jの最短経路と言えるのでしょうか？
もし、以下の画像のように点kの先に点pがあった場合、
i → k → p → j
という経路が最も重みが少なくなるように思うのですが。

Answer 1

「始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。」の点kは固定された点ではなく、全ての点をkとした場合を試します。
ワーシャルフロイド法のアルゴリズムをもう一度確認してください。

通常は、各頂点から直接行ける点への距離辺の長さとし、直接行けないところは無限大とし、自身へは0として初期化し、全ての頂点を順にkとした場合の、kを経由した場合の距離を算出して、「始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。」のです。

Answer 2

Dijをk経由で評価してその時のDik+Dkjである40で更新した後に、Dkjはp経由評価がかかって-480とかになったらDijはどうなるんだ、最短ではないだろう、という話と思います。
その場合、Dipがk経由評価で40をもらっているはずなので、p経由評価でDijが-460になります。経路はikpj。
負の重みを持っていることにより、経由評価の順序によってはDipはj経由評価で-400をもらうので、そのばあいはDijは-900になります。経路はijpj。

Answer 3

ワーシャルフロイド法で負の重みがあるときに解が求められるのはループがない時だけです。一周した時に値が負になるループがあると答えが出ません。ループをずっと回っていれば、いくらでも値が減るからです。j -> k -> p -> jと回っても、単にjとpを行ったり来たりしても、いくらでも値が減っていきます。
英語版WikipediaのFloyd–Warshall algorithmの中のBehavior with negative cyclesの項を参照してください (何故か、日本語版にはループの時の記述がない)。

リンク先の問題の重みは全て正のようですし、疑問点に書いてある図は、そもそも、どこから来たのでしょう?
実は有向グラフで、ループができないようになっているとか?

Comments

[Logarithm]

ワーシャルフロイド法の勉強中には負の重みでも最短経路が分かると書いてあったので、上記の画像の時反例っぽいと思ったので自分で画像を書きました。

Answer 4

i→j→k→pでは、「始点iから終点jまで」という条件を満たしていません。

Comments

[Logarithm]

i → k → p → jでした。申し訳ありません

Answer 5

距離の定義上、距離が負になることはありません

Comments

[Logarithm]

距離の話にしたのが悪かったです。
重みつきグラフです。