重み付き最短経路

定義 5.1（「グラフアルゴリズム」§5）

$G=(V,E)$ を有向グラフ、 $w:E\to\mathbb{R}_{\ge0}$ を非負の重み関数とする。歩道 $W=(v_0,\ldots,v_k)$ の重みを

w(W) = \sum_{i=0}^{k-1} w(v_i, v_{i+1})

で定める（ $k=0$ のときは $w(W)=0$ ）。 $s,v\in V$ に対し

\delta_w(s,v) = \min \{\, w(W) \mid W \text{ は } s \text{ から } v \text{ への歩道} \,\}

を $s$ から $v$ への最短距離といい、 $v$ が $s$ から到達不能なときは $\delta_w(s,v)=\infty$ と定める。最小値を与える歩道を最短路という。

閉包の状態

定義

定義は閉包の起点です（証明を要しません）。

印の意味: ✓公理まで証明済み・ △証明あり（閉包未完）・ ※主張のみ。テーマごとの集計は閉包の状況。