前提
競プロをしている際に気になったので。
解いていた問題(ABC051 D問題)
ワーシャルフロイド法の理解
自分の理解では始点iから終点jまで点kを経由して経由した場合現時点での最短距離よりも短ければ更新(DPと同じ)する。
という手順と理解しています。
疑問点
なぜ、点kという一点のみ経由しただけで始点iと終点jの最短経路と言えるのでしょうか?
もし、以下の画像のように点kの先に点pがあった場合、
i → k → p → j
という経路が最も重みが少なくなるように思うのですが。

回答5件
あなたの回答
tips
プレビュー
下記のような回答は推奨されていません。
このような回答には修正を依頼しましょう。
また依頼した内容が修正された場合は、修正依頼を取り消すようにしましょう。