Correctness- Part I Lemma Initializing ds<0 and d[v<oo for all ∈V-{s} establishes d v]≥8(s,v) for allve y, and this invariant is maintained over any sequence of relaxation steps Proof Suppose not. Let v be the first vertex for which d[v<8(s, v), and let u be the vertex that caused d[v] to change: d[v=d[u+w(u, v). Then, dlv]<δ(s,y) supposition <8(S, u)+8(u, v) triangle inequality ≤8(s,)+w(l2y)sh.path≤ specific path <dlu+ w(u, v) v is first violation Contradiction.□ o 2001 by Charles E. Leiserson Introduction to Agorithms Day29L17.20© 2001 by Charles E. Leiserson Introduction to Algorithms Day 29 L17.20 Correctness — Part I Lemma. Initializing d[s] ← 0 and d[v] ← ∞ for all v ∈ V – {s} establishes d[v] ≥ δ(s, v) for all v ∈ V, and this invariant is maintained over any sequence of relaxation steps. Proof. Suppose not. Let v be the first vertex for which d[v] < δ(s, v), and let u be the vertex that caused d[v] to change: d[v] = d[u] + w(u, v). Then, d[v] < δ(s, v) supposition ≤ δ(s, u) + δ(u, v) triangle inequality ≤ δ(s,u) + w(u, v) sh. path ≤ specific path ≤ d[u] + w(u, v) v is first violation Contradiction