Bellmanの最適性原理

What's this?となっている……

やりたいことは多分

「最短パスPに関して、最後の辺eを除いたパスP'も最短である」

ってことを示したいんだと思っている(けどこれは正確には正しくなくてk本のパスを使う中で？って感じのことを書かれてた)

示せるには示せるけどわからないな……

動機としては

「最短パスPがほしいけど、Pって、わかってる最短パスに辺を加えたものであって欲しいよね(じゃないとパス全探索しなきゃ見つからなくなっちゃう)」

ということで(以下PとかP'はs-tパスとかs-vパスとか脳内補完)

「(k本の辺からなる)Pが最短パス　ならば　最後の辺eを除いたパスP'はk-1本の辺からなるパスの中で最短である」

ということを示したくなる。これが示せると、

「sだけからなる辺の数が0の最短パスから、DPチックに最短経路を決める」

みたいなことができる(これがダイクストラとかの元になってる)

ダイクストラの正当性まで踏み込まないと行けないかなぁ……みたいに思ったりしてるけどそこまで行ける自信がない(オワオワリ)