- 253 名前：デフォルトの名無しさん [2017/01/03(火) 13:51:21.27 ID:hCDXc7Qp.net]
- Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。
このとき、Line10-11を実行すると、
d[v] = δ(s, v)
が成り立つ。
証明：
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)
(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。
(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。
