Dijkstra 法の納得感のある説明について考えている
以前からときどき考えています。完成はしていません。
基本的には距離の短いほうから探索するだけだと思うので、それを典型的な DP っぽく書いてみます。
dp[v][d] := 頂点 v までの距離がちょうど d の walk が存在するかどうか
としてみます。都合で path ではなく walk にしていますが、辺の長さが正なら最短な walk は path なので結果はどっちでも同じです。
そうすると dp[v][d] が成り立つのは v が始点で d = 0 のときと、ある u から v への長さ c の辺があって dp[u][d-c] が成り立っているときなので、d が小さいほうから DP するとテーブルが埋まります。
配る DP で書くとこんな感じになります。
dp[s][0] = true for d from 0: for (u, v, c) in E: if dp[u][d]: dp[v][d+c] = true
でも最短距離が知りたいだけだからこんなに大きなテーブルは必要なくて、最適化すると Dijkstra 法になると思うんですけど、ここから先があまりうまく導出できない。