グラフと動的計画法のプログラム
グラフ（頂点と辺）は、辺の両端を並べた辺の配列か、i 行 j 列に辺の有無や重みを入れた隣接行列（二次元配列）で表す。無向グラフの隣接行列は対称（[u, v] と [v, u] の両方に入れる）。最短距離は、すべての頂点の組について「k を経由した方が近ければ更新」を k = 1〜n でくり返すワーシャル–フロイド法や、近い頂点から確定していくダイクストラ法で求める。編集距離のように、小さな部分問題の答えを表に記録して積み上げる考え方が動的計画法。
解説（冒頭）
この続き：解説の残り・インタラクティブ教材 3 個・練習問題は、ログインして学べます。