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 法になると思うんですけど、ここから先があまりうまく導出できない。