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

回答5件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。